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

 

DP 어려워서 추가 연습중

 

---

가장 큰 증가하는 부분 수열 - 실버2

https://www.acmicpc.net/status?user_id=jain5379&problem_id=11055&from_mine=1

import sys
input = sys.stdin.readline

A = int(input())
num = list(map(int, input().split()))
DP = [0]*A  # 합이 가장 큰 증가하는 수열 저장
DP[0] = num[0]
max_value = 0

for i in range(A):
    for j in range(i):
        if num[i] > num[j]:
            DP[i] = max(DP[j] + num[i], DP[i])
        else:
            DP[i] = max(DP[i], num[i])

# print(DP)
print(max(DP))

• 처음에 else문을 빼먹었더니 틀렸다.

 

 

---

제곱 수의 합 - 실버2

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

# 시간 초과
import sys
import math
input = sys.stdin.readline

N = int(input())
DP = [0]*(N+1)

for i in range(1, N+1):
    if math.isqrt(i)**2 == i:
        DP[i] = 1
        continue
    DP[i] = DP[i-1] + 1
    for j in range(1, i):    
        DP[i] = min(DP[j]+DP[i-j], DP[i])

# print(DP)
print(DP[N])

• 제곱수인 경우 판별을 math를 이용하면 안될 것 같음

 

import sys
import math
input = sys.stdin.readline

N = int(input())
DP = [x for x in range(N+1)]

for i in range(1, N+1):
    for j in range(1, i):
        if j*j > i:
            break
        if DP[i] > DP[i-j*j]+1:
            DP[i] = DP[i-j*j] + 1

# print(DP)
print(DP[N])

• 먼저, 모든 수는 1의 제곱수로 표현될 수 있으므로 각 인덱스로 초기화
• 다른 제곱수의 합으로 표현될 수 있는 경우, j*j는 i보다 크면 안된다.
• DP[i] > DP[i-j*j]+1 제곱수로 표현할 때 가장 항의 갯수가 적은 j를 찾는다. DP[6] == DP[6 - 2*2] + 1 == DP[2] + 1 이 된다.
• 시간기준이 꽤 빡세다. min() 쓰지 말고 if문으로 확인해야함.
• https://jyeonnyang2.tistory.com/50

[Python] 백준 1699번: 제곱수의 합 풀이

 

 

 

---

동물원 - 실버1

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

import sys
input = sys.stdin.readline

N = int(input())
DP = [0]*(N+1)
# 0, 3, 7, 17, 41, ...

if N==1:
    print(3)
else:
    DP[1] = 3
    DP[2] = 7
    for i in range(3, N+1):
        DP[i] = (2*DP[i-1]+DP[i-2])%9901

    print(DP[N])

• DP[i] = DP[i-1] 에서 두 칸을 추가한 것이다.
• DP[i-1] 에서 두 칸을 추가 한 뒤, 사자를 놓는 경우의 수는 왼쪽/오른쪽 혹은 비워두는 경우의 수를 구해서 2*DP[i-1]이 된다.
• 여기서 DP[i-1] 칸을 비운 뒤(중복 문제) 놓는 경우의 수는 DP[i-2] 값이 된다.
• 어렵다.....아래 수학 식으로 보자...
• https://great-park.tistory.com/131

[BOJ/백준] 1309번 동물원 (Python 파이썬)

 

 

 

---

이동하기 - 실버2

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

import sys
input = sys.stdin.readline

N, M = map(int, input().split())
candy = [list(map(int, input().split())) for _ in range(N)]
DP = [[0]*(M+1) for _ in range(N+1)]



for i in range(1, N+1):
    for j in range(1, M+1):
        DP[i][j] = max(DP[i-1][j], DP[i][j-1], DP[i-1][j-1]) + candy[i-1][j-1]

print(DP[N][M])

• 위, 왼쪽, 대각선 왼쪽의 DP와 비교해서 가장 큰 값을 가져온 후 현재 위치의 candy값을 더해 DP[i][j] 에 저장한다.

 

 

---

점프 - 실버 1

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

import sys
input = sys.stdin.readline

N = int(input())
board = [list(map(int, input().split())) for _ in range(N)]
DP = [[0] * N for _ in range(N)]
DP[0][0] = 1  # 시작점 설정

