9461번: 파도반 수열(백준 C++)

9461번: 파도반 수열 링크

코드

#include <iostream>
#include <vector>
using namespace std;

vector<long long> v(4, 1);
//P(1) ~ P(3) 1, 1, 1 P(0)은 존재하지 않지만 편의상 생성.

void solve(int n){
    int l = v.size() - 1;
    //주어진 n의 크기가 Vector v의 크기보다 작으면 바로 출력.
    if(n > l){
    //주어진 n의 크기가 Vector v의 크기보다 크면
    //현재까지 구한 P의 값 이후부터 시작해서 P(n) 산출
    //점화식 P(n) = P(n-3) + P(n-2)
        for(int i = l+1; i<=n; i++){
            v.push_back(v[i-3] + v[i-2]);
        }
    }
    printf("%lld\n", v[n]);
}

int main() {
    int t, n;
    scanf("%d", &t);
    for(int i=0; i<t; i++){
        scanf("%d", &n);
        solve(n);
    }
}

풀이 및 사견

문제

위 사진과 같은 모양으로 삼각형을 배치할 때 n번째 배치하는 삼각형의 변의 크기는 무엇인가? 가 문제다.
사실 나의 경우에는 그림은 안 보고 문제에 주어진 N이 1~10까지의 수 배열을 보고 풀었다.

P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

여기서 점화식을 추측해 낼 수 있기 때문.

점화식 1

그림을 안 보고 P(1) ~ P(10)까지의 수열만 보았을때 추측한 점화식은 아래와 같다.

P(N) = P(N-3) + P(N-2) , (N >= 4)

점화식 2

그림을 보고 알 수 있는 점화식은 아래와 같다.

P(N) = P(N-1) + P(N-5), (N >= 6)

풀이

기존에 작성한 코드의 경우는 점화식 1을 가지고 작성된 코드이다.
아무생각없이 그림을 안 봐도 점화식이 보이는 것 같아 이렇게 풀었는데 글을 작성하며 그림을 보는데 점화식 2가 생각이 났다.

그래서 곧바로 점화식 2로 코드를 작성해 보았다.

#include <iostream>
#include <vector>
using namespace std;

vector<long long> v(4, 1);
//P(1) ~ P(3) 1, 1, 1 P(0)은 존재하지 않지만 편의상 생성.

void solve(int n){
    int l = v.size() - 1;
    //주어진 n의 크기가 Vector v의 크기보다 작으면 바로 출력.
    if(n > l){
    //주어진 n의 크기가 Vector v의 크기보다 크면
    //현재까지 구한 P의 값 이후부터 시작해서 P(n) 산출
    //점화식 P(n) = P(n-5 + P(n-1)
        for(int i = l+1; i<=n; i++){
            v.push_back(v[i-1] + v[i-5]);
        }
    }
    printf("%lld\n", v[n]);
}

int main() {
    v.push_back(2); //P(4)
    v.push_back(2); //P(5)
    int t, n;
    scanf("%d", &t);
    for(int i=0; i<t; i++){
        scanf("%d", &n);
        solve(n);
    }
}

정답이다.

아마 문제가 원래 원했던 정답은 점화식 2에 더 가깝지 않을까 생각이 들긴 한다.

점화식은 위의 두 개와 같으며, 또한 문제를 푸는 방법에 있어서도 두 가지를 생각해봤다.

여러개의 변수 사용하여 풀기

점화식이 P(N) = P(N-3) + P(N-2) , (N >= 4)라면
변수를 4개 설정한다. temp1, temp2, temp3, n
temp1 -> P(N-3)
temp2 -> P(N-2)
temp3 -> P(N-1)
n -> P(N-3) + P(N-2)

• N = 4
  n = temp1 + temp2
  temp1 = temp2
  temp2 = temp3
  temp3 = n

즉, n에 P(n) 값을 구해서 추가하고
temp1~3 을 index 하나씩 미뤄주는 것이다.

이 방법을 사용한 코드는 이와 같다.

#include <iostream>

using namespace std;

long long padovan(int n){
    long long n1 = 1;
    long long n2 = 1;
    long long n3 = 1;
    long long ans;
    if (n < 4) { return 1; }
    for (int i = 4; i <= n; i++) {
        ans = n1 + n2;
        n1 = n2;
        n2 = n3;
        n3 = ans;
    }
    return ans;
}

int main() {
    int t;
    cin >> t;
    for (int i = 0; i < t; i++) {
        int n;
        cin >> n;
        cout << padovan(n) << "\n";
    }
}

Vector 사용하여 저장하기.

내가 푼 방법이다.

점화식이 P(N) = P(N-3) + P(N-2) , (N >= 4)라면
변수 vector v를 생성하고 v = {1,1,1}로 초기화한다.
(나의 경우에는 index 1부터 시작하기 위해서 편의상 v[0]에도 1을 넣어놨다.)

초기상태의 벡터이다.
이후 P(4)를 구해야 한다고 하자.

초기상태의 벡터는 크기가 3이기 때문에 주어진 N인 6보다 작다.
따라서 점화식을 사용하여 P(6)을 구한다.
점화식의 시작은 벡터의 크기 + 1인 N = 4부터 시작해서 N = 6까지이며 이때까지의 값은 벡터에 저장한다.

다음 N = 5일때를 구해보자

이미 이전에 우리는 N = 6까지 구해놨다.
이는 벡터의 크기가 현재 6으로 주어진 수 N보다 크다는 것으로 알 수있다.
따라서 추가적으로 점화식을 할 필요없이 바로 출력한다.

다음 N = 8일때를 구해보자

마찬가지로 N = 8로 벡터의 크기인 6보다 크므로
벡터의 크기 + 1인 7부터 8까지 점화식을 진행해주면 점화식을 알 수 있다.