<PART 2> 다이나믹 프로그래밍 예제

<2> 1로 만들기
정수 x가 주어질 때 정수 x에 사용할 수 있는 연산은 다음과 같이 4가지입니다.
A. X가 5로 나누어떨어지면, 5로 나눈다.
B. X가 3으로 나누어떨어지면, 3으로 나눈다.
C. X가 2로 나누어떨어지면, 2로 나눈다.
D. X에서 1을 뺀다.

정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 합니다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
예를 들어 정수가 26이면
1. 26-1=25
2. 25/ 5 = 5
3. 5/ 5 =1
으로 3번의 연산이 최솟값입니다.
(1<=X<=30,000)

입력 예시)
26

출력 예시)
3

# 정수 입력받기
x = int(input())
 
# 빈 리스트 생성
d = [0] * 30001
 
# 입력받는 x값까지 바텀업 방식으로 구하기
for i in range(2,x+1):
    # 다음 값은 전에서 +1만 해주면 되는 값
    d[i] = d[i-1] + 1
 
    # %5가 된다면 %5연산횟수 1추가 해야함.
    if i % 5 == 0:
        d[i] = min(d[i],d[i//5]+1)
    # %3이 된다면 %3연산횟수 1추가 해야함.
    if i % 3 == 0:
        d[i] = min(d[i],d[i//3]+1)
    # %2가 된다면 %2연산횟수 1추가 해야함.
    if i % 2 == 0:
        d[i] = min(d[i],d[i//2]+1)
 
print(d[i])

풀이: 우선 빈리스트를 만들어줍니다. 그리고 난 뒤 for문을 사용해서 바텀업 방식으로 밑에서 위로 계산합니다. 매번 그 다음 값은 +1을 해주고 그 값이 //5, //3, //2가 했을 때 값이 0이라면 나눗셈 연산을 했으므로 +1을 해줍니다. 그리고 난 다음 단순히 +1해준 값이랑 나눗셈을 진행한 값 중에 최솟값을 고릅니다. 여기서 //5, //3, //2순서임에 유의합니다.

배운 점: 다이나믹 방식으로 문제를 풀어보는 것은 처음이였다. 바텀업 방식의 경우 for문을 사용하여 작은 수부터 d[i]를 구하고 그 다음 i에 대해서 점화식을 생각하면서 알고리즘을 짜야한다. 여기서는 min를 활용하는 것이 중요한데, d[i]자체를 떠올리는 것이 어려웠다. 이럴 때는 i가 1부터 x까지 천천히 그 과정을 생각해보면서 짜면 금방 익힐 것 같다.

<3> 개미전사
개미 전사는 부족한 식량을 충당하고자 메뚜기 마을의 식량창고를 몰래 공격하려고 한다. 이 식량 창고는 일직선으로 되어 있으며, 약탈하기 위해서는 최소한 한 칸 이상 떨어진 식량창고를 약탈해야 한다. 예를 들어 식량창고 4개가 다음과 같이 존재 한다.
{1,3,1,5}
그러면 두 번째, 네 번쨰 식량창고를 선택했을 때 최댓값이 8을 얻을 수 있다.
n개의 식량창고가 있을 때 얻을 수 있는 식량의 최댓값을 구하는 프로그램을 작성하시오
(3<=n<=100),(저장된 식량의 갯수 k, 0<=k<=1,000)

입력 예시)
4
1 3 1 5

출력 예시)
8

#식량창고 갯수받기
n = int(input())
#빈리스트 생성
d = [0]*100
#식량정보받기
k = list(map(int,input().split()))
d[0]=k[0]
d[1]=max(k[0],k[1])
for i in range(2,n):
    d[i] = max(d[i-1],d[i-2]+k[i])
print(d[n-1])

풀이: 인접할 수 있는 창고에는 갈 수 없는 것이 핵심입니다. 이를 이용해 풀면 입력 예시처럼 식량갯수가 1 3 1 5일때, 각각의 인덱스를 [0],[1],[2],[3]이라 할 수 있습니다. [3]까지 도달하는 최댓값은 [2]까지의 최댓값이거나 [1]까지의 최댓값+[3]의 값입니다. 이를 코드로 표현한 것입니다.

배운 점: 다이나믹 프로그래밍기법중에 바텀업 방식이 제일 나랑 맞는 것 같다. 차근차근히 처음 값부터 생각하면 쉽게 풀린다. 헷갈리는 점은 첫번째가 인덱스[0]이기 때문에 n-1,n,n+1중 뭐가 맞는지이다. 이럴 때는 [0]이 몇 번째인지만 생각하면 금방 해결되는 문제점이다.

<4> 바닥 공사
가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 이 얇은 바닥을 1X2의 덮개, 2X1의 덮개, 2X2의 덮개를 이용해 채우고자 한다. 이때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 2X3 크기의 바닥을 채우는 경우의 수는 5가지이다.
(1<=N<=1000),(바닥을 채우는 방법의 수를 796,796으로 나눈 나머지를 출력한다.)

입력 예시)
3

출력 예시)
5

#가로 길이 입력 받기
n = int(input())
#빈리스트 만들기
d= [0]*1000
 
#a2=a1+2a0 점화식 구현
d[1]=1
d[2]=3
for i in range(3,n+1):
    d[i] = (d[i-1]+2*d[i-2]) % 796796
 
print(d[n])

풀이: 위 문제의 점화식을 구하면 됩니다. An = An-1 + An-2 * 2이므로 앞서 구했던 문제들처럼 for문을 사용해서 바텀업방식대로 코드를 작성합니다.

배운 점: 문제를 보자마자 점화식으로 풀 생각을 하지 않았더라면 꽤나 고생했을 문제였을 것이라 생각한다. 앞으로 문제에 접근할 때 규칙이 있는 지 확인하는 눈이 필요할 것이다.

<5> 효율적인 화폐 구성
N가지 종류의 화폐가 있다. 이 화폐들의 개수를 최소한으로 이용해서 그 가치의 합이 M원이 되도록 하려고 한다.사용한 화폐의 구성은 같지만 순서만 다른 것은 같은 경우로 구분한다. 예를 들어 2원,3원 단위의 화폐가 있을 때는 15원을 만들기 위해 3원을 5개 사용하는 것이 가장 최소한의 화폐 개수이다.
(1<=N<=100, 1<=M<=10,000)
첫번째 줄에 N,M이 주어진다.
이후의 N개의 줄에는 각 화폐의 가치가 주어진다.
출력을 할 때 경우의 수 X를 출력하되, 불가능하면 -1을 출력한다.

입력 예시1)
2 15
2
3

출력 예시1)
5

