백준 알고리즘, 9461 문제

---

풀이

가장 큰 변의 길이를 추가한다고 했으므로 P[N - 1 ] 은 반드시 들어간다.

추가로 더해지는 값은 P[9] 부터 규칙이 형성된다.

P[9] = P[4] + P[8]

P[10] = P[5] + P[9]

P[11] = P[6] + P[10]

...

따라서 점화식은

P[N] = P[N - 5] + P[N - 1] 

---

코드

@github 에서 보기

/**
 * @site: https://www.acmicpc.net/problem/9461
 * @github: https://github.com/7772
 * @auth: Landon Park
 * @date: 2018. 08. 14
 */
#include <iostream>
using namespace std;
int main() {
    long P[101];
    int i, T, N;
    cin >> T;
    P[1] = 1;
    P[2] = 1;
    P[3] = 1;
    P[4] = 2;
    P[5] = 2;
    P[6] = 3;
    P[7] = 4;
    P[8] = 5;
    while ((T--)) {
        cin >> N;
        for (i = 9; i <= N; i++) {
            P[i] = P[i - 5] + P[i - 1];
        }
        cout << P[N] << endl;
    }
    return 0;
}

# 그림을 이용하여 그대로 코드로 옮기면 위 코드가 맞다. 그러나 수열만 두고 생각한다면 아래도 가능하다.

/**
 * @site: https://www.acmicpc.net/problem/9461
 * @github: https://github.com/7772
 * @auth: Landon Park
 * @date: 2018. 08. 14
 */
#include <iostream>
using namespace std;
int main() {
    long P[101];
    int i, T, N;
    cin >> T;
    P[0] = 0;
    P[1] = 1;
    P[2] = 1;
    
    while ((T--)) {
        cin >> N;
        for (i = 3; i <= N; i++) {
            P[i] = P[i - 2] + P[i - 3];
        }
        cout << P[N] << endl;
    }
    return 0;
}

# 수를 볼 것인지, 그림을 볼 것인지에 따라 필요한 초기값이 달라진다.