[WEEK 04] 알고리즘 - 동적 프로그래밍 문제풀이 2

1463. 1로 만들기

https://www.acmicpc.net/problem/1463

그리디 알고리즘을 이용해 간단히 해결할 수 있는 문제처럼 보일 수 있으나 자세히 보면 그렇지 않고 DP를 이용해 해결하는 문제이다. 최적의 방법을 반례없이 적용 가능한 경우에 사용 가능하나, 2와 3은 배수 관계가 아니기 때문에 큰 수로 나누는 방법이 계산 횟수의 최소값을 보장하지 않는다.

import sys

sys.stdin = open("1463_1로 만들기.txt", "r")
input = sys.stdin.readline

N = int(input())

dp = [0 for _ in range(N + 1)]

# 2부터 N까지의 수를 탐색
for i in range(2, N + 1):
    # dp[i]는 i를 1로 만들 수 있는 최소 연산 횟수
    dp[i] = dp[i - 1] + 1
    # if만 이용해야 세 연산을 다 거칠 수 있기 때문에 elif나 else를 사용하면 안된다.
    if i % 2 == 0:
        # 1을 더하는 이유는 DP 테이블은 결과가 아닌 계산 횟수를 저장하기 때문이다.
        dp[i] = min(dp[i], dp[i // 2] + 1)
    if i % 3 == 0:
        # dp[i]에는 1을 더하지 않는 이유는 이미 1을 뺄 때 1을 더해줬기 때문이다.
        dp[i] = min(dp[i], dp[i // 3] + 1)

print(dp[N])

---

1149. RGB거리

https://www.acmicpc.net/problem/1149

DP 테이블을 사용하진 않았지만 DP에 대한 이해를 기르는 데에 도움이 된 문제. i번째 집 이전까지 색칠하는 데에 사용한 총 비용의 최소값을 배열의 행마다 갱신하여 N번째 집까지 색칠하는 데에 필요한 최소 비용을 구할 수 있다.

import sys

sys.stdin = open("1149_RGB거리.txt", "r")
input = sys.stdin.readline

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]

# 배열의 i번째 행을 (i - 1)번째 집까지 색칠하는 데에 사용된 최저 비용의 합을 더하여 갱신
for i in range(1, N):
    arr[i][0] += min(arr[i - 1][1], arr[i - 1][2])
    arr[i][1] += min(arr[i - 1][0], arr[i - 1][2])
    arr[i][2] += min(arr[i - 1][0], arr[i - 1][1])

print(min(arr[N - 1]))

17404. RGB거리 2

https://www.acmicpc.net/problem/17404

한 가지 조건이 문제에 추가되면서 1149. RGB거리와 완전히 다른 문제가 되었다. 첫번째 집의 색깔을 세 가지 경우의 수로 나누어 시작하는 색깔이 아닌 색깔은 색칠하는 비용을 INF로 설정하였다. 또한 마지막 N번째 집의 색깔이 첫번째 집의 색깔과 다른 경우에만 결과값 result에 저장하도록 하였다.

import sys

sys.stdin = open("17404_RGB거리 2.txt", "r")
input = sys.stdin.readline

N = int(input())
arr = [list(map(int, input().split())) for _ in range(N)]
# DP 테이블은 해당 집까지 색칠하는 데에 사용한 총 비용의 최소값을 저장
dp = [[0 for _ in range(3)] for _ in range(N)]

# 최소값을 구하는 문제이기 때문에 result의 초기값을 INF로 설정
result = float('inf')

for i in range(3):
    # 첫번째 집의 색깔을 색칠하는 세 가지 경우의 수
    for j in range(3):
        if j == i:
            dp[0][j] = arr[0][j]
        else:
            # 색칠을 시작하는 색깔이 아닌 경우 색칠하는 비용을 INF로 설정
            dp[0][j] = float('inf')
    
    for k in range(1, N):
        # k번째 집을 색칠하는 비용을 이전까지의 집들을 색칠하는 데에 사용한 총 비용의 최소합에 더한다.
        dp[k][0] = min(dp[k - 1][1], dp[k - 1][2]) + arr[k][0]
        dp[k][1] = min(dp[k - 1][0], dp[k - 1][2]) + arr[k][1]
        dp[k][2] = min(dp[k - 1][0], dp[k - 1][1]) + arr[k][2]
    
    for l in range(3):
        # N번째 집의 색깔이 첫번째 집의 색깔과 다르면 최소값을 result에 저장
        if l != i:
            result = min(result, dp[-1][l])

print(result)

---

1912. 연속합

https://www.acmicpc.net/problem/1912

DP 테이블에는 주어진 수열의 i번째 원소까지의 부분수열의 최대합을 저장한다.

import sys

sys.stdin = open("1912_연속합.txt", "r")
input = sys.stdin.readline

N = int(input())
arr = list(map(int, input().split()))

dp = [0 for _ in range(N)]

for i in range(N):
    # dp[i]는 arr[i]까지의 부분수열의 최대합
    dp[i] = max(arr[i], dp[i - 1] + arr[i])

print(max(dp))

---

2839. 설탕 배달

https://www.acmicpc.net/problem/2839

설탕 봉지의 수를 최소화하기 위해선 5킬로그램 봉지를 최대한 많이 사용해야 하므로 N을 5로 나눌 수 있는지 확인한다. N을 5로 나누어 떨어진다면 봉지의 수에 5로 나눈 몫만큼 더한다. 5로 나누어 떨어지지 않으면 3을 한번씩 빼고 봉지를 1개씩 더하는 과정을 반복한다. N에서 3을 뺀 값이 3보다 작고 0이 아니라면 3킬로그램과 5킬로그램의 봉지로 포장할 수 없다는 뜻으로 -1을 출력한다.

import sys

sys.stdin = open("2839_설탕 배달.txt", "r")
input = sys.stdin.readline

N = int(input())

result = 0

while True:
    # 5로 나눈 몫을 결과값에 더한다.
    if N % 5 == 0:
        result += (N // 5)
        print(result)
        break
    
    # 5로 나누어지지 않으면 3을 빼고 결과값을 1 더한다.
    N -= 3
    result += 1
    
    # 3보다 작고 0이 아니면 -1을 출력
    if 0 < N < 3:
        print(-1)
        break

---