[BaekJoon/백준] 9461번 | 복습 1회 완료

파도반 수열에 대한 문제. 피보나치랑 비슷한 느낌이다.

이를 동적계획법으로 구현하면 된다.

 

 

P(N)에 대해서 나열해봤고,

Tn에 대해서 나열해봤다.

 

여기서 P(N)은 문제에서의 파도반수열이고

Tn은 삼각형 종류와 각 관계에 대한 수열이다.

그림에서보면 T3부터 더해지는 수의 앞자리가 P(N)에서 순서대로 가져와지며, 뒷자리는 자신의 바로 이전 삼각형을 참조한다는 것을 알 수 있다.

 

그리고 마침 T3인 P(6)부터 'P(N - 1) = P(N)의 이전 삼각형' 이 되므로 (1 1 1 2 2 에서는 n-1이 항상 n의 이전삼각형이 아니기 때문에)

이를 토대로 아래 식을 만들어 낼 수 있다.

 

P(N) = P(N - 5) + P(N - 1) // 단, N>5이며 P(1)=1, P(2)=1, P(3)=1, P(4)=2, P(5)=2

이해를 돕기 위한 그림

재귀 코드

#include <stdio.h>

long key[101] = {0, 1, 1, 1, 2, 2, }; // 0번째 인덱스는 안쓰인다. 자리차지로 아무값이나.

long pado(int n) {
    if(key[n])
        return key[n];
    return key[n] = pado(n - 5) + pado(n - 1);
}

int main() {
    int t, x;
    scanf("%d", &t);
    for(int i=0; i<t; i++) {
        scanf("%d", &x);
        printf("%ld\n", pado(x));
    }
}

반복문 코드

#include <stdio.h>

long key[101] = {0, 1, 1, 1, 2, 2, }; // 0번째 인덱스는 안쓰인다. 자리차지로 아무값이나.

int main() {
    int t, x;
    scanf("%d", &t);
    
    
    for(int i = 6; i <= 100; i++) {
        key[i] = key[i - 5] + key[i - 1];
    }
    
    for(int i=0; i<t; i++) {
        scanf("%d", &x);
        printf("%ld\n", key[x]);
    }
}

1~5인덱스까지는 미리 값을 넣어주고, 그 뒤부터 식에 맞게 만들어주면 된다.

 

---

2021.02.23 복습

다시풀어보았다. 이번엔 충분한 검증을 안해본 탓에 "틀렸습니다" 를 여러번 맞았다.. ㅜㅜ 문제는 자료형이 문제였다.

처음에 int로 담았다가 문제가 되어 long long으로 바꿨는데, 100인 경우에는 출력이 자꾸 마이너스가 되어서 문제점을 찾아보니

printf에 출력 서식이 여전히 int였던게 문제였다. 어쨌든 문제를 풀었고, 이전에 푼 걸 보니 long으로도 충분한 문제인 것 같다.

이전에 풀었던 코드가 훨씬 간결하다. ㅎㅎ..ㅜㅜ

#include <stdio.h>

int N;
long long arr[101];

int main() {
    int input;
    
    scanf("%d", &N);
    
    arr[1] = 1; arr[2] = 1; arr[3] = 1; arr[4] = 2; arr[5] = 2;
    
    //테스트케이스가 여러번이므로, 범위 내에서 미리 다 만들어놓음.
    for(int i = 6; i <= 100; i++) {
        arr[i] = (arr[i - 5] + arr[i - 1]);
    }
    
    for(int i = 0; i < N; i++) {
        scanf("%d", &input);
        printf("%lld\n", arr[input]);
    }
}

/*
 
 N
 1 | 1
 2 | 1
 3 | 1
 4 | 2
 5 | 2
 6 | 3 = P(1) + P(5) 규칙이 시작됨.
 7 | 4 = P(2) + P(6)
 8 | 5 = P(3) + P(7)
 9 | 7 = P(4) + P(8)
 10| 9 = P(5) + P(9)
 11| 12
 12| 16
 
 
 */