[백준] 11057, 9465, 2156, 1932 (파이썬)

오늘 1차 목표로 잡았던 백준 골드랭크를 달성했다. 결과적으로 내가 느낀 것은 한마디로 표현할 수 있다. 나는 한참 멀었다. 문제를 풀어갈 수록 느낀다. 이 문제를 더 효율적으로 풀 방법이 있다는 것을. 또한 내가 아직 알지 못하는 알고리즘 풀이법이 많다는 것을. 내일이면 이코테 책이 도착한다. 주말부터는 친구들과 스터디까지 진행할 예정. 그때까지는 남은 다이나믹 프로그래밍 문제를 풀어나가도록 하자. 다음 목표는 알고리즘 모든 개념숙지, 백준 플레티넘 랭크, 프로그래머스 문제풀이 시작이다. 앞으로도 파이팅이다.

백준 11057번 오르막 수

import sys
N = int(sys.stdin.readline())
dp = list([[1] * 10])
for _ in range(N):
    dp.append(list([0]*10))
for i in range(1,N+1):
    for j in range(10):
        for k in range(j+1):
            dp[i][j] += dp[i-1][k]
print(sum(dp[N-1])%10007)

백준 9465번 스티커

import sys
T = int(sys.stdin.readline())
for _ in range(T):
    n = int(sys.stdin.readline())
    dp = list()
    dp.append(list(map(int,sys.stdin.readline().split())))
    dp.append(list(map(int,sys.stdin.readline().split())))
    for i in range(1,n):
        if i==1:
            dp[0][i] = dp[0][i] + dp[1][i-1]
            dp[1][i] = dp[i][1] + dp[0][i-1]
        else:
            dp[0][i] = max(dp[1][i-2],dp[1][i-1])+dp[0][i]
            dp[1][i] = max(dp[0][i-2],dp[0][i-1])+dp[1][i]
    print(max(dp[0][n-1],dp[1][n-1]))

백준 2156번 포도주 시식

# 애매할 땐 경우의 수를 다 써보자
# 쉬울 줄 알았는데 생각보다 막혔던 문제
import sys
n = int(sys.stdin.readline())
podo = [0]
for _ in range(n):
    podo.append(int(sys.stdin.readline()))
dp = [0]
dp.append(podo[1])
if n>1:
    dp.append(podo[1]+podo[2])
    for i in range(3, n + 1):
        dp.append(max(dp[i-1],dp[i-3]+podo[i-1]+podo[i],dp[i-2]+podo[i]))
print(dp[n])

백준 1932번 정수 삼각형

import sys
T = int(sys.stdin.readline())
dp = list()
for _ in range(T):
    dp.append(list(map(int,(sys.stdin.readline().split()))))
count=2
for i in range(1, T):
    for j in range(count):
        # 행의 양쪽 끝은 그냥 더함
        if j==0:
            dp[i][j]=dp[i-1][j]+dp[i][j]
        elif i==j:
            dp[i][j]=dp[i-1][j-1]+dp[i][j]
        # 이전 행의 왼쪽과 오른쪽 중 큰 값
        else:
            dp[i][j]=max(dp[i-1][j-1],dp[i-1][j])+dp[i][j]
    count+=1
print(max(dp[T-1]))