BAEKJOON : 2156, 1932

No. 2156

1. Problem

2. My Solution

• 2차원 dp 풀이
• i 번째 포도주가 주어질 때, 3가지 경우로 나뉨
  - i 번째 포도주를 마시지 않는 경우 (OOX)
  - i 번째 포도주를 마시고 i-1 포도주는 마시지않고 i-2 포도주를 마시는 경우 (OXO)
  - i 번째 포도주를 마시고 i-1 포도주도 마시는 경우 (XOO)

• i 번째 포도주를 마시지 않는 경우를 dp[n-1][2] 로 구하면 안되고 dp[n-1] 중에서 max 값으로 해야함 (예를 들어 10개의 포도주가 있을 때, 10번째 포도주를 마시지 않고 무조건 8,9 포도주를 마시는 경우로 세팅하는 것보다 더 많이 마실 수 있는 경우가 존재할 수 있기 때문임)

import sys

n = int(sys.stdin.readline().rstrip())
juices = []

for _ in range(n):
    juices.append(int(sys.stdin.readline().rstrip()))

dp = [[0,0,0] for _ in range(n)]
dp[0][1] = dp[0][2] = juices[0]

for i in range(1,n):
    dp[i][0] = max(dp[i-1])
    dp[i][1] = dp[i-1][2] + juices[i]
    dp[i][2] = dp[i-1][0] + juices[i]

print(max(dp[n-1]))

3. Others' Solutions

• 1차원 dp 풀이
• i 번째 포도주가 주어질 때 3가지 경우로 나뉨
  - i 번째 포도주를 마시지 않는 경우
  - i 번째 포도주를 마시고 i-1 포도주는 마시지않고 i-2 포도주를 마시는 경우
  - i 번째 포도주를 마시고 i-1 포도주도 마시는 경우

• 3가지 경우의 수를 점화식으로 표현하면 아래와 같음
  - dp[i-1]
  - juices[i]+dp[i-2]
  - juices[i] + juices[i-1] + dp[i-3] (i-3까지 최대값에 더함)
  

# dp[i] -> i = n, n 일때 최대 포도주양 
                         
import sys

n = int(sys.stdin.readline().rstrip())
juices = [0]

for _ in range(n):
    juices.append(int(sys.stdin.readline().rstrip()))

dp = [0] * (n+1)
dp[1] = juices[1]

if n > 1:
    dp[2] = juices[1] + juices[2]

for i in range(3,n+1):
    temp = []
    temp.append(dp[i-1])
    temp.append(juices[i]+juices[i-1]+dp[i-3])
    temp.append(juices[i]+dp[i-2])

    dp[i] = max(temp)

print(dp[n])

4. Learned

• 최댓값 또는 최솟값이 어떤 경우로 나뉘는 지 판단할 수 있어야 함

---

No. 1932

1. Problem

2. My Solution

• 해당 level(층)에서 j 번째 요소로 끝나는 경우의 최대값을 각각 구함

# dp[i][j] -> i = n, j = 0 ~ level-1 (해당 층에서 j 번째 요소로 끝나는 경로의 최댓값) 
                         
import sys

n = int(sys.stdin.readline().rstrip())
dp = [[0]* n for _ in range(n+1)]

level = [[0]]
for _ in range(n):
    level.append(list(map(int,sys.stdin.readline().rstrip().split())))

dp[1][0] = level[1][0]

for i in range(2,n+1):
    for j in range(0,i):
        if j == 0:
            dp[i][j] = dp[i-1][j] + level[i][j]
        elif j == i-1:
            dp[i][j] = dp[i-1][j-1] + level[i][j]
        else:
            dp[i][j] = max(dp[i-1][j-1] + level[i][j], dp[i-1][j] + level[i][j])

print(max(dp[n]))