for i in range(N):
    for j in range(N):
        jump = board[i][j]

        if jump == 0:  # 종착점 도착 후 점프 방지
            continue

        if j + jump < N:  # 오른쪽 이동 가능
            DP[i][j + jump] += DP[i][j]
        if i + jump < N:  # 아래쪽 이동 가능
            DP[i + jump][j] += DP[i][j]

print(DP[N-1][N-1])  # (N-1, N-1) 위치에서 도달 가능한 경로 수 출력

• jump==0 조건을 빼먹어서 오래걸렸다. 이 조건을 빼먹으면 종착점에서 그대로 하번 더 DP값을 더하게된다...3+3+6해서 답이 12가 나왔당..

 

 

---

Four Squares - 실버3

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

import sys
input = sys.stdin.readline

N = int(input())
DP = [x for x in range(N+1)]

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

print(DP[N])

• 이전에 풀었던 제곱수의 합 문제 코드를 더 빠르게 해서 풀었는데 시간초과가 났다. 
• 다른 접근법을 찾았는데...그냥 PyPy로 제출하면 풀린다.

 

n = int(input())
count = 0

DP = [0] * (n + 1)

k = 1
while k**2 <= n:  # 제곱수는 1로 초기화
    DP[k**2] = 1
    k += 1

for i in range(1, n + 1):
    if DP[i] != 0:  # 최소 개수의 제곱수 합으로 표현된 경우
        continue
    j = 1
    while j*j <= i:  # 제곱수를 빼가며 최소 개수 계산
        if DP[i] == 0:
            DP[i] = DP[j*j] + DP[i - j*j]
        else:
            DP[i] = min(DP[i], DP[j*j] + DP[i - j*j])
        j += 1
print(DP[n])

• 제곱수를 빼가며 계산하는 다른 접근법. 시간은 똑같음
• 브루트포스로 풀면 Python으로 제출 가능.
• https://velog.io/@sbkwon16/%EB%B0%B1%EC%A4%80-17626%EB%B2%88-Python

 

 

---

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

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

# 시간 초과
T = int(input())

for i in range(T):
    N = int(input())
    DP = [0] * (N+1)  # 1, 2, 4, 7, ...
    DP[1], DP[2], DP[3] = 1, 2, 4
    for j in range(4, N+1):
        DP[j] = (DP[j-1] + DP[j-2] + DP[j-3])%1000000009
    print(DP[N])

• 4라는 숫자는 1 or 2 or 3에서 +3 or +2 or +1을 한 숫자이므로 위 점화식 도출.
• N 제한이 커서 O(T+N) 이 시간 초과가 남.

T = int(input())

DP = [0] * (1000001)  # 1, 2, 4, 7, ...
DP[1], DP[2], DP[3] = 1, 2, 4
for j in range(4, 1000001):
    DP[j] = (DP[j-1] + DP[j-2] + DP[j-3])%1000000009

for i in range(T):
    N = int(input())
    print(DP[N])

• DP 배열을 미리 만들어서 O(N) 으로 수정

 

---

상자넣기 - 실버2

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

N = int(input())
box = list(map(int, input().split()))
DP = [1]*(N)

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

print(max(DP))

• LIS와 같은 문제

 

---

돌 게임2 - 실버5

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

N = int(input())
DP = [0]*(1001)  # DP[i] = 돌이 i개 남았을 때 상근이가 이기는 경우 1
DP[1], DP[2], DP[3] = 0, 1, 0

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

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

• DP[i-1] 혹은 DP[i-3] 이 0이라는 것은 상근이의 패배, 즉 마지막 돌을 상근이가 가져간 것이다. 이 때 +1 혹은 +3이라면 상근이가 돌을 가져가고 남은 돌을 상대방이 가져가게 되는 돌의 갯수가 된다.

 

---

피보나치 수 4 - 실버5

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

N = int(input())
DP = [0]*(10001) 
DP[1] = 1

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

print(DP[N])

 

 

 

---

# 회고

 

DP 너무 어려워...실버 문제 계속 풀면서 감을 잡아야 할 것 같다.

점화식을 어떻게 찾을 수 있는지..피보나치처럼 공식이 있으면 좋겠다...