반응형

TetrisGame1.0

-메인 메뉴 구현

 

<C++ 소스 코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<iostream>
#include<vector>
using namespace std;
#define TABLE_X 20 //테트리스 판 x 축 길이
#define TABLE_Y 30 //테트리스 판 y 축 길이
class MainMenu {
public:
    MainMenu() {
        cout << "\n\n\n\n";
        cout << "\t\t"cout << "@@@@@@@@@@@@  @@@@@@@@@   @@@@@@@@@@@  @@@@@@@@   @   @@@@@@@@@@@\n";
        cout << "\t\t"cout << "      @       @                @       @      @   @   @          \n";
        cout << "\t\t"cout << "      @       @                @       @      @   @   @          \n";
        cout << "\t\t"cout << "      @       @@@@@@@@@        @       @     @    @   @@@@@@@@@@@\n";
        cout << "\t\t"cout << "      @       @                @       @ @ @      @             @\n";
        cout << "\t\t"cout << "      @       @                @       @     @    @             @\n";
        cout << "\t\t"cout << "      @       @@@@@@@@@        @       @      @   @   @@@@@@@@@@@\n\n\n\n\n";
        cout << "\t\t"cout << "                게임을 시작하려면 아무키나 누르세요.\n\n\n\n\n\n\n";
        cout << "\t\t"cout << "                   TetrisGame1.0 By SeokJinLee\n";
        getchar(); // 아무키 입력 기다림
        system("cls"); // 콘솔 창 clear
    }
};
class GameTable {
private:
    int x; // 가로
    int y; // 세로
    vector<vector<int> > table; // 테이블 판 0 = " ", 1 = "▦" , 2  = "■"
public:
    GameTable(int x, int y) { //테트리스 판 뼈대 생성
        this->= x;
        this->= y;
        for (int i = 0; i < y; i++) {
            vector<int> temp;
            for (int j = 0; j < x; j++) {
                temp.push_back(0);
            }
            table.push_back(temp);
        }
        //가장 자리 뼈대 색칠
        for (int i = 0; i < x; i++) {
            table[0][i] = 1;
            table[y - 1][i] = 1;
        }
        for (int i = 1; i < y - 1; i++) {
            table[i][0= 1;
            table[i][x - 1= 1;
        }
    }
    /*게임판 그리는 함수*/
    void DrawGameTable() {
        for (int i = 0; i < y; i++) {
            for (int j = 0; j < x; j++) {
                if (table[i][j] == 1)cout << "▦";
                else cout << "  "// 두 칸 띄우기
            }
            cout << "\n";
        }
    }
};
int main(void) {
    system("mode con cols=100 lines=40 | title 테트리스 게임"); // 콘솔창 크기 및 제목 설정
    GameTable gt(TABLE_X, TABLE_Y); //게임 판 그리기 객체 생성
    MainMenu(); // 메인 메뉴 그리기 생성자 호출
    gt.DrawGameTable(); // 게임판을 그린다.
    getchar();
    return 0;
}
cs

 

반응형
반응형

문제 링크:https://www.acmicpc.net/problem/2014

 

2014번: 소수의 곱

첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 K개의 소수가 오름차순으로 주어진다. 같은 소수가 여러 번 주어지는 경우는 없으며, 주어지는 소수는 모두 541보다 작거나 같은 자연수이다.

www.acmicpc.net

<문제 풀이> 우선순위 큐

각 소수에 대해서 K개의 소수를 계속 곱해 나가면 모든 소수의 곱을 구할 수 있는데, 여기서 중복 없이 구해서 최소 힙에 넣고 N 번째로 작은 수를 구하면 됩니다.

 

모든 소수의 곱을 구할 때 중복을 제거하는 방법은 가장 마지막에 곱해졌던 소수보다 작거나 같은 소수까지만 곱해주면 됩니다.

예를 들어

마지막에 곱해진 소수 2, 3, 5가 있을 때 각 소수에 K개의 소수인 2, 3, 5를 곱했을 때  2 * 3, 2 * 5, 3 * 5는 모두 중복입니다. 마지막에 곱해지는 수보다 큰 수를 곱하는 것은 어차피 뒤에서 한 번 더 곱해지기 때문에 더 곱해줄 필요가 없습니다.
2 x 2 | 3 x 2 | 5 x 2
2 x 3 | 3 x 3 | 5 x 3

2 x 5 | 3 x 5 | 5 x 5

 

<C++ 소스 코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
 
#define MAX (long long)2 << 31
int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int k, n;
    cin >> k >> n;
    priority_queue<long longvector<long long>, greater<long long> > pq;
    vector<int> plist;
    for (int i = 0; i < k; i++) {
        int p;
        cin >> p;
        plist.push_back(p);
        pq.push(p);
    }
    int cnt = 0;
    long long cur = 0;
    while (n--) {
        cur = pq.top();
        pq.pop();
        for (auto& p : plist) {
            if ((long long)p * cur >= MAX)break;
            pq.push(p * cur);
            if (cur % p == 0break; //중복 제거
        }
    }
    cout<<cur;
 
}
cs

 

 

반응형
반응형

문제 링크:https://www.acmicpc.net/problem/2075

 

2075번: N번째 큰 수

첫째 줄에 N(1 ≤ N ≤ 1,500)이 주어진다. 다음 N개의 줄에는 각 줄마다 N개의 수가 주어진다. 표에 적힌 수는 -10억보다 크거나 같고, 10억보다 작거나 같은 정수이다.

www.acmicpc.net

<문제 풀이> 우선순위 큐, 정렬

[정렬]


12MB이므로 2550000 크기의 배열 만들고 내림차순 정렬 후 N번째 수 출력

 

<C++ 소스 코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    vector<int> v(2550000);
    for (int i = 0; i < n * n; i++)cin >> v[i];
    sort(v.begin(), v.end(), greater<int>());
    cout << v[n-1];
    return 0;
}
cs

 

 

 

[우선순위 큐]

 

행마다 N개를 최소 힙에 push ,pop을 반복하면서 힙에 N개를 유지하면 결국 top에 N 번째로 큰 수가 나온다. 

 

<C++ 소스 코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
    int n;
    cin >> n;
    priority_queue<intvector<int>, greater<int> > pq;
    
