[Python] SWEA 4869 종이 붙이기

SWEA SW Expert Academy 4869번 종이 붙이기 문제는 20xN 크기의 직사각형을 테이프로 표시하고, 안에 10x20, 20x20인 종이를 빈틈없이 붙이는 모든 경우를 찾을 때, 몇 개의 테이프 영역이 필요한지 계산하는 문제로 동적 계획법 DP 알고리즘에 관한 문제다.

 

SW Expert Academy 4869번 종이 붙이기 문제 정보

알고리즘 분류

- DP Dynamic Programming 동적 계획법 알고리즘, memoization 메모이제이션

난이도

- D2

 

DP Dynamic Programming 동적 계획법 알고리즘과 예제

DP Dynamic Programming 동적 계획법 알고리즘과 예제

 

종이 붙이기 문제 요약

• 가로 x 세로 길이가 10x20, 20x20인 직사각형 종이가 잔뜩 있다.
• 20xN 크기의 직사각형을 테이프로 표시하고, 이 안에 준비한 종이를 빈틈없이 붙이는 모든 경우를 찾으려면 테이프로 만든 표시한 영역을 몇 개나 만들어야 되는지 계산한다.
• N은 10의 배수이고, 범위는 10 이상 300 이하이다.
• 직사각형 종이가 모자라는 경우는 없다.

문제 풀이 과정

1. f(n)에서 n을 (테이프 영역의 너비//10), f(n)을 종이를 붙이는 경우의 수라고 한다.
2. 점화식을 f(n) = f(n-1) + f(n-2) * 2, f(0) = f(1) = 1로 표현할 수 있다.
   • 재귀 함수를 호출하면 엄청난 중복 호출이 존재하여 실행 속도와 성능을 저하시키므로
   • DP 알고리즘과 memoization을 사용하여 이 전 계산 값을 저장하여 다시 계산하지 않고 재 사용할 수 있게 구현한다.
3. n에 따른 f(n)의 값을 저장해 놓고 필요할 때 사용하여 n의 점화식을 계산한다.
4. memoization에 저장된 마지막 값을 리턴한다.
5. 테스트 케이스 번호, 필요한 테이프 영역의 수를 출력한다.

 

코드 및 설명

• memoization [] - N에 대한 attach_paper(N)의 값들을 저장해놓은 리스트

def attach_paper(N):
    n = N // 10
    memoization = [0] * (n+1)
    memoization[0] = memoization[1] = 1
    # DP
    for i in range(2, n+1):
        memoization[i] = memoization[i-1] + memoization[i-2] * 2

    return memoization[-1]

for t in range(int(input())):
    print("#%d %d" % (t + 1, attach_paper(int(input()))))

---

SW Expert Academy SWEA 4869번 종이 붙이기 문제는 DP; Dynamic Programming 동적 계획법 알고리즘과 DP의 핵심 기술인 memoization 활용 문제이며 파이썬을 사용하였다. 재귀 함수 호출보다 실행 속도나 성능 면에서 뛰어나다. 난이도는 D2지만 알고리즘을 구현하는데 조금 어려움이 있었다.