Dynamic Programming 문제풀이

피보나치 수열 문제나 간단한 점화식을 세우는 쉬운 문제는 풀이가 가능하지만, 배열을 써야 하거나 추가적인 생각을 요하는 문제는 아직 많이 연습이 필요해 보인다...

포도주 시식

2 초

128 MB

128601

43844

31640

32.616%

 

문제

효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규칙이 있다.

1. 포도주 잔을 선택하면 그 잔에 들어있는 포도주는 모두 마셔야 하고, 마신 후에는 원래 위치에 다시 놓아야 한다.
2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.

효주는 될 수 있는 대로 많은 양의 포도주를 맛보기 위해서 어떤 포도주 잔을 선택해야 할지 고민하고 있다. 1부터 n까지의 번호가 붙어 있는 n개의 포도주 잔이 순서대로 테이블 위에 놓여 있고, 각 포도주 잔에 들어있는 포도주의 양이 주어졌을 때, 효주를 도와 가장 많은 양의 포도주를 마실 수 있도록 하는 프로그램을 작성하시오. 

예를 들어 6개의 포도주 잔이 있고, 각각의 잔에 순서대로 6, 10, 13, 9, 8, 1 만큼의 포도주가 들어 있을 때, 첫 번째, 두 번째, 네 번째, 다섯 번째 포도주 잔을 선택하면 총 포도주 양이 33으로 최대로 마실 수 있다.

입력

첫째 줄에 포도주 잔의 개수 n이 주어진다. (1 ≤ n ≤ 10,000) 둘째 줄부터 n+1번째 줄까지 포도주 잔에 들어있는 포도주의 양이 순서대로 주어진다. 포도주의 양은 1,000 이하의 음이 아닌 정수이다.

출력

첫째 줄에 최대로 마실 수 있는 포도주의 양을 출력한다.

import sys
input = sys.stdin.readline

n = int(input())
grape = [0]*10000
for i in range(n):
    grape[i] = int(input())
    
d = [0]*10000
d[0] = grape[0]
d[1] = grape[0] + grape[1]
d[2] = max(grape[2] + grape[0], grape[2] + grape[1], d[1])

for i in range(3, n):
    d[i] = max(grape[i] + d[i-2], grape[i] + grape[i-1] + d[i-3], d[i-1])

print(max(d))

이건 쉬운 점화식 유형이라고 생각할 수 있지만, 아직 리스트를 생성하고 인덱스 개념을 활용하여 값을 도출하는 컴퓨팅 계산에 대한 이해도가 떨어져 보인다... ㅜ 더 열심히 하자!

본인이 가장 어려워 하는 DP 유형 문제는 다음과 같다.

기타리스트 

2 초

128 MB

19356

7330

5715

37.234%

문제

Day Of Mourning의 기타리스트 강토는 다가오는 공연에서 연주할 N개의 곡을 연주하고 있다. 지금까지 공연과는 다른 공연을 보여주기 위해서 이번 공연에서는 매번 곡이 시작하기 전에 볼륨을 바꾸고 연주하려고 한다.

먼저, 공연이 시작하기 전에 각각의 곡이 시작하기 전에 바꿀 수 있는 볼륨의 리스트를 만들었다. 이 리스트를 V라고 했을 때, V[i]는 i번째 곡을 연주하기 전에 바꿀 수 있는 볼륨을 의미한다. 항상 리스트에 적힌 차이로만 볼륨을 바꿀 수 있다. 즉, 현재 볼륨이 P이고 지금 i번째 곡을 연주하기 전이라면, i번 곡은 P+V[i]나 P-V[i] 로 연주해야 한다. 하지만, 0보다 작은 값으로 볼륨을 바꾸거나, M보다 큰 값으로 볼륨을 바꿀 수 없다.

곡의 개수 N과 시작 볼륨 S, 그리고 M이 주어졌을 때, 마지막 곡을 연주할 수 있는 볼륨 중 최댓값을 구하는 프로그램을 작성하시오. 모든 곡은 리스트에 적힌 순서대로 연주해야 한다.

 

입력

첫째 줄에 N, S, M이 주어진다. (1 ≤ N ≤ 50, 1 ≤ M ≤ 1,000, 0 ≤ S ≤ M) 둘째 줄에는 각 곡이 시작하기 전에 줄 수 있는 볼륨의 차이가 주어진다. 이 값은 1보다 크거나 같고, M보다 작거나 같다.

출력

첫째 줄에 가능한 마지막 곡의 볼륨 중 최댓값을 출력한다. 만약 마지막 곡을 연주할 수 없다면 (중간에 볼륨 조절을 할 수 없다면) -1을 출력한다.

n, s, m = map(int, input().split())

v = list(map(int, input().split()))

d = [[0] * (m+1) for _ in range(n+1)]  # (m+1)*(n+1) 크기의 0 배열 생성
d[0][s] = 1 # 처음 주어진 volume 설정

for i in range(n):
    for j in range(m+1):
        if d[i][j] == 1: # 가능한 시나리오 표시 == 1
            if j + v[i] <= m:
                d[i+1][j+v[i]] = 1
            if j - v[i] >= 0:
                d[i+1][j-v[i]] = 1

# 답안 도출
ans = -1
for i in range(m, -1, -1):
    if d[n][i] == 1:
        ans = i
        break
print(ans)

코드를 뜯어보면 이해 가지만, 정작 풀 때는 이러한 배열로 도출하려는 생각이 안난다...

참 대단한 사람이 많은 것 같다