06-5. 다이나믹 프로그래밍 문제풀이

📝문제1. 백준 9095번(1, 2, 3 더하기)

- 문제

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

- 코드💻

for _ in range(int(input())):
    n = int(input())
    dp = [0]*12
    dp[0] = dp[1] = 1
    dp[2] = 2
    for i in range(3, n+1):
        dp[i] = dp[i-1] + dp[i-2] + dp[i-3]
    print(dp[n])

- 해설📖

---

📝문제2. 백준 1149번(RGB거리)

- 문제

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

- 코드💻

import sys
input = sys.stdin.readline 
n = int(input())

array = [[0 for _ in range(3)] for __ in range(n)]  # 3xn 배열
table = [[0 for _ in range(3)] for __ in range(n)]  # 3xn 배열

for i in range(n):
    array[i][0], array[i][1], array[i][2] = list(map(int, input().split()))
table[0] = array[0]

for i in range(n):
    table[i][0] = min(table[i - 1][1], table[i - 1][2]) + array[i][0]
    table[i][1] = min(table[i - 1][0], table[i - 1][2]) + array[i][1]
    table[i][2] = min(table[i - 1][0], table[i - 1][1]) + array[i][2]
min_cost = min(table[n - 1][0], table[n - 1][1], table[n - 1][2])

print(min_cost)

- 해설📖

참고 블로그 : https://cotak.tistory.com/11
https://seungjuitmemo.tistory.com/29

---

📝문제3. 백준 2156번(포도주 시식)

- 문제

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

- 코드💻

n = int(input())
wine_list = [int(input()) for x in range(n)]

dp = [0]
dp.append(wine_list[0])
if(n > 1):
    dp.append(wine_list[0] + wine_list[1])

# 연속 3잔을 마시지 않아야 하므로
# 1 : 이번 포도주를 먹고 이전 포도주를 먹지 않은 경우
# 2 : 이번 포도주를 먹고 이전 포도주도 먹은 경우
# 3 : 이번 포도주를 먹지 않아야 하는 경우
# 위 세가지 경우를 고려하여 max

for i in range(3, n + 1):
    # wine_list는 0부터 시작하므로 i - 1로 해준다.
    case_1 = wine_list[i - 1] + dp[i - 2]
    case_2 = wine_list[i - 1] + wine_list[i - 2] + dp[i - 3]
    case_3 = dp[i - 1]
    max_value = max(case_1, case_2, case_3)
    
    dp.append(max_value)
    
print(dp[n])

- 해설📖

참고 블로그 : https://hwiyong.tistory.com/257