[Python] 백준 코테 연습 - DP (2)

 

DP 이어서

 

---

BABBA - 실버5

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

K = int(input())
DP_B = [0] *(K+1)  # 1, 0, 1, 1, 2
DP_BA = [0] *(K+1) # 0, 1, 1, 2, 3
DP_B[1] = 1

for i in range(2, K+1):
    DP_BA[i] = DP_B[i-1] + DP_BA[i-1]
    DP_B[i] = DP_BA[i-1] 

print(DP_BA[K], DP_B[K]+DP_BA[K])

 

 

---

카드 구매하기2 - 실버 1

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

import sys
input = sys.stdin.readline

N = int(input())
P = [0] + list(map(int, input().split()))
DP = [float('inf')] * (N+1)  # DP[i] = 카드 i개를 구하는데 필요한 최소 비용
DP[0] = 0

for i in range(1, N+1):
    for j in range(1, i+1):
        DP[i] = min(DP[i], DP[i-j] + P[j])

print(DP[N])

 

 

 

---

1, 2, 3 더하기 5 - 실버1

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

import sys
input = sys.stdin.readline

T = int(input())

MAX_N = 100000  # 문제에서 n의 최대값을 미리 정할 수 있다.
DP = [[0] * 4 for _ in range(MAX_N + 1)]  # DP[i][j]: i를 만들 때 마지막이 j

# 초기값 설정
DP[1][1] = 1
DP[2][2] = 1
DP[3][1] = 1
DP[3][2] = 1
DP[3][3] = 1

# DP 테이블 채우기
for i in range(4, MAX_N + 1):
    DP[i][1] = (DP[i-1][2] + DP[i-1][3]) % 1000000009
    DP[i][2] = (DP[i-2][1] + DP[i-2][3]) % 1000000009
    DP[i][3] = (DP[i-3][1] + DP[i-3][2]) % 1000000009

for _ in range(T):
    N = int(input())
    print((DP[N][1] + DP[N][2] + DP[N][3])% 1000000009)  # N을 만들 수 있는 모든 경우의 합

• 같은 수를 연속으로 사용하면 안된다는 조건이 추가됐으므로, 마지막 숫자를 저장하는 2차원 DP 배열을 만든다.
• 마지막 숫자를 연속해서 사용하지 않도록 주의해서 i-1, i-2, i-3 번째 DP 값들을 더한다.

 

---

점프 점프 - 실버2

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

import sys
input = sys.stdin.readline

N = int(input())
A = [0] + list(map(int, input().split()))
DP = [float('inf')]*(N+1)  # DP[i] : i번째 칸에 도달하는 데 필요한 최소 점프 횟수
DP[1] = 0

for i in range(1, N+1):
    for j in range(1, i+1):
        if A[j] + j >= i:
            DP[i] = min(DP[j]+1, DP[i])

if DP[-1] == float('inf'):
    print(-1)
else:
    print(DP[-1])

• 점프 횟수이므로 DP[1] = 0, 도달하지 못하는 경우 -1 출력하기 주의

 

 

---

기타리스트 - 실버1

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

import sys
input = sys.stdin.readline

N, S, M = map(int, input().split())
V = list(map(int, input().split()))

DP = [[0] * (M+1) for _ in range(N+1)]  # DP[i][j] == i번째 곡에서 j 볼륨 가능 여부
DP[0][S] = 1

for i in range(N):
    for j in range(M+1):  # 볼륨 0부터 M까지
        if DP[i][j]:
            # i번째 곡에서 j+V[j] or j-V[j] 가능한지 확인
            if 0 <= j + V[i] <= M:
                DP[i+1][j+V[i]] = 1
            if 0<= j - V[i] <= M:
                DP[i+1][j-V[i]] = 1

# 마지막 곡에서 가능한 최댓값 찾기
max_volume = -1
for j in range(M+1):
    if DP[N][j]:
        max_volume = j

print(max_volume)

• DP 배열에 추가적인 정보를 저장하는 문제들이 특히 너무 어려운 것 같다.

 

---

극장 좌석 - 실버 1

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

import sys

input = sys.stdin.readline

N = int(input())  # 전체 좌석 수
M = int(input())  # VIP 좌석 개수
VIP = set(int(input().strip()) for _ in range(M))  # VIP 좌석 번호 집합

# DP 배열 초기화 (최대 N까지 필요)
DP = [1] * (N + 1)
if N > 1:
    DP[2] = 2  # 자리 교환 가능

# DP 테이블 채우기 (피보나치 형태)
for i in range(3, N + 1):
    DP[i] = DP[i - 1] + DP[i - 2]

# VIP 좌석을 기준으로 구간 나누기
prev = 0
result = 1

for i in range(1, N + 1):
    if i in VIP:  # VIP 좌석이면 구간 종료
        length = i - prev - 1
        if length > 0:
            result *= DP[length]
        prev = i  # 다음 구간 시작점 업데이트

# 마지막 구간 처리
length = N - prev
if length > 0:
    result *= DP[length]

print(result)

• DP 배열을 i번째 자리까의 가능한 가짓수로 잘못 두고 계산했다. DP[i] = i개의 연속된 자리가 있을 때의 가능한 가짓수로 두고 계산한다.
• 점화식은 피보나치 수열. i번째 사람이 자리에 앉은 경우(DP[i-1])와 자리를 교환하는 경우(DP[i-1])을 더한다.
• VIP 좌석을 기준으로 구간을 나누고, DP[i] 에 해당하는 값을 곱하면 된다.

 

---

수열 - 실버4

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

import sys

input = sys.stdin.readline

