99클럽 코테 스터디 29일차 TIL - DP(백준9461-파도반 수열 )

https://www.acmicpc.net/problem/9461

• 오늘의 학습 키워드 : DP
• 공부한 내용

일단 그림을 보고서 규칙을 생각했다. 

위 그림처럼 dp[i] = dp[i-5] + dp[i-1] 를 이용해서 풀었다..

근데 이렇게 생각할 필요 없이 해당 문제는 dp[i]=dp[i−2]+dp[i−3] 점화식으로도 풀수 있는 문제였다..

 

🎯 dp[i] = dp[i-5] + dp[i-1] DP 풀이

import sys

# 테스트 케이스 입력
T = int(sys.stdin.readline().strip())

# 최대 N 값을 위한 초기화
MAX_N = 100

# DP 테이블 초기화
dp = [0] * (MAX_N + 1)
dp[0],dp[1],dp[2],dp[3],dp[4] =1,1,1,2,2

# DP 채우기
for i in range(5,MAX_N+1):
    dp[i] = dp[i-5] + dp[i-1]

# 각 테스트 케이스에 대해 결과 출력
for _ in range(T):
    N = int(sys.stdin.readline().strip())
    print(dp[N])

 

🎯 dp[i] = dp[i-3] + dp[i-2] DP 풀이

 

import sys

# 테스트 케이스 입력
T = int(sys.stdin.readline().strip())

# 최대 N 값을 위한 초기화
MAX_N = 100

# DP 테이블 초기화
dp = [0] * (MAX_N + 1)
dp[1], dp[2], dp[3] = 1, 1, 1

# DP 채우기
for i in range(4, MAX_N + 1):
    dp[i] = dp[i - 2] + dp[i - 3]

# 각 테스트 케이스에 대해 결과 출력
for _ in range(T):
    N = int(sys.stdin.readline().strip())
    print(dp[N])

 

• 오늘의 회고
  • 하나만 보지말고.. 약간 넓게 숲을 보기..? 
  • 먼가,, 하나만 집중하면 하나밖에 안보이는 경향이 있는듯..?