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

SW Expert Academy에서 학습용으로 문제를 가져왔습니다. 문제가 될 시 수정, 삭제하겠습니다.

https://swexpertacademy.com/main/main.do

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

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

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

[입력]

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

[출력]

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

input

3
30
50
70

output

#1 5
#2 21
#3 85

code

Test_case=int(input())

def function(N):
    if N%10==0:
        if N==10: #N=10일때 1반환
            return 1
        elif N==20: #20x20은 3반환 
            return 3
        else:
            return function(N-10)+(2*function(N-20))
    else:
        print("10의 배수만 입력하세요")

for t in range(1, Test_case+1):
    N=int(input())
    count=function(N)
    print("#{} {}".format(t,count))

이 문제를 풀기위해서 먼저 패턴을 유의깊게 봐야합니다.
N을 밑변의 길이라고 두고 그림을 그려보면
N=10인 경우인 20x10 F(1)=1
N=20인 경우인 20x20 F(2)=3
N=30인 20x30은 문제에서 나와있는데로 F(3)=5
N=40인 20x40은 F(4)=11 (일일히 그림을 그려봤을때)
N=50인 20x50인 F(5)=21
...
N=70인 20x60인 문제에서 나와있는데로 F(7)=85
...
이것을 등차수열로 보고 식을 구해보면

이렇게 표현할 수 있습니다.

이제 원리를 알았으니 코드를 구현해봅시다.

 

여기서 입력받는 값을 10의 배수라고 하였지만 기타 10의 배수값이 아닌 경우를 따로 처리하라는 말이 없었으므로 임의로 "10의 배수로 입력하세요"라는 문구를 넣었다.

 

a_1값이 10일때는 1을 반환

a_2값이 20일때는 3을 반환해준다.(why? 초기값이 F(1)=1, F(2)=3이니까)

 

그 다음 재귀함수를 적용해서 피보나치 수열처럼 그 다음의 수열을 만들어나가게 한다.