EDOC 2024-1 4회차 과제 (동적 계획법 알아보기 2)

087. 2×n 타일링 (백준 11726번)

 

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

 

import sys
input = sys.stdin.readline
m = 10007

n = int(input())
# dp: 순열
dp = [[0 for _ in range(n + 1)] for _ in range(n + 1)]

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

ans = 0
i = n
j = 0
while i >= j:
    ans = (ans + dp[i][j]) % m
    i -= 1
    j += 1

print(ans)

n=1부터 적어보면서 규칙을 찾아보니 다음과 같았다. 

n=1 ⇒ 1C0 = 1

n=2 ⇒ 2C0 + 1C1 = 2

n=3 ⇒ 3C0 + 2C1 = 3

n=4 ⇒ 4C0 + 3C1 + 2C2 = 5

n=5 ⇒ 5C0 + 4C1 + 3C2 = 8

일반화해보면 i+j=n을 성립시키는 i와 j에 대해 iCj를 전부 더하면 되는 것이다. (당연히 i는 j보다 크거나 같아야 한다.) 그래서 n까지의 모든 C값을 dp에 저장해두고 답을 구했다. (정답)

 

import sys
input = sys.stdin.readline
m = 10007

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

# 점화식 dp[n] = dp[n-1] + dp[n-2]

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

for i in range(3, n + 1):
    dp[i] = (dp[i - 1] + dp[i - 2]) % m

print(dp[n])

그런데 더 쉬우면서도 간단하면서도 빠른 코드가 있었으니...  (책을 보고 알게 되었다.)  정말 간단한 점화식 하나로 풀 수 있는 문제였다. 이 점화식이 나오는 과정은 다음과 같다. (정답)

 

 

---

 

088. 쉬운 계단 수 (백준 10844번)

 

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

 

import sys
input = sys.stdin.readline

mod = 1000000000

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

for i in range(1, 10):
    dp[i][1] = 1

for j in range(2, n + 1):
    dp[0][j] = dp[1][j - 1]
    dp[9][j] = dp[8][j - 1]
    for i in range(1, 9):
        dp[i][j] = (dp[i - 1][j - 1] + dp[i + 1][j - 1]) % mod

ans = 0
for i in range(10):
    ans = (ans + dp[i][n]) % mod

print(ans)

dp[i][j] : 길이가 j이면서 i로 끝나는 계단 수

0으로 끝나는 수 ⇒ dp[0][j] = dp[1][j - 1]
9로 끝나는 수 ⇒ dp[9][j] = dp[8][j - 1]
나머지 ⇒ dp[i][j] = (dp[i - 1][j - 1] + dp[i + 1][j - 1])

이렇게 0 또는 9로 끝나는 경우와 아닌 경우로 나눠서 점화식을 세우고 풀었다. (정답)

 

---

 

089. 연속합 2 (백준 13398번)

 

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

 

import sys
input = sys.stdin.readline

n = int(input())
data = list(map(int, input().split()))

l = [0 for _ in range(n)]
l[0] = data[0]
res = l[0]

for i in range(1, n):
    l[i] = max(data[i], l[i - 1] + data[i])
    res = max(res, l[i]) # 수를 제거하지 않았을 때의 최댓값

r = [0 for _ in range(n)]
r[n - 1] = data[n - 1]

for i in range(n - 2, -1, -1):
    r[i] = max(data[i], r[i + 1] + data[i])

for i in range(1, n - 1):
    tmp = l[i - 1] + r[i + 1] # 수를 제거했을 때의 최댓값
    res = max(res, tmp)

print(res)

왼쪽부터의 합과 오른쪽부터의 합을 나누어서 해결해야 된다는 느낌은 받았으나.. 정확히 어떻게 dp 배열을 만들어야 하고 그걸 통해서 어떻게 답을 도출해내는 건지는 감이 안 잡혔다... 그래서 거의 책을 보고 풀었다. (정답)

l[n] : 왼쪽에서부터 n을 포함한 최대 연속 합 ⇒ l[i] = max(data[i], l[i - 1] + data[i])

r[n] : 오른쪽에서부터 n을 포함한 최대 연속 합 ⇒ r[i] = max(data[i], r[i + 1] + data[i])

수를 제거하지 않았을 때의 최댓값 : l[n] 중 최댓값

수를 제거했을 때의 최댓값 : l[n - 1] + r[n + 1]중 최댓값