SWEA 4869 종이붙이기 (python)

 

4869. [파이썬 S/W 문제해결 기본] 4일차 - 종이붙이기

 

파이썬 SW문제해결 기본 - Stack1

2021.06.05 - [Algorithm] - SWEA 4869 종이붙이기 (python)

2021.06.05 - [Algorithm] - SWEA 4866 괄호검사 (python)

2021.06.05 - [Algorithm] - SWEA 4871 그래프 경로 (python)

2021.06.05 - [Algorithm] - SWEA 4873 반목문자 지우기 (python)

 

 

문제

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

그리고 교실 바닥에 20xN 크기의 직사각형을 테이프로 표시하고, 이 안에 준비한 종이를 빈틈없이 붙이는 방법을 찾아보려고 한다. N이 30인 경우 다음 그림처럼 종이를 붙일 수 있다.

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

 

[입력]

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

 

[출력]

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

 

코드

T = int(input())

def tape(N):
    # 만약 N의 길이가 20이라면 3가지 방법밖에 없음
    if N == 20:
        return 3
    # 만약 10이 남았다면 남은 경우의 수는 1가지 밖에 없음
    elif N == 10:
        return 1
    # 아니라면 세로가 왔을때와 가로가 왔을때 두가지 경우가 생김
    # 하지만 가로의 경우 2가지가 생김
    return tape(N-10) + 2*tape(N-20)

for tc in range(1, T+1):
    N = int(input())
    result = tape(N)
    print("#{} {}".format(tc, result))