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

문제

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

   

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

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

 

 

 

 

내 생각

점화식,, 하,, 점화식을 생각해내는 연습이 필요하다 ! 관련된 문제를 많이 풀어봐야겠음!

아무튼 처음에는 그림을 그렸다. 주어지는 N은 10단위로 주어지니 //10을 한다 생각하고 1일 때, 2일 때, 적어도 4일 때까지 그렸다. 그러고 얻어낸 점화식

f(N) =  f(N-1) + 2 * f(N-2)

20 x 10과 20 x 20을 이용해야 한다. 즉 n-1 에는 세로로 작은 사각형 쌓기, 그리고 n-2에는 가로로 작은 사각형 두 개 쌓기 또는 큰 사각형 쌓기 두 방법이 있으니 *2 로 표현할 수 있다.

 

재귀로 먼저 구현했고, 다음으로 DP로 구현했다.  그리고 DP로 구현한 후에 전형적인 DP문제라는 생각을 하였다 ! 슬슬 감이 잡히는듯!

 

 

 

 

 

내 코드 

1. 재귀

 

def solution(n):
	if n == 1:
		return 1
	elif n == 2:
		return 3
	return solution(n-1) + solution(n-2) * 2
    
T = int(input())

for test_case in range(1, T+1):
    N = int(input())
    print("#{} {}".format(test_case, solution(N // 10)))

 

2. DP

T = int(input())

for test_case in range(1, T+1):
    N = int(input()) // 10
    memo = [1, 3]
    if N > 2:
        for i in range(2, N):
        	memo.append(memo[i - 1] + memo[i - 2] * 2)
    print("#{} {}".format(test_case, memo[N - 1]))

 

 

 

 

 

* DP는 Memoization(메모이제이션)과 함께 사용될 때 효과적이다.

메모이제이션 : 함수의 결과를 저장하고, 이미 계산된 결과가 필요한 경우 저장된 결과를 반환한다.