    for (int i = 0; i < n; i++) {
        int data;
        cin >> data;
        pq.push(data);
    }
 
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < n; j++) {
            int data;
            cin >> data;
            pq.push(data);
        }
        for (int i = 0; i < n; i++)pq.pop();
    }
    cout << pq.top();
    return 0;
}
cs

 

반응형

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 2696번] 중앙값 구하기  (0) 2020.03.19
[백준 2014번] 소수의 곱  (0) 2020.03.13
[백준 1715번] 카드 정렬하기  (0) 2020.03.11
[백준 1002번] 터렛  (0) 2020.03.11
[백준 11286번] 절댓값 힙  (0) 2020.03.10
반응형

문제 링크: https://www.acmicpc.net/problem/1715

 

1715번: 카드 정렬하기

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장의 숫자 카드 묶음을 합치려면 50번의 비교가 필요하다. 매우 많은 숫자 카드 묶음이 책상 위에 놓여 있다. 이들을 두 묶음씩 골라 서로 합쳐나간다면, 고르는 순서에 따라서 비교 횟수가 매우 달라진다. 예를 들어 10장, 20장, 40장의 묶음이 있다면

www.acmicpc.net

<문제 풀이> 우선순위 큐

항상 카드 수가 최소가 되는 카드 묶음끼리 뭉치면 됩니다.

최소 힙을 사용해서 입력받은 데이터를 모두 push 합니다.

 

사이즈가 1이 될 때까지 다음을 반복합니다.

1. 최소 힙에서 두 개를 꺼낸다.

2. 두 개를 더한 결과를 cnt에 추가한다.

3. 두 개를 더한 결과를 최소 힙에 push 한다.

 

<C++ 소스 코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
    int n;
    cin >> n;
    priority_queue<intvector<int>, greater<int> > pq;
    while (n--) {
        int num;
        cin >> num;
        pq.push(num);
    }
    int cnt = 0;
    while (pq.size() != 1) {
        int a = pq.top();
        pq.pop();
        int b = pq.top();
        pq.pop();
        cnt += a + b;
        pq.push(a + b);
    }
    cout << cnt;
 
    return 0;
}
cs

 

반응형

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 2014번] 소수의 곱  (0) 2020.03.13
[백준 2075번] N번째 큰 수  (0) 2020.03.11
[백준 1002번] 터렛  (0) 2020.03.11
[백준 11286번] 절댓값 힙  (0) 2020.03.10
[백준 1927번] 최소 힙  (0) 2020.03.09
반응형

문제 링크: https://www.acmicpc.net/problem/1002

 

1002번: 터렛

각 테스트 케이스마다 류재명이 있을 수 있는 위치의 수를 출력한다. 만약 류재명이 있을 수 있는 위치의 개수가 무한대일 경우에는 -1을 출력한다.

www.acmicpc.net

<문제 풀이> 기하학

아군의 위치를 A(x1, y1), B(x2, y2), 상대편의 위치를 C(x, y)라고 하고 점과 점 사이의 거리를 계산하면
(x - x1)^2 + (y - y1)^2 = r1^2
(x - x2)^2 + (y - y1)^2 = r2^2

따라서 중심이 A, 반지름이 r1인 원과 중심이 B, 반지름이 r2인 원의 교점의 개수를 찾으면 됩니다.

 

1. 두 원이 일치할 때 (r1 = r2 and A = B)


2. 내접할 때 (선분 AB = r2 - r1)

 

두 원이 내접하면 접하는 점과 두 원의 중심이 일직선상에 위치해 있습니다.


3. 외접할 때 (선분 AB = r1 + r2)

 

두 원이 외접할 때 접하는 점과 두 원의 중심이 일직선상에 위치해 있습니다.



4. 두 원이 떨어져 있을 때 (선분 AB > r2 + r1)


5. 원 안에 원이 있을 때 (선분 AB  < r2 - r1)


