이 문제는 분할정복법으로 푸는 문제로 분할정복법이란 큰 문제를 작은 문제로 나누어 처리하는 방식(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

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


문제는 간단하고 어렵지는 않지만 fgets()와 EOF에 대해 알 수 있는 문제이다.

배열의 크기를 101로 잡게 되면 틀린다!

getchar()를 이용해서 하나씩 받아와도 무관하다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>
 
using namespace std;
 
char input[102];
int main() {
    while(fgets(input, 102, stdin)) {
        int small = 0, capital = 0, num = 0, space = 0;
        for (int i = 0; input[i]; i++) {
            if ('a' <= input[i] && input[i] <= 'z') //small letter
                small++;
            else if ('A' <= input[i] && input[i] <= 'Z') //capital letter
                capital++;
            else if ('0' <= input[i] && input[i] <= '9') //number
                num++;
            else if (input[i] == ' ') //space
                space++;
        }
        printf("%d %d %d %d\n", small, capital, num, space);
    }
    return 0;
}
cs



<Amazing Code From https://www.acmicpc.net/source/4430326>


1
2
3
4
5
6
7
8
9
10
11
12
13
#include <cstdio>
int a,A,n,s;
char c;
int main() {
    while(~(c=getchar())) {
        if(c>='a' && c<='z') a++;
        if(c>='A' && c<='Z') A++;
        if(c>='0' && c<='9') n++;
        if(c==' ') s++;
        if(c=='\n') printf("%d %d %d %d\n", a,A,n,s), a=A=n=s=0;
    }
    return 0;
}
cs


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

[1065번] 한수 - Bruth force & Search[C++]  (0) 2017.03.27
[1181번] 단어 정렬 - Sorting[C++]  (0) 2017.03.27
[10809번] 알파벳 찾기 - String[C++]  (1) 2017.03.15
[10808번] 알파벳 개수 - string[C++]  (0) 2017.03.13
[10828번] 스택 Stack - Stack[C++]  (0) 2017.03.13

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


어려운 문제는 아니고 아이디어만 있다면 간단하게 해결할 수 있다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
#include <string>
 
using namespace std;
int alpha[27];
int main() {
    string input;
    cin >> input;
    for (int i = 0; i < 26; i++)
        alpha[i] = -1;
    for (int i = 0; i < input.length(); i++)
        if(alpha[input[i] - 97] == -1)
            alpha[input[i] - 97] = i;
    for (int j = 0; j < 26; j++)
        cout << alpha[j] << " ";
    return 0;
}
cs


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

[1181번] 단어 정렬 - Sorting[C++]  (0) 2017.03.27
[10820번] 문자열 분석 - String[C++]  (0) 2017.03.15
[10808번] 알파벳 개수 - string[C++]  (0) 2017.03.13
[10828번] 스택 Stack - Stack[C++]  (0) 2017.03.13
[10953번] A+B(6) - 사칙연산[C++]  (0) 2017.03.13

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


이 문제는 간단한 문제로 배열을 생각하지 못한다면 노가다로 빠질 위험이 있다.(알파벳의 개수는 26개다.)


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
#include <string>
 
using namespace std;
 
int alpha[37];
int main() {
    string input;
    cin >> input;
    for (int i = 0; i < input.length(); i++)
        alpha[input[i] - 97]++;
    for (int j = 0; j < 26; j++)
        cout << alpha[j] << " ";
    return 0;
}
cs


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

[10820번] 문자열 분석 - String[C++]  (0) 2017.03.15
[10809번] 알파벳 찾기 - String[C++]  (1) 2017.03.15
[10828번] 스택 Stack - Stack[C++]  (0) 2017.03.13
[10953번] A+B(6) - 사칙연산[C++]  (0) 2017.03.13
[11722번] 가장 긴 감소하는 부분 수열 - LIS & DP[C++]  (0) 2017.03.06

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


그리 어려운 문제는 아니고 라이브러리 쓰는 방법을 블로그에 저장용.


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
#include <iostream>
#include <stack>
#include <string>
 
using namespace std;
 
int main() {
    int N;
    stack<int> stack1;
    cin >> N;
    for (int i = 0; i < N; i++) {
        string str;
        cin >> str;
        if (str == "push") {
            int a;
            cin >> a;
            stack1.push(a);
        }
        else if (str == "top") {
            if (stack1.empty() == 1)
                cout << "-1" << endl;
            else
                cout << stack1.top() << endl;
        }
        else if (str == "size")
            cout << stack1.size() << endl;
        else if (str == "empty")
            cout << stack1.empty() << endl;
        else if (str == "pop") {
            if (stack1.empty() == 1) {
                cout << "-1" << endl;
            }
            else {
                cout << stack1.top() << endl;
                stack1.pop();
            }
        }
    }
    return 0;
}
cs


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

[10809번] 알파벳 찾기 - String[C++]  (1) 2017.03.15
[10808번] 알파벳 개수 - string[C++]  (0) 2017.03.13
[10953번] A+B(6) - 사칙연산[C++]  (0) 2017.03.13
[11722번] 가장 긴 감소하는 부분 수열 - LIS & DP[C++]  (0) 2017.03.06
[11053번] 가장 긴 증가하는 수열 - LIS & DP[C++]  (0) 2017.03.06

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


%*c 를 처음봐서 참고용으로 올리게 되었다.

%*c는 입력은 받지만 저장은 안한다.


1
2
3
4
5
6
7
8
9
10
11
12
13
#include <cstdio>
 
using namespace std;
 
int main() {
    int N, a, b;
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%1d %*c %1d", &a, &b);
        printf("%d\n", a + b);
    }
    return 0;
}
cs


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

