이코테 - DP 4문제

다이나믹 프로그래밍

DP (Dynamic Programming) 은 바텀업 방식에서 사용되며 결과 저장용 DP 테이블을 이용.

점화식을 도출할수 있는지 유의

• DP vs 메모제이션DP는 바텀업 방식으로 반복문을 통해 DP 테이블에 저장
• 메모제이션 방식은 탑다운 방식으로 재귀를 이용하여 한번 푼 문제 저장

1로 만들기

• 사이트/난이도: 이코테 / 1.5
• 코드

x = int(input())
dp = [0] * 30001

for i in range(2,x+1):
    dp[i] = dp[i-1] + 1
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2] + 1)
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3] + 1)
    if i % 5 == 0:
        dp[i] = min(dp[i], dp[i//5] + 1)

print(dp[x])

• 느낀점
  • 도식화하면 작은 값들을 가지는 함수들이 여러번 호출되므로 DP 문제
  • 피보나치 수열 처럼 점화식 구하기
  • DP 로 생각해야되는데 … ⇒ 함수가 호출되는 과정 도식화 해야지 생각 가능할듯

개미 전사

• 사이트/난이도: 이코테/ 2
• 코드

n = int(input())
k = list(map(int, input().split()))

dp = [0] * 100
dp[0] = k[0]
dp[1] = max(k[0], k[1])
for i in range(2, n):
    dp[i] = max(dp[i-1], dp[i-2] + k[i])

print(dp[n-1])

• 느낀점
  • 왼쪽부터 차례대로 식량창고 개수를 늘리면서, i번째에서 인접한 i-1번째 식량창고는 접근할수 없고, i-2번째는 i번째와 같이 접근할수 있으므로 점화식을 다음과 같이 유도하자.
  • $a_i = max(a_{i-1}, a_{i-2}+k_i)$ (k 는 i 번째 식량 개수)
  • 식량창고 개수가 증가할때마다를 유의하여 점화식을 세우자

바닥 공사

• 사이트/난이도: 이코테/ 1.5
• 코드

n = int(input())
dp = [0] * 1001

dp[1] = 1
dp[2] = 3

for i in range(3, n+1):
    dp[i] = (dp[i-1] + 2 * dp[i-2]) % 796796

print(dp[n])

• 느낀점
  • 바닥 타일이 1x2, 2x2, 2x1 밖에 없기 때문에 타일로 구성할수 있는 덮개의 최대는 2x2 까지 총 3개로 만들수 있다. 그 후의 덮개의 최대 개수 점화식은 다음과 같다.
  • $a_i = a_{i-1} + a_{i-2} * 2$

효율적인 화폐 구성

• 사이트/난이도: 이코테/ 2
• 코드

n, m = map(int, input().split())
coins = []
for _ in range(n):
    coins.append(int(input()))

INF = 100000
dp = [INF] * (m+1)
dp[0] = 0

for i in range(n):
    for j in range(coins[i], m+1):
        if dp[j-coins[i]] != INF:
            dp[j] = min(dp[j], dp[j-coins[i]] + 1)

if dp[m] != INF:
    print(dp[m])
else:
    print(-1)

• 느낀점
  • 그리디에서 푼 거스름돈 문제와 비슷하지만, 그때 거스름돈 문제는 화폐단위가 배수 관계라서 그리디로 가능했고, 여기서는 배수관계가 아니라 dp를 이용해서 모든경우를 구해야한다.
  • 금액 i를 만드는 최소화폐 개수에 대한 점화식은 다음과 같다.모든 화폐단위에 대해 적용시켜서 최소가 되는 화폐 개수를 구하여 dp에 저장하자.
  • $a_i = min(a_{i}, a_{i-k}+1)$ (k는 화폐단위)

총평

DP문제인지 아는게 중요한것 같다.
기본적으로 DP문제는 단순하게 완전탐색으로 접근할때 시간이 매우 오래걸리고, 패턴이 있어서 점화식을 세울수 있으면 DP 문제이다.