Jinho Tech

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

평범하게 다이나믹 프로그래밍으로 풀면 아래 코드와 같다. 마지막 자리가 0인 숫자 뒤에는 0과 1 2개를, 마지막 자리가 1인 숫자는 0 1개를 추가할 수 있다는 점을 이용하면 된다.

N = int(input())
dp = [0]*91
dp[1] = dp[2] = 1
for i in range(3, N+1):
    dp[i] = dp[i-2]*2 + dp[i-3]
print(dp[N])

결과를 보면 1, 1, 2, 3, 5, 8... 과 같은 규칙이 있어서 아래 코드 같이 쉽게 풀 수도 있다.

N = int(input())
a = b = 1
for i in range(3, N+1):
    a, b = a+b, a
print(a)

간단한 수학 & 다이나믹 프로그래밍 문제이다.

평범하게 다이나믹 프로그래밍으로 풀면 아래 코드와 같다.

N = int(input())
dp = [0]*(11)
dp[1] = 0
dp[2] = 1
for i in range(3, N+1):
    m = i//2
    dp[i] = m*(i-m) + dp[m] + dp[i-m]
print(dp[N])

수학적으로 풀 수도 있는데, 결과를 보면 1, 3, 6, 10, 15... 과 같은 규칙이 있어서 아래 코드 같이 쉽게 풀 수도 있다.

N = int(input())
print(N*(N-1)//2)

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

n = int(input())
dp = [0]*(36)
dp[0] = 1
dp[1] = 1
dp[2] = 2
for i in range(3, n+1):
    t = 0
    if i%2:
        for j in range(i//2):
            t += 2*dp[j]*dp[i-j-1]
        dp[i] = t + dp[i//2]**2
    else:
        for j in range(i//2):
            t += 2*dp[j]*dp[i-j-1]
        dp[i] = t
print(dp[n])

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

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

9655번 돌 게임과 비슷한 문제이다. 이번엔 N이 홀수이면 창영이가, 짝수이면 상근이가 이긴다.

N = int(input())
print("CY" if N%2 else "SK")

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

n = int(input())
a, b = 1, 0
for i in range(n):
    a, b = (a+b)%10, a%10
print(a)

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

H, Y = map(int, input().split())
dp = [0]*(Y+1)
dp[0] = H
for i in range(1, Y+1):
    if i-1 >= 0 and dp[i-1]:
        dp[i] = max(int(dp[i-1]*1.05), dp[i])
    if i-3 >= 0 and dp[i-3]:
        dp[i] = max(int(dp[i-3]*1.2), dp[i])
    if i-5 >= 0 and dp[i-5]:
        dp[i] = max(int(dp[i-5]*1.35), dp[i])
print(dp[Y])

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

n = int(input())
dp = [-1]*(n+1)
dp[0] = 0
for i in range(1, n+1):
    if i >= 2 and dp[i-2] > -1:
        dp[i] = (dp[i-2]+1) if dp[i] == -1 else min(dp[i-2]+1, dp[i])
    if i >= 5 and dp[i-5] > -1:
        dp[i] = (dp[i-5]+1) if dp[i] == -1 else min(dp[i-5]+1, dp[i])
print(dp[n])

N이 홀수면 상근이가 짝수면 창영이가 이길 수 밖에 없다.

N = int(input())
print("SK" if N%2 else "CY")

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

N = int(input())
dp = [0]*(N+1)
dp[0] = 2
dp[1] = 4
for i in range(2, N+1):
    dp[i] = dp[i-1]+dp[i-2]
print(dp[N])

기본적인 다이나믹 프로그래밍 문제이다. 처음에 풀 때 dp에 문자열(EX: "BA")을 저장했는데

메모리 초과가 나와서 그냥 숫자로 해결했다.

k = int(input())
dp = [0]*(k+1)
dp[1] = 1
for i in range(2, k+1):
    dp[i] = dp[i-1]+dp[i-2]
print(dp[k-1], dp[k])

기본적인 이분 탐색 문제이다.

while 1:
    n = int(input())
    if n == 0:
        break
    s, e = 1, 50
    while s <= e:
        m = (s+e)//2
        print(m, end=' ')
        if m == n:
            break
        elif m < n:
            s = m+1
        else:
            e = m-1
    print()

기본적인 BFS 문제이다.

from collections import deque

def bfs(y, x):
    q = deque()
    q.append((y, x))
    graph[y][x] = 'w'
    cnt = 0
    while q:
        y, x = q.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < N) and (0 <= X < N) and graph[Y][X] == '-':
                q.append((Y, X))
                graph[Y][X] = 'w'
                cnt += 1
    return cnt

for _ in range(int(input())):
    N = int(input())
    graph = [list(input()) for _ in range(N)]
    d = [(-1, -1), (-1, 1), (1, -1), (1, 1), (-1, 0), (1, 0), (0, -1), (0, 1)]
    res = 0
    for i in range(N):
        for j in range(N):
            if graph[i][j] == 'w':
                res += bfs(i, j)
    print(res)

기본적인 BFS 문제이다.

from collections import deque

def bfs(y, x):
    q = deque()
    q.append((y, x))
    graph[y][x] = 0
    while q:
        y, x = q.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < 8) and (0 <= X < 8) and graph[Y][X] == -1:
                q.append((Y, X))
                graph[Y][X] = graph[y][x]+1

sy, sx = map(int, input().split())
ey, ex = map(int, input().split())
graph = [[-1]*8 for _ in range(8)]
d = [(-2, -1), (-2, 1), (2, -1), (2, 1), (-1, -2), (1, -2), (-1, 2), (1, 2)]
bfs(sy-1, sx-1)
print(graph[ey-1][ex-1])

기본적인 BFS 문제이다.

from collections import deque

def bfs(y, x):
    q = deque()
    q.append((y, x))
    graph[y][x] = 0
    while q:
        y, x = q.popleft()
        for dy, dx in d:
            Y, X = y+dy, x+dx
            if (0 <= Y < M) and (0 <= X < N):
                if graph[Y][X] == '4':
                    return graph[y][x]+1
                if graph[Y][X] == '1':
                    q.append((Y, X))
                    graph[Y][X] = graph[y][x]+1

M, N, M1, M2 = map(int, input().split())
graph = [input().split() for _ in range(M)]
d = [(-M1, -M2), (-M1, M2), (M1, -M2), (M1, M2), (-M2, -M1), (-M2, M1), (M2, -M1), (M2, M1)]
for i in range(M):
    for j in range(N):
        if graph[i][j] == '3':
            print(bfs(i, j))