Jinho Tech

기본적인 다이나믹 프로그래밍 문제이다. 1차원 DP처럼 똑같이 해주면 된다. 

N, M = map(int, input().split())
li = [list(map(int, input().split())) for _ in range(N)]
dp = [[0]*M for _ in range(N)]
dp[0][0] = li[0][0]
for i in range(N):
    for j in range(M):
        if i == 0 and j == 0:
            continue
        elif i > 0 and j == 0:
            dp[i][j] = dp[i-1][j]
        elif i == 0 and j > 0:
            dp[i][j] = dp[i][j-1]
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        if li[i][j] == 1:
            dp[i][j] += 1
print(max(map(max, dp)))

기본적인 다이나믹 프로그래밍 문제이다. 

N = int(input())
li = list(map(int, input().split()))
dp = [N+1]*N
dp[0] = 0
for i in range(N):
    for j in range(1, li[i]+1):
        if i+j >= N:
            break
        dp[i+j] = min(dp[i+j], dp[i]+1)
print(dp[N-1] if dp[N-1] != N+1 else -1)

기본적인 다이나믹 프로그래밍 문제이다.

import sys
input = sys.stdin.readline

while 1:
    N = int(input())
    if N == 0:
        break
    li = [int(input()) for _ in range(N)]
    for i in range(1, N):
        li[i] = max(li[i], li[i]+li[i-1])
    print(max(li))

기본적인 다이나믹 프로그래밍 문제이다.

n = int(input())
li = list(map(int, input().split()))
dp = [1]*n
for i in range(1, n):
    for j in range(i):
        if li[i] > li[j]:
            dp[i] = max(dp[i], dp[j]+1)
print(max(dp))

기본적인 다이나믹 프로그래밍 문제이다. 

N = int(input())
li = list(map(int, input().split()))
dp1, dp2 = [1]*N, [1]*N
for i in range(1, N):
    if li[i] <= li[i-1]:
        dp1[i] = max(dp1[i], dp1[i-1]+1)
    if li[i] >= li[i-1]:
        dp2[i] = max(dp2[i], dp2[i-1]+1)
print(max(max(dp1), max(dp2)))

기본적인 다이나믹 프로그래밍 문제이다. 자기 앞에 자기보다 작은 수가 없는 경우도 있는데,

이 부분만 주의하면 쉽게 풀 수 있다.

from copy import deepcopy

N = int(input())
li = list(map(int, input().split()))
dp = deepcopy(li)
for i in range(1, N):
    for j in range(i):
        if li[j] < li[i]:
            dp[i] = max(dp[i], li[i]+dp[j])
print(max(dp))

기본적인 다이나믹 프로그래밍 문제이다.

N = int(input())
li = list(map(int, input().split()))
dp = [1]*N
for i in range(1, N):
    for j in range(i):
        if li[i] < li[j]:
            dp[i] = max(dp[i], dp[j]+1)
print(max(dp))

기본적인 다이나믹 프로그래밍 문제이다. 뒤쪽 대각선 방향으로 첫 번째, 두 번째 위치의 값 중 큰 걸 선택하면 된다.

dp[0][j] += max(dp[1][j-1], dp[1][j-2]) 

dp[1][j] += max(dp[0][j-1], dp[0][j-2])

for _ in range(int(input())):
    n = int(input())
    dp = [[0]+list(map(int, input().split())) for _ in range(2)]    
    for j in range(2, n+1):
        dp[0][j] += max(dp[1][j-1], dp[1][j-2])
        dp[1][j] += max(dp[0][j-1], dp[0][j-2])
    print(max(dp[0][n], dp[1][n]))

기본적인 다이나믹 프로그래밍 문제이다.

N = int(input())
dp = [[0]*10 for _ in range(N+1)]
for i in range(10):
    dp[1][i] = 1
for i in range(2, N+1):
    for j in range(10):
        for k in range(j+1):
            dp[i][j] += dp[i-1][k]
print(sum(dp[N])%10007)

기본적인 다이나믹 프로그래밍 문제이다.

def dfs(n):
    if n == M:
        print(*t)
        return ;
    for i in range(N):
        if check[i]:
            continue
        t.append(li[i])
        check[i] = 1
        dfs(n+1)
        t.pop()
        check[i] = 0

N, M = map(int, input().split())
li = sorted(map(int, input().split()))
check = [0]*N
t = []
dfs(0)

간단한 브루트포스 알고리즘 or 다이나믹 프로그래밍 문제이다.

브루트포스 알고리즘 풀이

a, b, c, n = map(int, input().split())
res = 0
for i in range(0, n+1, a):
    for j in range(0, n-i+1, b):
        for k in range(0, n-i-j+1, c):
            if i+j+k == n:
                res = 1
print(res)

다이나믹 프로그래밍 풀이