[10808번] 알파벳 개수 - string[C++]  (0) 2017.03.13
[10828번] 스택 Stack - Stack[C++]  (0) 2017.03.13
[11722번] 가장 긴 감소하는 부분 수열 - LIS & DP[C++]  (0) 2017.03.06
[11053번] 가장 긴 증가하는 수열 - LIS & DP[C++]  (0) 2017.03.06
[13699번] 점화식 - Dynamic Programming 동적계획법[C++]  (0) 2017.02.20

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


이 문제는 11053번(https://www.acmicpc.net/problem/11053)에서 부등호만 바꾸면 된다.


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
#include <iostream>
#include <cstdio>
 
#pragma warning(disable : 4996)
 
using namespace std;
 
int ary[1001];        //array
int lis[1001];        //LIS values
 
int main() {
    int N, input, output;
 
    scanf("%d", &N);
 
    for (int k = 0; k < N; k++) {
        scanf("%d", &input);
        ary[k] = input;
    }
 
    for (int k = 0; k < N; k++) {
        lis[k] = 1;
    }
 
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j < i; j++) {
            if (ary[i] < ary[j] && lis[i] < lis[j] + 1) {
                lis[i] = lis[j] + 1;
            }
        }
    }
 
    output = lis[0];
    for (int k = 0; k < N; k++) {
        if (output < lis[k]) {
            output = lis[k];
        }
    }
 
    printf("%d", output);
 
    return 0;
}
cs


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

[10828번] 스택 Stack - Stack[C++]  (0) 2017.03.13
[10953번] A+B(6) - 사칙연산[C++]  (0) 2017.03.13
[11053번] 가장 긴 증가하는 수열 - LIS & DP[C++]  (0) 2017.03.06
[13699번] 점화식 - Dynamic Programming 동적계획법[C++]  (0) 2017.02.20
[11726번] 2xn 타일링 - Dynamic Programming 동적계획법[C++]  (0) 2017.02.20

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


Longest Increasing Subsequence(이하 LIS)를 이용하여 푸는 문제이다.

일단 최대한 간단하고 직관적으로 풀었다.

ary[]에는 값을 전부다 받아왔고

lis[]는 배열을 줄을 세워 줄의 길이를 넣었다. 초기값은 1로 해야한다.

output는 lis[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
#include <iostream>
#include <cstdio>
 
#pragma warning(disable : 4996)
 
using namespace std;
 
int ary[1001];        //array
int lis[1001];        //LIS values
 
int main() {
    int N, input, output;
    int sum = 0;
 
    scanf("%d", &N);
 
    for (int k = 0; k < N; k++) {
        scanf("%d", &input);
        ary[k] = input;
    }
 
    for (int k = 0; k < N; k++) 
        lis[k] = 1;
 
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j < i; j++) {
            if (ary[i] > ary[j] && lis[i] < lis[j] + 1) {
                lis[i] = lis[j] + 1;
            }
        }
    }
 
    output = lis[0];
    for (int k = 0; k < N; k++) {
        if (output < lis[k]) {
            output = lis[k];
        }
    }
 
    printf("%d", output);
 
    return 0;
}
cs


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

[10953번] A+B(6) - 사칙연산[C++]  (0) 2017.03.13
[11722번] 가장 긴 감소하는 부분 수열 - LIS & DP[C++]  (0) 2017.03.06
[13699번] 점화식 - Dynamic Programming 동적계획법[C++]  (0) 2017.02.20
[11726번] 2xn 타일링 - Dynamic Programming 동적계획법[C++]  (0) 2017.02.20
[1010번] 다리 놓기 - Dynamic Programming 동적 계획법[C++]  (0) 2017.02.20

+ Recent posts

티스토리툴바