[백준] 20187 종이접기 (골드 3)

별로 어렵지 않은 구현문제였는데 아이디어를 떠올리는 데 시간이 조금 걸렸습니다.

 

종이를 R, U, D, L 방향으로 접는데 k번 접고 난 이후에는 변의 길이가 1인 정사각형이 남아있어야 하므로

좌우 방향 접는 횟수와 상하 방향 접는 횟수가 동일하다는 조건이 문제에 주어져 있습니다.

 

문제를 푸는 키 아이디어는 결과적으로 반복된다는 것입니다.

 

2*2 정사각형의 상하좌우의 뚫린 구멍이 모두 결정되고 나면 그러한 정사각형이 반복되는 구조입니다.

 

그러한 구조는 잘 생각해본다면 가장 마지막으로 접은 좌우 방향, 그리고 상하 방향으로 결정됩니다.

 

그리고 그 정보를 통해 우리는 2*2 정사각형의 구멍을 채울 수 있습니다.

 

 

<예시 1>

예를 들어, R L L D U L R D D U 으로 접는다면,

가장 마지막으로 접은 좌우방향은 R이고, 가장 마지막으로 접은 상하 방향은 U입니다.

 

h = 3 이라면 2*2 정사각형의 R U 방향, 즉 오른쪽 아래의 값이 3이 된다는 것을 의미합니다.

이는 곧 2*2 정사각형은 [[0, 1], [2, 3]]으로 구성됨을 알 수 있습니다.

 

<예시 2>

또, U D D D D U R L R L L L 으로 접는다면,

가장 마지막으로 접은 좌우방향은 L이고, 가장 마지막으로 접은 상하 방향은 U입니다.

 

h = 0 이라면 2*2 정사각형의 L U 방향, 즉 왼쪽 아래의 값이 0이 된다는 것을 의미합니다.

이는 곧 2*2 정사각형은 [[2, 3], [0 ,1]]으로 구성됨을 알 수 있습니다.

 

 

이런식으로 얻어낸 2*2 정사각형에 적힌 숫자를

가로, 세로의 길이가 2^k인 정사각형에 반복적으로 채워넣어주면 문제에 대한 답이 됩니다.

 

 

중간 중간 하나의 역할을 하는 함수를 만들어가면서 코딩을 진행하여

구조화된 문제풀이를 할 수 있었습니다.

 

정답 코드는 아래와 같습니다.

import sys
input = sys.stdin.readline

def printArr(arr):
    n = len(arr)
    m = len(arr[0])

    for i in range(n):
        for j in range(m):
            print(arr[i][j], end=" ")
        print()


def update_board(x, y):

    for i in range(2):
        for j in range(2):
            result_board[x+i][y+j] = base_board[i][j]

k = int(input().rstrip())
command = list(input().rstrip().split(' '))
h = int(input().rstrip())

left_right = ''
up_down = ''
for item in command[::-1]:

    if left_right != '' and up_down != '':
        break

    if left_right == '' and (item == "R" or item == "L"):

        if item == "L":
            left_right = 0
        else:
            left_right = 1

    if up_down == '' and (item == "D" or item == "U"):
        
        if item == "U":
            up_down = 0
        else:
            up_down = 1


base_board = [[0 for _ in range(2)] for _ in range(2)]
result_board = [[0 for _ in range(2**k)] for _ in range(2**k)]

type_1 = [
    [0, 1],
    [2, 3]
]

type_2 = [
    [1, 0],
    [3, 2]
]

type_3 = [
    [3, 2],
    [1, 0]
]

type_4 = [
    [2, 3],
    [0, 1]
]



base_board[up_down][left_right] = h

# type1
if base_board[up_down][left_right] == type_1[up_down][left_right]:
    base_board = type_1

# type2
elif base_board[up_down][left_right] == type_2[up_down][left_right]:
    base_board = type_2

# type3
elif base_board[up_down][left_right] == type_3[up_down][left_right]:
    base_board = type_3

# type4
elif base_board[up_down][left_right] == type_4[up_down][left_right]:
    base_board = type_4


for i in range(0, 2**k, 2):

    for j in range(0, 2**k, 2):

        update_board(i, j)


printArr(result_board)