[백준]_9461번 : 파도반 수열(파이썬 and C언어)

9461번: 파도반 수열

반복적으로 돌아가는 수열같아서 살짝 피보나치 냄새가 나는 문제인 것 같다. 경우들을 나열해 보면서 규칙을 찾아 보자

 

규칙 찾기

N	1	2	3	4	5	6	7	8
N 번째길이	1	1	1	2	2	3	4	5

N 번째 삼각형의 한변의 길이를 p[N] 이라고 하자. 

p[4]=p[1]+p[2]

p[5]=p[2]+p[3]

p[6]=p[3]+p[4]

...

따라서 p[N]=p[N-2]+p[N-3] 을 도출할 수 있다. 

시도 1(Python)

import sys
input=sys.stdin.readline
dp=[i for i in range(101)]
dp[1], dp[2], dp[3] = 1, 1, 1
for i in range(4,101):
    dp[i]=dp[i-2]+dp[i-3]
for _ in range(int(input())):
    print(dp[int(input())])

<평가> 굳이 101까지 잡고 dp[0]에 아무것도 배정하지 않은 이유는 사용자로부터 N을 입력받았을 때 dp[N]을 바로 꺼내주는 것이 더 직관적으로 이해하기 쉬워서이다. 

시도 2(C언어)

#include <stdio.h>
int main() {
    long long dp[101]={ 0 };
    int cnt,n;
    dp[1]=1;
    dp[2]=1;
    dp[3]=1;
    for(int i=4;i<101;i++)
        dp[i]=dp[i-2]+dp[i-3];
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&cnt);
        printf("%lld\n", dp[cnt]);
    }
    return 0;	
}

파이썬과 유일하게 다른 점은 dp의 자료형을 long long 으로 충분히 크게 설정해 주는 것이다. 왜냐하면 dp[100] 무려 888855064897이 나오기 때문이다.