Jinho Tech

누적 합 & 다이나믹 프로그래밍 문제이다. 처음에는 아래 코드와 같이 풀었다. 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)

기본적인 다이나믹 프로그래밍 문제이다. dp 리스트를 만들어서 풀면 메모리 초과가 나오고

그냥 a, b 변수 2개를 사용해서 풀면 시간 초과가 나오길래 뭔가 했는데, 너무 큰 숫자들로 계산하는 것이 문제였다.

a, b를 변환할 때 1000000007을 나눈 나머지로 수정해주는 식으로 해결했다.

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

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

n = int(input())
dp = [1]*117
for i in range(4, n+1):
    dp[i] = dp[i-3] + dp[i-1]
print(dp[n])

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

def koong(n):
    if n < 2:
        return 1
    if n == 2:
        return 2
    if n == 3:
        return 4
    if dp[n]:
        return dp[n]
    dp[n] = koong(n-1) + koong(n-2) + koong(n-3) + koong(n-4)
    return dp[n]
    
dp = [0]*68
for _ in range(int(input())):
    n = int(input())
    print(koong(n))

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

평범하게 다이나믹 프로그래밍으로 풀면 아래 코드와 같다. 마지막 자리가 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])