[Algorithm] 7주차 스터디 - 분할정복

1. 색종이 - 2 (실버 5)

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

2567번: 색종이 - 2

문제

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int paper[102][102];
 
int y_dir[4] = {-1, 0, 1, 0};
int x_dir[4] = {0, -1, 0, 1};

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int N;
    scanf("%d", &N);
 
    while (N--)
    {
        int x, y;
        scanf("%d %d", &y, &x);
        for (int i = y; i < y + 10; i++)
            for (int j = x; j < x + 10; j++)
                    paper[i][j] ++;
    }
 
    int sum(0);
    for (int i = 0; i <= 100; i++)
        for (int j = 0; j <= 100; j++)
            if (paper[i][j] == 0)
                for (int k = 0; k < 4; k++){
                    int new_y = i + y_dir[k];
                    int new_x = j + x_dir[k];
                    if ((0 <= new_y && new_y <= 100) && (0 <= new_x && new_x <= 100) && paper[new_y][new_x] >= 1)
                        sum++;
                }
 
    cout << sum;
    return 0;
}

문제풀이

색종이에 해당하는 좌표들을 넣고, 도화지의 최대 크기인 100*100를 반복문으로 돌아가면서 본다.

해당하는 좌표에 색종이가 없을 경우 그 좌표의 상하좌우 값을 찾아서 그 값이 1과 100 사이에 있고 도화지에서 그 값이 1보다 클 경우 그 변이 둘레로 적합하다고 판단하고 더한다.

 

2. 색종이 만들기 (실버 3)

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

2567번: 색종이 - 2

문제

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int paper[128][128];
int N;
int b, w;

void solve(int y, int x, int size){
    int ck = paper[y][x];

    for (int i = y; i < y + size; i++){
        for (int j = x; j < x + size; j++){

            if (ck == 0 && paper[i][j] == 1){
                ck = 2;
            }
            else if (ck == 1 && paper[i][j] == 0){
                ck = 2;
            }
            if (ck == 2){
                solve(y, x, size/2);
                solve(y, x + size/2, size/2);
                solve(y + size/2, x, size/2);
                solve(y + size/2, x + size/2, size/2);

                return;
            }
        }
    }
    if (ck == 0) w++;
    else b++;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> paper[i][j];

    solve(0, 0, N);
    cout << w << '\n' << b << '\n';

    return 0;
}

문제풀이

문제를 푸는 과정을 분할정복에 맞게 solve(int y, int x, int size)라는 함수로 분할하였다. solve의 x와 y는 탐색하는 사분면의 첫 좌표이며 size는 한 변의 길이다.

ck 변수에 현재 좌표의 색을 할당해주고 그와 다른 색이 존재하는지 확인한다. 만약 존재한다면 자를 수 없으므로 4등분하고, 같은 색이면 변수에 더해준다.

 

3. 222-풀링 (실버 2)

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

17829번: 222-풀링

문제

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int p[1024][1024];
int N, sum;

int solve(int y, int x)
{
    vector<int>a;
    for (int i = x; i < x + 2; i++)
        for (int j = y; j < y + 2; j++)
            a.push_back(p[i][j]);
    sort(a.begin(), a.end());
    return a[2];
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> p[i][j];
        }
    }
    while (N > 1)
    {
        for (int i = 0; i < N; i+=2)
            for (int j = 0; j < N; j+=2)
                p[i/2][j/2] = solve(j, i);
        N /= 2;
    }
    cout << p[0][0] << '\n';

    return 0;
}

문제풀이

B와 마찬가지로 분할정복에 맞게 solve(int y, int x)라는 함수로 분할하였다. solve는 paper안을 정렬하고 그 중 두 번째로 큰 수를 반환한다.

메인에서 스트라이드 값이 2 이므로 x, y축 각 2씩 움직이며 paper 내의 값을 갱신한다.

 

 

4. Z (실버 1)

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

1074번: Z

문제

코드

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int N;
int r, c;
int result;

void solve(int x, int y, int n) {
    
    if(x == r && y == c) {
        cout<< result;
        return; 
    }

    if(r <= x+n-1 && c <= y+n-1);
    else {
        result += n*n;
        return;
    }
    
    solve(x, y, n/2);
    solve(x + n/2, y, n/2); 
    solve(x, y + n/2, n/2); 
    solve(x + n/2, y + n/2, n/2); 
    
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N;
    cin >> r >> c;

    solve(0, 0, pow(2, N));

    return 0;
}

문제풀이

solve의 x와 y는 시작 좌표이고 n은 한 변의 길이이다. solve에서 현재 영역이 원하는 좌표를 포함하지 않을 경우 영역의 크기만큼 넘기며 모든 섹션에 대해 반복한다.

main에서 n^2만큼의 길이로 0, 0부터 탐색을 시작한다.