문제 출처 : [SWEA] 4869 종이 붙이기
learn -> course -> programming intermediate -> stack1 -> 종이 붙이기

문제

어린이 알고리즘 교실의 선생님은 경우의 수 놀이를 위해, 그림처럼 가로x세로 길이가 10x20, 20x20인 직사각형 종이를 잔뜩 준비했다.

그리고 교실 바닥에 20xN 크기의 직사각형을 테이프로 표시하고, 이 안에 준비한 종이를 빈틈없이 붙이는 방법을 찾아보려고 한다.

10의 배수인 N이 주어졌을 때, 종이를 붙이는 모든 경우를 찾으려면 테이프로 만든 표시한 영역을 몇 개나 만들어야 되는지 계산하는 프로그램을 만드시오. 직사각형 종이가 모자라는 경우는 없다.

입력

첫 줄에 테스트 케이스 개수 T가 주어진다. 1≤T≤50
다음 줄부터 테스트 케이스 별로 N이 주어진다. 10≤N≤300, N은 10의 배수

출력

각 줄마다 "#T" (T는 테스트 케이스 번호)를 출력한 뒤, 답을 출력한다.

코드

# 경우의 수를 구하는 재귀함수
def paper(N):
    # N이 0이거나 1이면 1을 return
    if N == 0 or N == 1:
        return 1
    # 그 외의 경우에는 재귀를 이용
    else:
        return paper(N-1) + paper(N-2) * 2


T = int(input())
for tc in range(1, T + 1):
    N = int(input()) // 10      # 가로의 길이를 받아옴
    result = paper(N)       # 함수의 return 값을 저장할 변수

    print(f'#{tc} {result}')

풀이 방법

처음엔 어떻게 접근해야할지 막막해서 경우의 수를 하나하나 따져보았다. 이 경우의 수에서 규칙성을 찾아서 재귀함수로 코드를 짜주었다. 현재 경우의 수가 (n-1) + 2*(n-2) 라는 것을 찾아내는 것이 어려웠던 문제였다.