[백준] 1780번 리뷰

서론

코딩 테스트를 위해서 꾸준히 진도를 밀면서 연습하고 있다. 제한시간 안에 풀지 못하는 문제는 솔루션을 통해서 코드를 확인하고 접근법을 학습한다. 이후 해당 접근법은 Anki로 기록하여 복습하고 추후 다시 풀어보는 방식으로 학습을 진행하고 있다. 처음엔 어색했지만 나름 진전이 있다고 생각한다. 현재는 재귀를 풀고 있는데, 그 중 재밌는 문제가 있어서 소개하고자 한다.

본론

[ 1780번 서술 ]
N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1 중 하나가 저장되어 있다. 
우리는 이 행렬을 다음과 같은 규칙에 따라 적절한 크기로 자르려고 한다.

만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
(1)이 아닌 경우에는 종이를 같은 크기의 종이 9개로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.
이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

조건 해석

강의를 통해 수학적 귀납법을 생각하면 좋다는 팁을 얻었다. 이 팁을 통해서 문제에 접근해보자!

F(1) = 9
F(k) = 9 × F(k-1)
F(k+1) = 9 × F(k)

이 수학적 귀납법(?)을 통해서 다음과 같은 사실을 알 수 있다.

• 종이의 구조는 재귀적이다.
• 종이의 최소 단위는 9칸 (3 × 3)
• 종이는 ×9 단위로 확장된다.

이제 우리는 입력된 K를 3으로 나눠서, 종이를 똑같이 9개로 나눌 것이다. 만약 계속해서 등분하다 더 나눌 수 없는 경우에 도달한다면, 우린 어떻게 해야 할까?

우리의 최종 목표는 종이를 세는 것이다. 이를 위해서는 구성 원소를 알아야 한다. 잘린 종이를 구성하는 원소를 알아야 이 종이에 대한 핵심 결정을 내릴 수 있다. 그렇기 때문에, 우리는 초기값에 도달하였을 때 구성 원소를 반환하여 재귀를 하나씩 풀 것이다.

우린 구성 원소를 하나하나 모은 뒤, 모든 원소가 같다면 이를 압축하며 하나의 원소로 만들 것이다. 만약 원소가 하나라도 다르면 압축을 거치지 않고 원소 리스트를 반환할 것이다. 이 과정을 재귀 함수에서 수행한다면 무사히 최종 원소를 구할 수 있다.

모든 함수가 종료되고 최종 원소 리스트를 받았다면 이를 세기만 하면 끝이다!

더 좋은 풀이가 있을 것이라고 생각한다, 그러나 난 이렇게 풀긴 했다.

코드

from sys import stdin
def input(): return stdin.readline().strip()

SIDE = int(input())

def sol(paper, n, y, x):
    
    elements = []
    if n == 1: 
        elements.append(paper[y][x])
        return elements
    
    unit = n // 3
    DIR = [ 0, unit, unit * 2]
    
    for ay in DIR:
        dy = y + ay
        for ax in DIR:
            dx = x + ax
            result = sol(paper, unit, dy, dx)
            elements.extend(result)
    
    element_set = set(elements)
    if len(element_set) == 1: return list(element_set)
    return elements
    
if __name__ == '__main__':

    paper = []
    for _ in range(SIDE): 
        paper.append(list(map(int, input().split())))
    
    elements = sol(paper, SIDE, 0, 0)
    counter = { 0: 0, 1: 0, -1: 0}
    
    for element in elements:
        counter[element] += 1
        
    print(counter[-1])
    print(counter[0])
    print(counter[1])

결론

1. 수학적 귀납법 관점에서 생각하니까 많이 진전된다.
2. 원소를 모으고 바로바로 세려다가 시간을 많이 허비했다.
3. 큰 문제 나누고 천천히 생각하는 연습이 많이 도움된다.