평범한 대학생의 이것저것

문제를 봤는데 어떻게 풀어야 될 지 감이 안와서 보니 과거 값을 이용하여 미래 값을 도출해내는 방식이 있어 이런 접근 방식에 익숙해져야할 것 같다.

코드 (RGB 거리)

import sys

N = int(sys.stdin.readline())
cost = []

for i in range(N):
    cost.append(list(map(int, sys.stdin.readline().split())))

for i in range(1, N):
    cost[i][0] = min(cost[i-1][1],cost[i-1][2]) + cost[i][0]
    cost[i][1] = min(cost[i-1][0],cost[i-1][2]) + cost[i][1]
    cost[i][2] = min(cost[i-1][0],cost[i-1][1]) + cost[i][2]

print(min(cost[N-1][0],cost[N-1][1],cost[N-1][2]))

cost 배열은 2차원 배열로 되어있으며 각 집마다 색을 칠하는 가격이 저장되어있다.
반복자 i는 집을 칠할 색 하나를 골랐을 때 그 이전 집을 두 색중 하나를 골라 칠하고 그 비용의 합을 해당 집 위치의 인덱스에 저장하는 식으로 진행된다.

코드 (포도주 시식)

import sys

n = int(sys.stdin.readline())
Grape = []
res = []

for i in range(n):
    Grape.append(int(sys.stdin.readline()))
res.append(Grape[0])

if n > 1:
    res.append(Grape[0] + Grape[1])
    if n > 2:
        res.append(max(Grape[0] + Grape[1], Grape[0] + Grape[2], Grape[1] + Grape[2]))

for i in range(3,n):
    res.append(max(res[i-1], res[i-2] + Grape[i], res[i-3] + Grape[i-1] + Grape[i]))

print(res[n-1])

앞서 RGB 거리와 비슷한 유형의 문제라서 같이 정리해두었다.
포도주 문제는 이전 인덱스값까지의 최대 양을 저장해두어 다음 어떤 와인을 골라 마셔야 최대의 양을 마실 수 있는 지 찾을 수 있다.
경우의 수는 세가지가 있다.

1. 현재 잔과 이전 잔을 마셨을 때

이 경우 전전 잔을 마시지 않았어야 한다.
i, i-1의 값의 합을 dp[i-3]에 더한다.

2. 현재 잔과 전전 잔을 마셨을 때

i값을 dp[i-2]에 더한다.

3. 현재 잔을 마시지 않았을 때

dp[i-1]의 값을 가져온다.

각 경우의 수를 따져 최대로 먹을 수 있는 경우를 선택하여 값을 추가한다.

댓글남기기

참고