참고자료 : 이것이 코딩 테스트다 (나동빈 저)

1. 중복되는 연산을 줄이자

1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

• 메모이제이션 : DP를 구현하는 방법 중 하나로, 한 번 구현한 결과를 메모리에 저장해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법이다. -> 탑다운에서 사용 (캐싱이라고도 한다.)
• Top-Down : 재귀함수를 이용하여 DP 코드 작성
• Bottom-Ip : 반복문을 이용하여 소스코드 작성 (DP 테이블 사용) => 권장
• DP 문제를 푸는 첫 단계는 DP 유형인지 파악하는 것이다.

2. 1로 만들기

난이도 중하

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1. X가 5로 나누어 떨어지면, 5로 나눈다.
2. X가 3으로 나누어 떨어지면, 3으로 나눈다.
3. X가 2로 나누어 떨어지면, 2로 나눈다.
4. 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

해설

이 문제는 잘 알려진 DP 문제이다. 점화식을 토대로 코드를 구현하자.

코드

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

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

print(d[x])

3. 개미 전사

난이도 중

문제

메뚜기 마을에는 여러 개의 식량창고가 있는데 각 창고는 일직선으로 이어져 있다. 식량창고에는 정해진 수의 식량을 저장하고 있으며 개미 전사는 식량창고를 선택적으로 약탈하여 식량을 빼앗을 예정이다. 이때 메뚜기 정찰병들은 일직선상에 존재하는 식량창고 중에서 서로 인접한 식량창고가 공격받으로 바로 알아챌 수 있다. 따라서 개미 전사가 정찰병에게 들키지 않기 위해서는 최소한 한 칸이상 떨어진 창고를 약탈해야 한다. 식량창고 N개에 대한 정보가 주어졌을 때 얻을 수 있는 식량의 최댓값을 구하시오.

해설

a[i] = max(a[i-1], a[i-2]+k[i])

위 점화식을 사용한다.

코드

x = int(input())
arr = list(map(int, input().split()))
d = [0] * 100
d[0] = array[0]
d[1] = max(array[0], array[1])

for i in range(2, n):
    d[i] = max(d[i-1], d[i-2]+arr[i])

print(d[n-1])

4. 바닥 공사

난이도 중하

문제

가로의 길이가 N, 세로 길이가 2인 직사각형의 바닥이 있다. 이 얇은 바닥을 1* 2 덮개, 2* 1 덮개, 2*2 덥개를 이용해 채우고자 한다. 바닥을 채우는 경우의 수를 모두 구하시오.

해설

이 문제도 DP 예제에서 빠질 수 없는 타일링 문제 유형이다. 왼쪽부터 N-2 미만의 길이는 고려할 필요가 없다.

a[i] = a[i-1] + a[i-2] * 2

코드

x = int(input())
d = [0] * 1001
d[1] = 1
d[2] = 3

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

print(d[n])

5. 효율적인 화폐 구성

문제

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

해설

그리디랑 비슷하지만 큰 화폐가 작은 화폐의 배수가 아니라는 점이 다르다. 그렇기 때문에 DP를 사용해야 한다.

코드

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

d = [10001] * (m+1)
d[0] = 0

for i in range(n):
    for j in range(array[i], m+1):
        if d[j-array[i]] != 10001:
            d[j] = min(d[j], d[j-array[i]]+1)

if d[m] == 10001:
    print(-1)
else : print(d[m])