[백준] 2225, 15988, 1149, 1309 (파이썬)

이제 슬슬 감이 오는 것 같다. 그리고 아는만큼 궁금한 점이 많아지기 시작했다. 오늘은 효율적인 메모리 사용의 기준에 대해서 궁금증이 생겼다. 코테 관련 교재를 구매했으니 배송되는대로 확인하면 될 것 같다. 백준 골드 랭크까지 달성한다면 알고리즘 학습이 적당히 될 것이라고 생각했었는데 오산이었다. 생각보다 배울 것이 많다. 꾸준히 노력해야겠다는 생각이 든다.

백준 2225번 합분해

import sys
N,K = map(int,sys.stdin.readline().split())
dp = [[0]*201 for _ in range(201)]
for i in range(1,N+1):
    if i == 1 :
        for j in range(1,K+1):
            dp[i][j] = j
    else:
        for j in range(1,K+1):
            dp[i][j] = (dp[i][j-1]+dp[i-1][j])
print(dp[N][K]%1000000000)

백준 15988번 1, 2, 3 더하기 3

# 메모리 관리와 관련된 내용을 읽어보고 싶다.
# 교재가 도착하면 세부적으로 알아볼 예정
import sys
T = int(sys.stdin.readline())
dp = [0 for i in range(1000001)]
d = [0, 1, 2, 4]
for i in range(4, 1000001):
    d.append(d[i - 3]%1000000009 + d[i - 2]%1000000009 + d[i - 1]%1000000009)
for j in range(T):
    n = int(sys.stdin.readline())
    print(d[n] % 1000000009)

백준 1149번 RGB거리

import sys
N = int(sys.stdin.readline())
color = list()
for i in range(N):
    color.append(list(map(int,sys.stdin.readline().split())))
for j in range(1,len(color)):
    color[j][0] = color[j][0] + min(color[j-1][1],color[j-1][2])
    color[j][1] = color[j][1] + min(color[j-1][0],color[j-1][2])
    color[j][2] = color[j][2] + min(color[j-1][0],color[j-1][1])
print(min(color[N-1][0],color[N-1][1],color[N-1][2]))

백준 1309번 동물원

import sys
N = int(sys.stdin.readline())
dp = [0, 3, 7]
for i in range(3, 100001):
    dp.append((dp[i - 2] + 2*dp[i - 1])%9901)
print(dp[N]%9901)