BOJ : https://www.acmicpc.net/problem/1992

 

1992번: 쿼드트리

첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1≤N ≤64의 범위를 가진다. 두 번째 줄부터는 길이 N 의 문자열이 N 개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

www.acmicpc.net

문제 해결을 위한 알고리즘 : 분할정복, 재귀

문제 난이도 : 최최하

 

구간마다 반복문을 통해 통일되었는지 안되었는지 확인하고

안되었으면 ( 입력후에

간단하게 재귀로 구간을 나눠서 호출해주고

재귀가 끝나는 곳에 ) 을 작성해주면 된다.

 

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
#include <cstdio>
#include <string>
using namespace std;
 
int arr[65][65];
string s;
int index;
int cnt;
 
void quad(int size, int y, int x) {
    bool check = true;
    int start = arr[y][x];
    for (int i = y; i < y + size; i++) {
        for (int j = x; j < x + size; j++) {
            if (start != arr[i][j]) {
                check = false;
                break;
            }
        }
        if (check == false) break;
    }
    if (check == true) {
        if (start == 1) 
            s.insert(index++, "1");
        else 
            s.insert(index++, "0");
    }
    else {
        s.insert(index++, "("); cnt++;
        quad(size / 2, y, x);
        quad(size / 2, y, x + size / 2);
        quad(size / 2, y + size / 2, x);
        quad(size / 2, y + size / 2, x + size / 2);
        if (cnt > 0) cnt--, s.insert(index++, ")");
    }
}
 
int main() {
    int N;
    scanf("%d", &N);
 
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            scanf("%1d", &arr[i][j]);
        }
    }
 
    quad(N, 1, 1);
    for (int i = 0; i < s.size(); i++)
        printf("%c", s[i]);
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter

 

'algorithm > BOJ' 카테고리의 다른 글

BOJ 11729번 하노이 탑 이동 순서  (0) 2019.05.31
백준 1780번 : 종이의 개수 - Junnnho  (0) 2019.05.30
백준 1011번 : Fly me to the Alpha Centauri - Junnnho  (0) 2019.05.19
백준 2529번 : 부등호 Junnnho  (0) 2019.05.17
BOJ 2252번 줄세우기  (0) 2019.05.17

BOJ : https://www.acmicpc.net/problem/1011

 

1011번: Fly me to the Alpha Centauri

우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행사가 되어 새로운 세계에 발을 내려 놓는 영광의 순간을 기다리고 있다. 그가 탑승하게 될 우주선은 Alpha Centauri라는 새로운 인류의 보금자리를 개척하기 위한 대규모 생활 유지 시스템을 탑재하고 있기 때문에, 그 크기와 질량이 엄청난 이유로 최신기술력을

www.acmicpc.net

 

처음 스타트가 1 마지막이 1이 되도록 해줄려면

증가해주다가 마지막으로 다가갈수록 감소시켜서 마지막 전단계가 2가 되거나 1이 되야 1칸을 이동할 수 있다.

