[백준] 11057, 2156, 1932

오르막 수 (11057번)

• 사이트/난이도: 백준 / 실버1
• 코드

# 실버1 오르막 수
import sys
input = sys.stdin.readline

n = int(input())
dp = [1] * 10 # 끝자리 수가 0~9 일때 가능한 모든 경우의 수

for i in range(n-1):
    for j in range(1,10):
        dp[j] += dp[j-1]
print(sum(dp) % 10007)

• 느낀점
  • 점화식 규칙을 찾기 힘들었던 dp 문제
  • 끝자리 수를 중점적으로 보면서 0~9으로 끝나는 끝자리 수에 대해 경우의 수를 나열하면 그 앞의 경우의 수가 더해지는걸 알 수 있다.
  • https://jainn.tistory.com/91

포도주 시식 (2156번)

• 사이트/난이도: 백준 / 실버1
• 코드

# 실버1 포도주 시식
import sys
import copy
input = sys.stdin.readline

n = int(input())
arr = [0]
for _ in range(n):
    arr.append(int(input()))

dp = [0]
dp.append(arr[1])
if n > 1:
    dp.append(arr[1] + arr[2])
for i in range(3, n+1):
    dp.append(max(dp[i-1], dp[i-3] + arr[i-1] + arr[i], dp[i-2] + arr[i]))
print(dp[n])

• 느낀점
  • 점화식 못찾아서 못푼 문제..
  • 아래 사이트를 참고해 보니 일단 예시를 자세하게 풀어보면 점화식을 찾을 수 있었따…
  • https://pacific-ocean.tistory.com/152

정수 삼각형 (1932번)

• 사이트/난이도: 백준 / 실버1
• 코드

# 실버1 정수 삼각형

n=int(input())
tri=[]
for _ in range(n):
  tri.append(list(map(int,input().split())))

for i in range(1,n):
  for j in range(i+1):
    if j==0:
      left=0
    else:
      left=tri[i-1][j-1]
    if j==i:
      right=0
    else:
      right=tri[i-1][j]
    tri[i][j] = tri[i][j] + max(left,right)

answer=0
for i in range(n):
  answer=max(answer,tri[n-1][i])
print(answer)

• 느낀점
  • 해당 문제의 점화식은 (i,j) 위치에서 최대값 = (i,j) 값 + i-1 위치에서 왼쪽, 오른쪽 중 최대값 이다.