6. 원이 두 점에서 만날 때 (선분 AB < r1 + r2)

 

<C++ 소스 코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
using namespace std;
 
int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
    int test_case;
    cin >> test_case;
 
    while (test_case--) {
        int x1, y1, r1, x2, y2, r2;
        cin >> x1 >> y1 >> r1 >> x2 >> y2 >> r2;
        int d1 = (x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1);
        int d2 = r1 * r1 + 2*r1 * r2 + r2 * r2;
        int d3 = r1 * r1 - 2 * r1 * r2 + r2 * r2;
 
        if (r1 == r2 && x1 == x2 && y1 == y2) cout << "-1\n"; // 두 원이 일치
        else if (d1 == d3) cout << "1\n"; // 내접
        else if (d1 == d2) cout << "1\n"; // 외접
        else if (d1 > d2) cout << "0\n"; // 두 원이 떨어져있음
        else if (d1 < d3) cout << "0\n"; // 원 안에 다른 원
        else cout << "2\n"; // 두 점에서 만날 때
    }
 
    return 0;
}
cs

 

반응형

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 2075번] N번째 큰 수  (0) 2020.03.11
[백준 1715번] 카드 정렬하기  (0) 2020.03.11
[백준 11286번] 절댓값 힙  (0) 2020.03.10
[백준 1927번] 최소 힙  (0) 2020.03.09
[백준 11279번] 최대 힙  (0) 2020.03.09
반응형

문제 링크: https://www.acmicpc.net/problem/11286

 

11286번: 절댓값 힙

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 0이 아니라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 절댓값이 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 정수는 -231보다 크고, 231보다 작다.

www.acmicpc.net

<문제 풀이> 우선순위 큐

pair로 최소 힙을 만들면 되는데 frist는 x 절댓값을 저장하고 second는 x의 원본을 저장하면 된다.

(절댓값의 최소니깐 first 기준으로 최소 힙을 만들면 됨)

 

<C++ 소스 코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include <iostream>
#include <cmath>
#include <queue>
#include <utility>
using namespace std;
 
typedef pair<intint> pib;
 
pair<intint> p;
 
int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    priority_queue<pib, vector<pib>, greater<pib> > pq;
 
    while (n--) {
        int x;
        cin >> x;
        if (x == 0) {
            if (!pq.empty()) {
                cout << pq.top().second << "\n";
                pq.pop();
            }
            else {
                cout << "0\n";
            }
        }
        else {
            pq.push({ abs(x), x });
        }
    }
    
    return 0;
}
cs

 

반응형

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 1715번] 카드 정렬하기  (0) 2020.03.11
[백준 1002번] 터렛  (0) 2020.03.11
[백준 1927번] 최소 힙  (0) 2020.03.09
[백준 11279번] 최대 힙  (0) 2020.03.09
[백준 1484번] 다이어트  (0) 2020.03.07
반응형

문제 링크: https://www.acmicpc.net/problem/1927

 

1927번: 최소 힙

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 2^31보다 작다.

www.acmicpc.net

<문제 풀이> 우선순위 큐

priority_queue<자료형, 구현체, 비교연산자>
비교연산자에 greater<int> 넣어주면 힙을 오름차순으로 정렬

 

<C++ 소스 코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <queue>
using namespace std;
 
 
int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    priority_queue<intvector<int>, greater<int> > pq;
 
    while (n--) {
        int x;
        cin >> x;
        if (!x) {
            if (!pq.empty()) {
                cout << pq.top()<<"\n";
                pq.pop();
            }
            else {
                cout << "0\n";
            }
        }
        else {
            pq.push(x);
            
        }
    }
    
    return 0;
}
cs

 

반응형

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 1002번] 터렛  (0) 2020.03.11
[백준 11286번] 절댓값 힙  (0) 2020.03.10
[백준 11279번] 최대 힙  (0) 2020.03.09
[백준 1484번] 다이어트  (0) 2020.03.07
[백준 1806번] 부분합  (0) 2020.03.05
반응형

문제 링크: https://www.acmicpc.net/problem/11279

 

11279번: 최대 힙

첫째 줄에 연산의 개수 N(1≤N≤100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 2^31보다 작다.

www.acmicpc.net

<문제 풀이>

priority_queue 사용

<C++ 소스 코드>

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <queue>
using namespace std;
 
 
int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    priority_queue<int> pq;
 
    while (n--) {
        int x;
        cin >> x;
        if (!x) {
            if (!pq.empty()) {
                cout << pq.top()<<"\n";
                pq.pop();
            }
            else {
                cout << "0\n";
            }
        }
        else {
            pq.push(x);
            
        }
    }
    
    return 0;
}
cs

 

반응형

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 11286번] 절댓값 힙  (0) 2020.03.10
[백준 1927번] 최소 힙  (0) 2020.03.09
[백준 1484번] 다이어트  (0) 2020.03.07
[백준 1806번] 부분합  (0) 2020.03.05
[백준 1644번] 소수의 연속합  (0) 2020.03.05

+ Recent posts