[스터디] 문제 풀이 - 7주차

실 - 2630, 1780, 1446
골 - 5972, 5430, 14503
프 - 입국심사

---

2630번

문제

분할정복 / 조건을 만족할 때까지 색종이를 자른다.

파이썬 풀이

import sys
input = sys.stdin.readline

n = int(input())
papers = [list(map(int, input().strip().split())) for _ in range(n)]
w, b = 0, 0

def countPapers(x, y, n):
    global w, b
    count_blue = 0
    for i in range(x, x+n):
        for j in range(y, y+n):
            if papers[i][j]:
                count_blue += 1
    if count_blue == 0:
        w += 1
    elif count_blue == n**2:
        b += 1
    else:
        countPapers(x, y, n//2)
        countPapers(x + n//2, y, n//2)
        countPapers(x, y + n//2, n//2)     
        countPapers(x + n//2, y + n//2, n//2)
    
countPapers(0, 0, n)
print(w)
print(b)

C++ 풀이

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> papers;
int n;
int w = 0, b = 0;

void countPapers(int x, int y, int n){
    int count_b = 0;
    for(int i = x; i < x + n; ++i){
        for(int j = y; j < y + n; ++j){
            if(papers[i][j]) {++count_b;}
        }
    }
    if(count_b == 0) {++w;}
    else if(count_b == n * n) {++b;}
    else {
        countPapers(x, y, n/2);
        countPapers(x + n/2, y, n/2);
        countPapers(x, y + n/2, n/2);
        countPapers(x + n/2, y + n/2, n/2);
    }
}

int main(){
    scanf("%d", &n);
    papers = vector<vector<int>>(n, vector<int>(n));
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            scanf("%d", &papers[i][j]);
        }
    }
    countPapers(0, 0, n);
    printf("%d\n%d", w, b);
    
    return 0;
}

1780번

문제

분할정복 / 시간초과 주의!!

파이썬 풀이

import sys
input = sys.stdin.readline

n = int(input())
papers = [list(map(int, input().strip().split())) for _ in range(n)]
a, b, c = 0, 0, 0

def countPapers(x, y, n):
    global a, b, c
    check_num = papers[x][y]
    for i in range(x, x+n):
        for j in range(y, y+n):
            if check_num != papers[i][j]:
                # 1행
                countPapers(x, y, n//3)
                countPapers(x, y + n//3, n//3)
                countPapers(x, y + n//3 * 2, n//3)
                # 2행
                countPapers(x + n//3, y, n//3)
                countPapers(x + n//3, y + n//3, n//3)
                countPapers(x + n//3, y + n//3 * 2, n//3)
                # 3행
                countPapers(x + n//3 * 2, y, n//3)     
                countPapers(x + n//3 * 2, y + n//3, n//3)
                countPapers(x + n//3 * 2, y + n//3 * 2, n//3)
                return
        
    if check_num == -1:
        a += 1
    elif check_num == 0:
        b += 1
    elif check_num == 1:
        c += 1       
    
countPapers(0, 0, n)
print(a)
print(b)
print(c)

2630번과 동일한 방식으로 풀면 시간초과가 난다.
잘린 영역에 해당하는 모든 숫자를 확인하는 것이 아니라 첫번째 숫자와 다른 숫자가 등장하는 순간 해당 함수를 종료해주어야한다.
return을 이용하여 종료해준다.

C++ 풀이

#include <iostream>
#include <vector>

using namespace std;

vector<vector<int>> papers;
int n;
int a = 0, b = 0, c = 0;

void countPapers(int x, int y, int n){
    int check_num = papers[x][y];
    for(int i = x; i < x + n; ++i){
        for(int j = y; j < y + n; ++j){
            if(papers[i][j] != check_num){
                countPapers(x, y, n/3);
                countPapers(x, y + n/3, n/3);
                countPapers(x, y + n/3 * 2, n/3);
                countPapers(x + n/3, y, n/3);
                countPapers(x + n/3, y + n/3, n/3);
                countPapers(x + n/3, y + n/3 * 2, n/3);
                countPapers(x + n/3 * 2, y, n/3);
                countPapers(x + n/3 * 2, y + n/3, n/3);
                countPapers(x + n/3 * 2, y + n/3 * 2, n/3);
                return;
            }
        }
    }
    if(check_num == -1) {++a;}
    else if(check_num == 0) {++b;}
    else {++c;}
}

int main(){
    scanf("%d", &n);
    papers = vector<vector<int>>(n, vector<int>(n));
    for(int i = 0; i < n; ++i){
        for(int j = 0; j < n; ++j){
            scanf("%d", &papers[i][j]);
        }
    }
    countPapers(0, 0, n);
    printf("%d\n%d\n%d", a, b, c);
    
    return 0;
}

1446번

문제

파이썬 풀이

C++ 풀이

---

5972번

문제

파이썬 풀이

C++ 풀이

5430번

문제

파이썬 풀이

C++ 풀이

14503번

문제

파이썬 풀이

C++ 풀이

---

입국심사

문제

파이썬 풀이

C++ 풀이