[python]백준 9461번: 파도반 수열(DP)

# 9461 파도반 수열

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

9461번: 파도반 수열

코드

T = int(input())
for _ in range(T):
  n = int(input())
  dp = [0] * 101
  dp[1] = 1
  dp[2] = 1
  dp[3] = 1
  dp[4] = 2
  dp[5] = 2
  dp[6] = 3
  for i in range(5, n+1):
    dp[i] = dp[i-1] + dp[i-5]

  print(dp[n])

📝 풀이

그림과 같이 정삼각형의 변의 길이를 추적하면 되는 문제이다.

1, 1, 1, 2, 2, 3, 4, 5, 7, 9로 변의 길이가 점점 증가하는데 규칙성을 찾기만 하면 쉬운 문제였던 것 같다.

🔓 코드 뜯어보기

T = int(input())
for _ in range(T):
  n = int(input())
  dp = [0] * 101
  dp[1] = 1
  dp[2] = 1
  dp[3] = 1
  dp[4] = 2
  dp[5] = 2
  dp[6] = 3
  for i in range(5, n+1):
    dp[i] = dp[i-1] + dp[i-5]

  print(dp[n])

규칙성을 찾기 위해서 숫자를 일일이 적어봤다.

1 1 1 2 2 3 4 5(4+1) 7(5+2) 9(7+2) 12(9+3) 16(12+4) 21(16+5) 28(21+7) 37(28+9) 49(37+ 12)

위와 같은 방법으로 7은 5+2, 9는 7+2, 12는 9+3으로 규칙성을 가진다. 즉 dp[i] = dp[i-1] + dp[i-5]의 규칙을 가진다. 그렇기 때문에 dp[i-5]까지는 dp리스트에 기록해주고 for문으로 n+1까지 반복문을 돌려주면 dp에 정삼각형의 변의 길이가 기록되게 된다.