EDOC 2024-1 4회차 정모 (동적 계획법 알아보기 1)

A. 돌 게임 (백준 9655번)

 

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

 

#python

import sys
input = sys.stdin.readline

n = int(input())

if n % 2 == 0:
    print("CY")
else:
    print("SK")

규칙을 찾으려고 몇 개 적어봤는데, 한 8까지 적어보니까 그냥 n이 홀수인 경우에는 상근이가 이기고 n이 짝수인 경우에는 창영이가 이기는 것 같은데..?? 라는 생각이 들었다. 뭔가 아닐 것 같지만 일단 한번 제출해봤는데 이왜진... (정답)

 

---

 

B. 수열 (백준 2491번)

 

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

 

#python

import sys
input = sys.stdin.readline

n = int(input())
data = list(map(int, input().split()))
dif = [0 for _ in range(n - 1)]

for i in range(n - 1):
    dif[i] = data[i + 1] - data[i]

maxP = tmp = 0
for i in range(n-1):
    if dif[i] >= 0:
        tmp += 1
        if tmp > maxP:
            maxP = tmp
    else:
        tmp = 0

maxM = tmp = 0
for i in range(n-1):
    if dif[i] <= 0:
        tmp += 1
        if tmp > maxM:
            maxM = tmp
    else:
        tmp = 0

print(max(maxP, maxM) + 1)

우선 입력으로 들어오는 수들은 data 배열에 넣어주고, data[n+1] - data[n] 값이 dif[n]에 들어가도록 차 dif 배열를 만들었다. 그리고 증가하는 수열 중 최대 길이와 감소하는 수열 중 최대 길이를 각각 구해 둘 중 더 큰 값을 출력하도록 했다. (정답)

 

---

 

C. 파도반 수열 (백준 9461번)

 

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

 

#python

import sys
input = sys.stdin.readline

p = [0 for _ in range(101)]

p[1] = p[2] = p[3] = 1
p[4] = p[5] = 2
for i in range(6, 101):
    p[i] = p[i - 1] + p[i - 5]

t = int(input())
for _ in range(t):
    n = int(input())
    print(p[n])

그림을 잘 들여다보면 각 변은 짧은 변과 긴 변이 합쳐진 것이며, 그 중 짧은 변은 5번 이전의 변이며 긴 변은 1번 이전의 변이다. 즉 점화식은 p[n] = p[n-1] + p[n-5] 이 된다. (정답)

 

---

 

D. 포도주 시식 (백준 2156번)

 

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

 

#python

import sys
input = sys.stdin.readline

n = int(input())
data = [0 for _ in range(n + 1)]
dp = [0 for _ in range(n + 1)]

for i in range(1, n + 1):
    data[i] = int(input())

# 점화식 dp[n] = max(dp[n - 1], dp[n - 2] + data[n],
#                   dp[n - 3] + data[n - 1] + data[n])

dp[1] = data[1]

if n > 1:
    dp[2] = data[1] + data[2]
    
for i in range(3, n + 1):
    dp[i] = max(dp[i - 1], dp[i - 2] + data[i],
                dp[i - 3] + data[i - 1] + data[i])

print(dp[n])

 

data[n] : n번째 포도주 잔에 들어있는 포도주의 양

dp[n] : n번째 포도주 잔까지 마실 수 있다고 가정할 때, 최대로 마실 수 있는 포도주의 양

 

n번째 포도주 잔까지의 최대로 마실 수 있는 포도주의 양을 계산하려면 세가지 경우를 고려해야 한다. 

1) n번째도 마시고 (n-1)번째도 마신 경우 → 자동적으로 (n-2)번째는 마실 수 없다.

2) n번째를 마시고 (n-1)번째는 마시지 않은 경우

3) n번째를 마시지 않은 경우

이 세가지 중 최댓값을 dp[n]에 저장하면 된다.

 

즉, 점화식은 다음과 같다. 

dp[n] = max(dp[n - 1], dp[n - 2] + data[n], dp[n - 3] + data[n - 1] + data[n])

 

처음에는 이렇게 세가지 경우로 나누면 모든 경우를 커버할 수 있다는 것이 잘 이해가 안 됐는데, 다음의 그림을 보면 이해가 더 쉽다. 그림을 보면 어떤 경우더라도 다 세가지 경우 중 하나로 들어갈 수 있다는 것을 알 수 있다. 

 

주의할 점! 

처음에 if n > 1: 없이 무조건 dp[2] = data[1] + data[2] 가 실행되도록 했다가 인덱스 에러가 났다. (오답) n이 1일 수도 있어서 문제가 되는 것이다. 조건문만 추가해주니 해결되었다. (정답)