문제를 손으로 써보면 규칙이 보인다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <cstdio>
int main(){
    int count, T, temp, tempcheck;
    long long F, S;
    scanf("%d", &T);
    while (T--) {
        scanf("%lld%lld", &F, &S);
        count = 1 , temp = 1, tempcheck = 0;
        long long minus = 1;
        while (1) {
            if (minus + temp <= S - F) {
                tempcheck++, minus += temp, count++;
                if (tempcheck == 2) tempcheck = 0, temp++;
            }
            else if (minus + temp > S - F) {
                printf("%d\n", count);
                break;
            }
        }
    }
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

백준 1780번 : 종이의 개수 - Junnnho  (0) 2019.05.30
백준 1992번 : 쿼드트리 - Junnnho  (0) 2019.05.29
백준 2529번 : 부등호 Junnnho  (0) 2019.05.17
BOJ 2252번 줄세우기  (0) 2019.05.17
백준 2623번 - 음악프로그램 Junnnho  (0) 2019.05.15

BOJ : https://www.acmicpc.net/problem/2529

 

2529번: 부등호

두 종류의 부등호 기호 ‘<’와 ‘>’가 k개 나열된 순서열  A가 있다. 우리는 이 부등호 기호 앞뒤에 서로 다른 한 자릿수 숫자를 넣어서 모든 부등호 관계를 만족시키려고 한다. 예를 들어, 제시된 부등호 순서열 A가 다음과 같다고 하자.  A =>  < < < > < < > < > 부등호 기호 앞뒤에 넣을 수 있는 숫자는 0부터 9까지의 정수이며 선택된 숫자는 모두 달라야 한다. 아래는 부등호 순서열 A를 만족시키는 한 예이다.  3 < 4 < 5 <

www.acmicpc.net

문제풀이를 위한 알고리즘 : 그리디 알고리즘(or 위상 정렬)

 

도대체 여기에 위상정렬을 어떻게 적용하는건지

적응력이 부족한 실력때문에 그냥 그리디로 해결하였다.

 

가장 큰 수를 찾기 위해서는 맨 앞자리가 9로 시작하면 되고

가장 작은 수를 찾기 위해서는 맨 앞자리가 0으로 시작하게 하여서 < 과 > 를 비교해가며 해결하였다.

 

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
68
69
70
71
72
73
74
75
#include <cstdio>
#include <algorithm>
using namespace std;
 
int N, arr[10], min_num, max_num;
char charr[9];
bool check;
 
void find_min() {
    arr[0] = 0;
    max_num = 0;
    for (int i = 1; i < (N + 1); i++) {
        if (charr[i-1] == '<') {
            arr[i] = max_num + 1;
            max_num++;
        }
        else {
            for (int k = i - 1; k >= 0; k--) {
                if (k >= 1) {
                    arr[k]++;
                    max_num = max(arr[k], max_num);
                    if (charr[k - 1] == '<')
                        break;
                }
                else {
                    arr[k]++;
                    max_num = max(arr[k], max_num);
                }
            }
            arr[i] = arr[i - 1] - 1;
        }
    }
    for (int i = 0; i <= N; i++)
        printf("%d", arr[i]);
}
 
void find_max() {
    arr[0] = 9;
    min_num = 9;
    for (int i = 1; i < (N + 1); i++) {
        if (charr[i-1] == '<') {
            for (int k = i - 1; k >= 0; k--) {
                if (k >= 1) {
                    arr[k]--;
                    min_num = min(arr[k], min_num);
                    if (charr[k - 1] == '>')
                        break;
                }
                else {
                    arr[k]--;
                    min_num = min(arr[k], min_num);
                }
            }
            arr[i] = arr[i - 1] + 1;
        }
        else {
            arr[i] = min_num - 1;
            min_num--;
        }
    }
    for (int i = 0; i <= N; i++)
        printf("%d", arr[i]);
}
 
int main() {
    scanf("%d\n", &N);
    for (int i = 0; i < N; i++) {
        scanf("%c", &charr[i]);
        if (i + 1 != N) scanf(" ");
    }
    find_max();
    printf("\n");
    find_min();
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter

 

'algorithm > BOJ' 카테고리의 다른 글

백준 1992번 : 쿼드트리 - Junnnho  (0) 2019.05.29
백준 1011번 : Fly me to the Alpha Centauri - Junnnho  (0) 2019.05.19
BOJ 2252번 줄세우기  (0) 2019.05.17
백준 2623번 - 음악프로그램 Junnnho  (0) 2019.05.15
백준 : 1516번 - 게임 개발 Junnnho  (0) 2019.05.14

BOJ : https://www.acmicpc.net/problem/2252

github : https://github.com/junho0956/Algorithm/blob/master/2252/2252/%EC%86%8C%EC%8A%A4.cpp

 

위상정렬 형태의 코드입니다.

 

v[a] 내부의 값들은 a 뒤에 와야하는 값들을 의미하는 것이고

in[b] 의 값들은 b 앞에 와야하는 값들의 갯수 입니다.

이 값들을 비교대로 나열했다고 생각해보면 반드시 가장 앞에 서야하는 값이 존재하게 됩니다.

그게 in[b] == 0 의 기준이 됩니다.

이 값들을 queue 에 넣어놓고, 현재 queue 내부의 값들에는 순서(서열)가 상관없으니

순서대로 뽑아서 자신의 뒤에 와야할 숫자들을 탐색합니다.

in[자신의 뒤에 올 숫자]를 비교할때마다 1씩 감소시키다가

in[자신의 뒤에 올 숫자]가 0이 된다면 더이상 그 숫자와는 비교될 숫자가 없는 것이니 queue에 삽입합니다.

 

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
#include <queue>
#include <cstdio>
#include <vector>
using namespace std;
 
vector<int> v[32001];
int in[32001];
queue<int> q;
 
int main() {
    int N, M, a, b;
    scanf("%d%d", &N, &M);
    for (int i = 0; i < M; i++) {
        scanf("%d%d", &a, &b);
        v[a].push_back(b);
        in[b]++;
    }
    for (int i = 1; i <= N; i++) {
        if (in[i] == 0) {
            q.push(i);
        }
    }
 
    while (!q.empty()) {
        int parent = q.front();
        q.pop();
        printf("%d ", parent);
        for (int i = 0; i < v[parent].size(); i++) {
            int child = v[parent][i];
            in[child]--;
            if (!in[child]) q.push(child);
        }
    }
}
http://colorscripter.com/info#e" target="_blank" style="color:#4f4f4f; text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

백준 1011번 : Fly me to the Alpha Centauri - Junnnho  (0) 2019.05.19
백준 2529번 : 부등호 Junnnho  (0) 2019.05.17
백준 2623번 - 음악프로그램 Junnnho  (0) 2019.05.15
백준 : 1516번 - 게임 개발 Junnnho  (0) 2019.05.14
2568번 : 전깃줄2 - Junnnho  (0) 2019.04.08

+ Recent posts

티스토리툴바