[실버 III] 9461번. 파도반 수열

 문제 

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

9461번: 파도반 수열

 사용 언어 

Python3

 풀이 과정 

solved.ac의 클래스 3을 따내려고 난이도가 낮은 것부터 한 문제씩 푸는 중인데, 아직까지는 풀만 한 것 같다.

이번에는 DP와 수열이 합쳐진 문제였고 규칙성을 생각해보면 그대로 금방 풀 수 있었다.

 

삼각형이기 때문에 변의 개수 만큼 돌아가고, 그래서 i번째 숫자와 i+1번째 숫자를 더한 값이 i+3번째에 놓인다는 사실을 알았다.

 

그렇게 풀어서 제출했더니 쉽게 맞았습니다!!

 제출 답안 

from sys import stdin
input = stdin.readline

dp = [0] * 101
dp[1] = 1
dp[2] = 1
dp[3] = 1
for i in range(0, 98):
    dp[i+3] = dp[i] + dp[i+1]

case = int(input())
for i in range(case):
    n = int(input())
    print(dp[n])

 다른 사람 코드 

문제가 간단해서 엄청 다르게 푼 코드를 찾진 못했다.

import sys

T = int(sys.stdin.readline())

arr = [0] * 100
arr[0] = 1
arr[1] = 1
arr[2] = 1
arr[3] = 2
arr[4] = 2
arr[5] = 3

for i in range(6, 100):
    arr[i] = arr[i - 2] + arr[i - 3]

for _ in range(T):
    N = int(sys.stdin.readline())
    print(arr[N - 1])

➡ 위와 같이 문제에서 주어진 수열은 다 기본값으로 제공해주고 연산량을 조금이라도 줄인게 도움이 됐는지 모르겠다. 그리고 뭔가 DP 문제를 풀 때 변수 선언을 위와 같이 i를 기준으로 하는 게 확실히 깔끔하다는 것을 느꼈다.