[알고리즘] 다이나믹 프로그래밍

중복되는 연산을 줄이자.

컴퓨터는 연산 속도에 한계가 있고 메모리 공간을 사용할 수 있는 데이터의 개수도 한정적이라는 점이 많은 제약을 발생시킨다. 그래서 우리는 연산 속도와 메모리 공간을 최대한으로 활용할 수 있는 효율적인 알고리즘을 작성해야 한다.

다만, 어떤 문제는 메모리 공간을 약간 더 사용하면 연산 속도를 비약적으로 증가시킬 수 있는 방법이 있는데 이중 대표적인 방법이 다이나믹 프로그래밍, 동적 계획법이다.

 

 

실전 문제 2. 1로 만들기

정수 X가 주어질 때 정수 X에 사용할 수 있는 연산은 다음과 같이 4가지이다.

  ① X가 5로 나누어떨어지면, 5로 나눈다.

  ② X가 3으로 나누어떨어지면, 3으로 나눈다.

  ③ X가 2로 나누어떨어지면, 2로 나눈다.

  ④ X에서 1을 뺀다.

정수 X가 주어졌을 때, 연산 4개를 적절히 사용해서 1을 만들려고 한다 . 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

▶ 입력 조건

 - 첫째 줄에 정수 X가 주어진다. (1≤X≤30,000)

 

▶ 출력 조건

 - 첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

 

# -*- coding: utf-8 -*-
x = int(input())

def solution(x) :
    num = 1
    count = 0
    
    while(num <= x) :
        
        if num == x :
            return count
        
        if 5*num <= x :
            num = num*5
            count+=1
            
        elif 3*num <= x:
            num = num*3
            count+=1
            
        elif 2*num <= 2:
            num = num*2
            count+=1
            
        else:
            num+=1
            count+=1

print(solution(x))

처음에는 이렇게 무식하게 짰습니다,, 다이나믹에 맞지 않다고 생각되어 책을 보고 다시 풀어 보았습니다.. 

 

# -*- coding: utf-8 -*-
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. 개미 전사

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

 

▶ 입력 조건

 - 첫째 줄에 식량창고의 개수 N이 주어진다. (3≤N≤500)

 - 둘째 줄에 공백으로 구분되어 각 식량창고에 저장된 식량의 개수 K가 주어진다. (0≤K≤1,000)

 

▶ 출력 조건

 - 첫째 줄에 개미 전사가 얻을 수 있는 식량의 최댓값을 출력하시오.

 

# -*- coding: utf-8 -*-
x = int(input())
array = list(map(int, input().split()))

d = [0]*100

d[0] = array[0]
d[1] = max(array[0], array[1])
for i in range(2, x) :
    d[i] = max(d[i-1], d[i-2]+array[i])
    
print(d[x-1])

 

 

실전 문제 4. 바닥 공사

가로의 길이가 N, 세로의 길이가 2인 직사각형 형태의 얇은 바닥이 있다. 태일이는 이 얇은 바닥을 1 × 2의 덮개, 2 × 1의 덮개, 2 × 2의 덮개를 이용해 채우고자 한다.

이때 바닥을 채우는 모든 경우의 수를 구하는 프로그램을 작성하시오. 예를 들어 2 × 3 크기의 바닥을 채우는 경우의 수는 5가지이다.

 

▶ 입력 조건

 - 첫째 줄에 N이 주어진다. (1≤N≤1,000)

 

▶ 출력 조건

 -  첫째 줄에 2 × N 크기의 바닥을 채우는 방법의 수를 796,796으로 나눈 나머지를 출력한다.

n = 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) % 796796

print(d[n])

 

 

실전 문제 5. 효율적인 화폐 구성

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

 

▶ 입력 조건

 - 첫째 줄에 N, M이 주어진다. (1≤N≤100, 1≤M≤10,000)

 - 이후 N개의 줄에는 각 화폐의 가치가 주어진다. 화폐 가치는 10,000보다 작거나 같은 자연수이다.

 

▶ 출력 조건

 - 첫째 줄에 M원을 만들기 위한 최소한의 화폐 개수를 출력한다.

 - 불가능할 때는 -1을 출력한다.

 

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

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])

(이해못함)