입력 예시2)
3 4
3
5
7

출력 예시2)
-1

# n: 종류의 화폐, m: 가격의 합
n,m = map(int,input().split())
 
# 빈리스트 생성
d = [10001] * (m+1)
# 화폐 가격 받기
cost = []
d[0] = 0
for i in range(n):
    cost.append(int(input()))
 
for i in range(n):
    for j in range(cost[i],m+1):
        # a5=a(5-3)+1와 a5를 비교, a(5-3)가 필요해야 비교할 수 있으므로 있는지 확인
        if d[j-cost[i]] != 10001: #비교할 값이 있다면
            d[j] = min(d[j], d[j-cost[i]]+1) #그 값에서 +1만 하면 됨
 
if cost[i] == 10001: #만드는 방법이 없는 경우
    print(-1)
else:
    print(d[m])

풀이: 최솟값을 구해야하므로 화폐가치 1로 10000번이 나올 수 있는 값이 최대값이므로 빈 리스트를 10001로 채운다. (필자는 바로 -1을 넣었는데 나중에 min을 사용할 것이므로 잘못 이해했었다.) 그 후 만약에 화폐가치가 [2,3,5]일 때 화폐가치이고, a5인 경우를 생각해봅시다. a5은 a(5-3) + 1입니다. 여기서 a(5-3)의 값이 이미 존재해야만 a5를 구할 수 있으며, 나중에 화폐가치가 5일 때에서 a5가 구해지게 됩니다. 그러므로 min으로 자기자신의 값과 a(5-3)+1값 이 2개를 비교해야 합니다.

배운 점: 풀이없이 풀 때는 2,3,5를 각각 넣어주고, min을 사용해야 하는데 어떻게 코드로 구현할지가 막막했다. 그래서 풀이를 보니깐 실제로 d[j]값을 넣을 때 조건문이 될 때만 넣었다. 바로 이해가 안가서 천천히 다시 보았다. 화폐가치가 2일 때 d[2] = min(d[2],d[0]+1)였고 d[2]는 아직 10001이므로 d[2] = 0+1인 1이 들어갔다. 이걸 보고나니깐 그 다음 수순도 이해가 가기 시작했다. 이 문제는 나에게 많이 어려웠다. 점화식으로 간단하게 표현할 수 없지만 바텀업 방식으로 풀어야 하는 문제이다. 이런 유형을 더 접해봐야겠다.