N = int(input())
num = list(map(int, input().split()))
DP = [[0]*2 for _ in range(N)]  # [i][j] 는 [i]번째 까지의 긴 구간의 길이, j는 감소/증가 여부
DP[0][0], DP[0][1] = 1, 1  # 0은 감소, 1은 증가

for i in range(1, N):
    # if num[i] == num[i-1]:
    if num[i] > num[i-1]:
        DP[i][1] = DP[i-1][1] + 1
        DP[i][0] = 1
    elif num[i] < num[i-1]:
        DP[i][0] = DP[i-1][0] + 1
        DP[i][1] = 1
    else:
        DP[i][0], DP[i][1] = DP[i-1][0] + 1, DP[i-1][1] + 1

# print(DP)
print(max(max(x) for x in DP))

• 실버 4라 2차원 DP배열 문제도 쉽게 풀었다^^ DP[i][0] 에는 감소하는 긴 배열, DP[i][1] 에는 증가하는 긴 배열의 길이를 저장했다.

 

 

---

지름길 - 실버1

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

import sys

input = sys.stdin.readline

N, D = map(int, input().split())
roads = []
for _ in range(N):
    roads.append(list(map(int, input().split())))
DP = [i for i in range(D+1)]

for i in range(D+1):
    DP[i] = min(DP[i], DP[i-1]+1)

    for road in roads:
        if road[0] == i and road[1] <= D:
            DP[road[1]] = min(DP[road[1]], DP[road[0]]+road[2])


print(DP[D])

• DP[i]가 아닌 지름길을 타고 도착한 장소 DP[road[1]] 을 update해야 한다. 또한 모든 이용할 수 있는 지름길을 사용하도록 고려해야 한다.
• 도착 지점이 D를 벗어나지 않도록 조건문 추가.

 

---

타일 장식물 - 실버5

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

import sys

input = sys.stdin.readline

N = int(input())
DP = [0]*(N+2)
DP[1] = 4  # 4, 6, 10, 16
DP[2] = 6

for i in range(3, N+1):
    DP[i] = DP[i-1] + DP[i-2]

print(DP[N])

 

 

 

---

격자상의 경로 - 실버2

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

import sys

input = sys.stdin.readline

N, M, K = map(int, input().split())

if K:
    DP1 = [[1]*(K%M) for _ in range(K//M+1)]
    DP2 = [[1]*(M-K%M+1) for _ in range(N-(K//M+1)+1)]
    # print(DP2)

    for i in range(K//M+1):
        for j in range(K%M):
            if i == 0 or j == 0:
                DP1[i][j] = 1
            else:
                DP1[i][j] = DP1[i-1][j] + DP1[i][j-1]

    for i in range(N-(K//M+1)+1):
        for j in range(M-K%M+1):
            if i == 0 or j == 0:
                DP2[i][j] = 1
            else:
                DP2[i][j] = DP2[i-1][j] + DP2[i][j-1]
    print(DP1[-1][-1]*DP2[-1][-1])

else:
    DP = [[1]*M for _ in range(N)]
    for i in range(N):
        for j in range(M):
            if i==0 or j==0:
                DP[i][j] = 1
            else:
                DP[i][j] = DP[i-1][j] + DP[i][j-1]
    print(DP[-1][-1])

• K의 유무에 따라 나누고, K가 있다면 K를 기준으로 DP를 나눈뒤 끝 경로의 경우의 수를 곱해준다.
• 위 풀이는 32점이 나왔다. K를 기준으로 DP 배열을 나누는 과정에서 문제가 있었다.

import sys

input = sys.stdin.readline

N, M, K = map(int, input().split())

def count_paths(n, m):
    DP = [[1] * m for _ in range(n)]
    for i in range(1, n):
        for j in range(1, m):
            DP[i][j] = DP[i-1][j] + DP[i][j-1]
    return DP[-1][-1]

if K:
    r, c = divmod(K-1, M)  # 0-based index
    result = count_paths(r + 1, c + 1) * count_paths(N - r, M - c)
else:
    result = count_paths(N, M)

print(result)

• 일단 DP를 구하고 최종 경로 경우의 수를 return하는 함수를 따로 빼서 가독성을 높였다.
• 그리고 divmod라는 함수를 이용해 K-1과 M의 몫, 나머지를 바로 구해줌.
• 100점!

 

---

돌 게임 3 - 실버3

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

import sys

input = sys.stdin.readline

N = int(input())
DP = [0]*(N+5)  # 1은 SK, 0은 CY
DP[1], DP[2], DP[3], DP[4] = 1, 0, 1, 1 

for i in range(5, N+1):
    if DP[i-1] or DP[i-3] or DP[i-4]:
        DP[i] = 1

if DP[N] == 1:
    print("SK")
else:
    print("CY")

• 틀림. DP[i-1], DP[i-3], DP[i-4] 중 창영이 패배 상태가 하나라도 있으면 상근이가 이길 수 있음. 으로 점화식 수정하기

import sys

input = sys.stdin.readline

N = int(input())
DP = [0]*(N+5)  # 0은 상근, 1은 창영
DP[1], DP[2], DP[3], DP[4] = 1, 0, 1, 1

for i in range(5, N+1):
    if DP[i - 1] == 0 or DP[i - 3] == 0 or DP[i - 4] == 0:
        DP[i] = 1  # 상대가 패배할 수 있는 경우라면, 현재 플레이어가 이긴다.

if DP[N] == 1:
    print("SK")
else:
    print("CY")

 

 

 

 

---

# 회고

 

점화식은 계속 어렵다....