문제

SWEA 4869. 종이붙이기
https://swexpertacademy.com/main/talk/solvingClub/problemView.do?solveclubId=AYWpDVe6hEgDFAVt&contestProbId=AYZJ8ts6dlEDFAVw&probBoxId=AYZJ8Nuadg4DFAVw&type=USER&problemBoxTitle=230214_%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4&problemBoxCnt=5

Check point

📌 동적 계획 (DP) / Dynamic Programming

💡 DP란?

• 입력 크기가 작은 부분 문제들을 모두 해결하여 그 해들을 이용하여 보다 큰 크기의 부분 문제들을 해결하고 최종적으로 원래 주어진 입력의 문제를 해결하는 알고리즘
  
  
• 재귀와 방식이 매우 유사하나 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산이 될 수 있는 재귀의 문제를 해결하기 위해 DP를 사용한다.
  => 즉, 분할된 하위 문제가 동일한 반복이 일어나면 DP를 사용한다.

💡 DP의 구현 방식

• recursive 방식 ( 재귀 ) : fib1()
• iterative 방식 ( 반복 ) : fib2()
  
  
• memoization을 재귀적 구조에 사용하는 것보다 반복적 구조로 구현한 것이 성능면에서 효율적
  재귀적 구조는 내부에 시스템 호출 스택을 사용하는 오버헤드가 발생하기 때문

📌 풀이 접근 방법

• 20 x 30 직사각형을 빈틈없이 붙이는 총 5가지 방법과 20 x 10 , 20 x 20 직사각형을 빈틈없이 붙이는 1 , 3 가지 방법과의 관계성을 파악한다.

코드

python

T = int(input())
for test_case in range(1, T + 1):
    N = int(input())
    arr = [0] * (N + 1)
 
    arr[10] = 1
    arr[20] = 3
    for i in range(30, N + 1, 10):
        arr[i] = 2 * arr[i-20] + arr[i-10]
    # print(arr)
    print(f'#{test_case} {arr[N]}')