a, b, c, n = map(int, input().split())
li = [a, b, c]
dp = [0]*(n+1)
dp[0] = 1
for i in range(1, n+1):
    for t in li:
        if i-t >= 0 and dp[i-t]:
            dp[i] = 1
print(dp[n])

기본적인 다이나믹 프로그래밍 문제이다. 현재 포도주를 마시지 않는 경우, 앞에 포도주를 마시고 현재 포도주를

마시는 경우, 앞에 포도주를 마시지 않고 현재 포도주를 마시는 경우로 총 세 가지를 고려해주면 된다.

-> dp[i] = max(dp[i-1], dp[i-3]+li[i-1]+li[i], dp[i-2]+li[i])

n = int(input())
li = [0] + [int(input()) for _ in range(n)]
dp = [0]*(n+1)
dp[1] = li[1]
if n > 1:
    dp[2] = li[1] + li[2]
for i in range(3, n+1):
    dp[i] = max(dp[i-1], dp[i-3]+li[i-1]+li[i], dp[i-2]+li[i])
print(max(dp))

다이나믹 프로그래밍 or 그래프 탐색 문제이다.

다이나믹 프로그래밍 풀이

N = int(input())
dp = [[0, []] for _ in range(N+1)]
dp[1][0] = 0
dp[1][1] = [1]
for i in range(2, N+1):
    dp[i][0] = dp[i-1][0] + 1
    dp[i][1] = dp[i-1][1] + [i]
    if i%2 == 0 and dp[i//2][0]+1 < dp[i][0]:
        dp[i][0] = dp[i//2][0] + 1
        dp[i][1] = dp[i//2][1] + [i]
    if i%3 == 0 and dp[i//3][0]+1 < dp[i][0]:
        dp[i][0] = dp[i//3][0] + 1
        dp[i][1] = dp[i//3][1] + [i]
print(dp[-1][0])
print(*dp[-1][1][::-1])

그래프 탐색(BFS) 풀이

입력이 1일 때만 주의해서 잘 처리해주면 된다.

from collections import deque

def bfs(node, dp):
    q = deque()
    q.append((node, dp))
    while q:
        node, dp = q.popleft()
        for n in [node+1, node*2, node*3]:
            if n <= N and check[n] == 0:
                if n == N:
                    return check[node]+1, dp+[n]
                q.append((n, dp+[n]))
                check[n] = check[node]+1

N = int(input())
if N == 1:
    print(0)
    print(1)
else:
    check = [0]*(N+1)
    cnt, dp = bfs(1, [1])
    print(cnt)
    print(*dp[::-1])

누적 합 & 다이나믹 프로그래밍 문제이다. 처음에는 아래 코드와 같이 풀었다. PyPy3로 제출해야 통과가 된다.

import sys

N, M = map(int, sys.stdin.readline().split())
li = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
for i in range(N):
    for j in range(1, N):
        li[i][j] = li[i][j-1]+li[i][j]
for _ in range(M):
    sy, sx, ey, ex = map(int, sys.stdin.readline().split())
    res = 0
    for i in range(sy-1, ey):
        if sx < ex:
            res += (li[i][ex-1]-li[i][sx-2]) if sx > 1 else li[i][ex-1] 
        else:
            res += li[i][sx-1]-li[i][sx-2] if sx > 1 else li[i][sx-1]
    print(res)

그러다 더 좋은 해답이 없나 찾아보다가 아래 코드같이 더 효율적으로 풀 수 있었다. 

import sys

N, M = map(int, sys.stdin.readline().split())
li = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
dp = [[0]*(N+1) for _ in range(N+1)]
for i in range(1, N+1):
    for j in range(1, N+1):
        dp[i][j] = li[i-1][j-1] + dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1]
for _ in range(M):
    sy, sx, ey, ex = map(int, sys.stdin.readline().split())
    res = dp[ey][ex] - dp[sy-1][ex] - dp[ey][sx-1] + dp[sy-1][sx-1]
    print(res)

res = dp[ey][ex] - dp[sy-1][ex] - dp[ey][sx-1] + dp[sy-1][sx-1] 가 핵심이다. (sy, sx)~(ey, ex)까지의 합을

구하기 위해 (1, 1)~(ey, ex)까지의 합에서 (1, 1)~(sy-1, ex)까지의 합과 (1, 1)~(ey, sx-1)까지의 합을 빼주게 되는데

이때 (1, 1)~(sy-1, ey-1)까지의 합은 2번 빼게 돼서 결과에 한 번 더해줘야 한다.

기본적인 다이나믹 프로그래밍 문제이다.

n = int(input())
if n < 2:
    print(1)
else:
    a, b = 1, 1
    for i in range(n-1):
        a, b = a+b+1, a
    print(a%1000000007)