[이것이 코딩테스트다] 19일차 - DP 예제풀이 | 효율적인 화폐구성, 바닥 공사

본문은 [이것이 취업을 위한 코딩테스트다 - 나동빈] 책을 공부하고 작성한 글입니다.

Chapter 8 다이나믹 프로그래밍

오늘 풀이한 문제 - 다이나믹 프로그래밍 예제

[이코테 226p] 효율적인 화폐구성

문제

N가지 종류의 화폐가 있을 때, 이 화폐들의 개수를 최소한으로 이용해 그 가치의 합이 M원이 되도록 하여라.각 화폐는 몇 개라도 사용할 수 있고, 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다.

 

접근 방법

만약 m = 7, 주어진 화폐가 2,3이라고 하면

7 -> 4+3 -> 2+2+3 이런식으로 쪼개질 수 있다 = DP로 풀이할 수 있다

 

화폐 사용 횟수 저장 리스트 = a (큰값으로 초기화)

m에서 각 화폐를 따지면서 업데이트 할 수 있는 최솟값을 a에 업데이트 한다

 

점화식은 다음과 같다

 

소스 코드

n,m = map(int, input().split())
cash = [int(input()) for _ in range(n)]
a = [10001] * (m+1)
a[0]= 0 ## 0은 만들수없기때문에 0으로 초기화하고 연산에 사용

for ca in cash: ## 각 화폐 하나씩 돌며 확인
    for want in range(ca, m+1): ## 가지고 있는 화폐 이전의 값은 만들수없으므로 확인 X
        if a[want-ca] != 10001: ## 현재위치에서 cash를 빼어 연산할 수 있다면
            a[want] = min(a[want-ca]+1, a[want]) ## 현재 값 or 이전 연산값+1 보다 작은값
            
if a[m] == 10001:
    print (-1)
else:
    print (a[m])

 

[이코테 223p] 바닥공사

문제

가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이가 이 바닥을 1x2, 2x1, 2x2 덮개를 이용해 채울 때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성해라.

단, 방법의 수를 796,796으로 나눈 나머지를 출력해야한다.

 

접근 방법

경우의 수라는 조건을 까먹고 점화식을 세우는데 시간이 걸렸다 ,, ^^ 

이전까지의 경우의 수에서,

내 바로 앞 칸이 비어있다면 2x1 타일만 사용할 수 있기때문에 이전 경우의 수를 그대로 사용한다

내 바로 앞앞칸까지 비어있다면 1x2 타일 두개, 2x2 타일 하나로 바닥을 채울수 있어 이전 경우의 수*2를 더한다

따라서 점화식은 다음과 같다

소스 코드

n = int(input())
dp = [0]*(n+1)

dp[1] = 1
dp[2] = 3 ## 앞에 아무것도 없을때 2*(1*2) , 2*2 + 앞에 타일이 있을때 2*1

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

print (dp[n])

 

점화식을 세우는게 아직 익숙하지 않은데 재미있는것 같기도 하다!

DP 문제를 풀 때 왼쪽으로 부터 차례차례 하나씩 해나간다고 생각하고 도식화한 다음,

N번째 기준으로 몇 번째 직전까지는 고려하지 않아도 되는지를 먼저 생각해보기