[C++]백준 - 1780번 문제

1780번: 종이의 개수 (acmicpc.net)

1780번: 종이의 개수

 

1780번 : 종이의 개수

---

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다.

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

 

입력

---

첫째 줄에 N(1 ≤ N ≤ 37, N은 3k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.

 

 

출력

---

첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.

 

 

---

 

생각해 볼 점

---

2630번 문제와 유사합니다.

 

2630번과 동일한 방식의 재귀를 사용하되, 9번 재귀합니다.

 

우선, 입력 값으로 -1, 0, 1을 받으나, 편의를 위해 +1 씩 더하여 0, 1, 2로 치환하겠습니다.

이렇게 치환되면 배열의 index로 사용하기 편해집니다.

 

재귀 함수에서는 9번의 재귀를 통해, 0, 1, 2의 갯수를 셉니다.

 

재귀 함수로 반환된 값은 3진수로 더하여 모두 동일한 값인지 확인합니다.

 

반환값이 {0, 1, 2}일 경우

0 -> 0 

1 -> 0 * 3 + 1

2 -> ((0 * 3) + 1 ) * 3 + 2

 

와 같이 계산하여

3진수로 012 => 10진수로 5입니다. 

 

3진수로 000,000,000 혹은, 111,111,111 혹은, 222,222,222의 값이면 9개의 반환값이 모두 같으므로

해당하는 숫자의 종이를 하나로 취급하고, 각각 0 혹은 1 혹은 2를 반환합니다.

 

반면, 위의 조건에 해당하지 않으면 9개의 반환값이 다른 것이므로,

큰 음수를 반환하여 상위의 재귀 함수에서 3진수 계산 시 혼동이 없도록 합니다.

 

코드

---

#include <iostream>
using namespace std;


int paper[2187][2187];    //3의 7승 만큼의 공간을 할당
int result[3] = {0, };    //각각 -1의 갯수, 0의 갯수, 1의 갯수

int solution(int N, int x, int y)
{
    if(N == 1) 
    {
        result[paper[y][x]]++;
        return paper[y][x];
        
    }
    
    int sum = 0;    //3진수로 9자리를 받음
    for(int i = 0; i < 3; i++)
    {
        for(int j = 0; j < 3; j++)  
        {
            sum *= 3;
            sum += solution(N / 3, x + i * N / 3, y + j * N / 3);
        }
    }
    
    
    //3진수로 111111111 일경우 9841임
    if(sum == 0 || sum == 9841 || sum == 19682)  
    {
        sum /= 9841;
        result[sum] -= 8;
        return sum;
    }
    //모두 일치하지 않을경우 큰 음수를 반환하여 위의 조건문에 걸리지 않도록 조정
    else return -9999;
}





int main() 
{
	int N;
	scanf("%d", &N);
	for(int i = 0; i < N; i++)
	{
	    for(int j = 0; j < N; j++) 
	    {
	        int input;
	        scanf("%d", &input);
	        paper[j][i] = input + 1;    //입력값 -1, 0, 1을 음이 아닌 정수 index 0,1,2의 형태로 받음
	    }
	}
	solution(N, 0, 0);
	printf("%d\n%d\n%d", result[0], result[1], result[2]);
	
	return 0;
}

 

그 외

---

이차원 배열의 x, y를 혼동하지 않도록 주의합니다.