이 문제는 분할정복법으로 푸는 문제로 분할정복법이란 큰 문제를 작은 문제로 나누어 처리하는 방식(Top-down)으로

보통 재귀를 이용한 방법이 일반적이다.

이 문제를 좀 오래동안 풀었는데 그 이유는 for문에 j를 써야하는데 i라고 써서 눈이 나쁜 필자는 이걸 찾는데 일주일이 걸렸다고 한다...
이 문제와 비슷한 문제로는 쿼드트리가 있다.



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
#include <iostream>
 
using namespace std;
 
int output[3];  // -1 0 1
int arr[2187][2187];
 
void paper(int x, int y, int N){
    int first = arr[x][y];
    bool flag = true;
    
    for(int i = x; i < x + N; i++){
        for(int j = y; j < y + N; j++){
            if(arr[i][j] != first){
                flag = false;
                break;
            }
        }
    }
    
    if(flag) {
        output[first + 1]++;
    }
    else {
        for(int a = x; a < x + N; a += N/3 ){
            for(int b = y; b < y + N; b += N/3){
                paper(a, b, N/3);
            }
        }
    }
}
 
int main(){
    int N;
    
    cin >> N;
    
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> arr[i][j];
        }
    }
    
    paper(0, 0, N);
    
    for(int i = 0; i < 3; i++){
        cout << output[i] << endl;
    }
    
    return 0;
}
 
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[11758번] CCW - CCW 알고리즘[C++]  (0) 2017.08.24
[1463번] 1로 만들기 - 동적계획법 [C++]  (0) 2017.05.11
[1065번] 한수 - Bruth force & Search[C++]  (0) 2017.03.27
[1181번] 단어 정렬 - Sorting[C++]  (0) 2017.03.27
[10820번] 문자열 분석 - String[C++]  (0) 2017.03.15

https://www.acmicpc.net/problem/1065


이 문제는 일단 한수라는 개념을 알아야한다. 한수란 각 자리수가 등차수열이 되어야 한다. 예를 들면, 234, 357 등으로 각 자리수가 등차수열만 만족시키면 된다. 여기서 문제는 100이하는 어떻게 해야하는가인데, 결론은 100이하의 수는 무조건 한수이다. 예를 들면, 25, 36, 29 등 무조건 한수의 조건을 만족시킨다. 이 개념만 알고 시작하면 어려운 문제는 아니다. 일단 직관적으로 풀었다. 더 좋은 방법도 충분히 많이 있을 것이라 생각이 드는 문제이다.


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
#include <iostream>
 
using namespace std;
 
int han(int input, int count) {
    if (input < 100)
        return count += input;
    else if (input == 1000)
        han(input - 1, count);
    else {
        if ((input / 100 - (input % 100) / 10) == (input % 100) / 10 - (input % 10) / 1)
            count++;
        han(input - 1, count);
    }
}
 
int main() {
    int N;
    int count = 0;
    cin >> N;
 
    cout << han(N, count);
 
    return 0;
}
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[1463번] 1로 만들기 - 동적계획법 [C++]  (0) 2017.05.11
[1780번] 종이의 개수 - 분할정복법 [C++]  (1) 2017.05.11
[1181번] 단어 정렬 - Sorting[C++]  (0) 2017.03.27
[10820번] 문자열 분석 - String[C++]  (0) 2017.03.15
[10809번] 알파벳 찾기 - String[C++]  (1) 2017.03.15

https://www.acmicpc.net/problem/1186


간단히 정렬하는 문제로 좀 특이한 점이 있다면 단어 길이 sorting를 신경써야한다는 점이다.


처음 든 생각은 length 와 string을 구조체에 넣고 계산할까 하다가


string 타입과 sort함수를 사용하면 코드가 간결해질 것 같은 느낌적인 느낌이 들어서 이들을 이용하였다.


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 <string>
#include <string.h>
#include <algorithm>
 
using namespace std;
 
bool compare(const string& a, const string& b){
    if(a.length() == b.length())
        return (a < b);
    else
        return a.length() < b.length();
}
 
int main() {
    int N;
    string input[20001];
    
    cin >> N;
    
    for(int i = 0; i < N; i++)
        cin >> input[i];
    
    sort(input, input + N, compare);
 
    for(int i = 0; i < N; i++){
        if(input[i] == input[i-1] && i != 0)
            continue;
        cout << input[i] << endl;
    }
    
    return 0;
}
cs


'Algorithm Problems > BOJ' 카테고리의 다른 글

[1780번] 종이의 개수 - 분할정복법 [C++]  (1) 2017.05.11
[1065번] 한수 - Bruth force & Search[C++]  (0) 2017.03.27
[10820번] 문자열 분석 - String[C++]  (0) 2017.03.15
[10809번] 알파벳 찾기 - String[C++]  (1) 2017.03.15
[10808번] 알파벳 개수 - string[C++]  (0) 2017.03.13

+ Recent posts

티스토리툴바