[ 백준 9461 ] 파도반 수열 (C++)

백준의 파도반수열(9461) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

작은 정삼각형부터 그려가면서 하나의 규칙을 한번 찾아보자.

지금부터 간단하게 표시하기 위해서 F[a] = b 라는 표현을 사용할 것이다.

F[a] = b의 의미는 "a번째 정삼각형의 한 변의 길이는 b입니다." 를 의미한다.

즉, F[1] = 1 일 것이다.

그럼 첫 번째 정삼각형부터 그려보자.

.

말할 필요없이 F[1] = 1 이라는 것을 문제에서도 제시해주었으므로, 바로 알 수 있다.

F[1] = 1

두 번째 정삼각형을 한번 그려보자. 문제에서 제시된 그림을 참고해서 그려보면 다음과 같이 정삼각형이 추가된다.

.

두 번째 삼각형이 저렇게 아래에 붙는 꼴로 만들어진다. F[2] = 1 이다.

F[1] = 1 , F[2] = 1

세 번째 삼각형도 그려보면 다음과 같이 정삼각형이 추가된다.

.

F[1] = 1 , F[2] = 1 , F[3] = 1

네 번째 정삼각형 부터는 크기가 커지게 된다.

.

이렇게 삼각형이 붙게 되는데 , 여기서 4번 정삼각형의 한 변의 길이를 보면 , 1번 삼각형의 한 변의 길이와 3번 삼각형의 한 변의 길이를 더한 길이를 갖는다는 것을 알 수 있다.

그럼 확실한건 아니지만 한번 예상을 해보자. F[N] = F[N - 1] + F[N - 3] 이라고 !

F[1] = 1 , F[2] = 1 , F[3] = 1 , F[4] = 2

이제 다섯번째 정삼각형을 그려보자.

.

5번 삼각형은 다음과 같이 추가된다. 그럼 우리가 4번 정삼각형을 구할 때 구했던 식으로 적용이 되는지 확인해보자.

먼저 결론부터 말해보면, F[5] = 2 이다. 그런데 위의 공식을 적용시켜보면 F[5] = F[4] + F[2] 가 되고 이는 2 + 1 = 3 으로 올바른 공식이 아닌 것을 확인할 수 있다. 그럼 계속해서 그려나가 보자.

F[1] = 1 , F[2] = 1 , F[3] = 1 , F[4] = 2 , F[5] = 2

여섯번째 정삼각형을 그려보자.

.

6번 정삼각형의 한 변의 길이를 보면 , 5번 정삼각형과 3번 정삼각형의 변의 길이들의 합으로 이루어져 있는데, 하지만

우리는 F[N] = F[N - 1] + F[N - 3] 은 정확한 식이 아니라는 것을 알고 있다.

F[6] = 3 이라는 것 정도만 알고 넘어가자.

F[1] = 1 , F[2] = 1 , F[3] = 1 , F[4] = 2 , F[5] = 2 , F[6] = 3

일곱번째 정삼각형을 그려보자.

.

7번 정삼각형을 보게 되면 , 6번 정삼각형의 한 변의 길이 + 2번 정삼각형의 한 변의 길이가 한 변의 길이가 되어서 길이가 4인 정삼각형을 만들고 있다.

여덟번째 정삼각형을 그려보자.

.

8번 정삼각형을 보게 되면, 7번 정삼각형의 한 변의 길이 + 1번 정삼각형의 길이가 되어서 총 길이가 5인 정삼각형을 이루고 있다.

F[1] = 1 , F[2] = 1 , F[3] = 1 , F[4] = 2 , F[5] = 2 , F[6] = 3 , F[7] = 4 , F[8] = 5

마지막으로 아홉번재 정삼각형까지만 그려보자.

.

이렇게 정삼각형이 추가된다. 9번 정삼각형의 한변의 길이는 8번 정삼각형의 한 변의 길이 + 4번 정삼각형의 한 변의 길이가 되어서 총 길이가 10 인 정삼각형을 이루고 있다.

그럼 ! 여기서 그만그리고 규칙을 한번 찾아보자.

글을 읽으면서 중간중간에 굵은 글씨로 표시되어 있는 글들이 몇 개 있었다. 다시 스크롤을 위로 올려서 확인해보면 알겠지만,

1 ~ 5 번 정삼각형들에는 굵은 글씨가 없는데 , 6 ~ 9번 정삼각형들에 대해서는 굵은 글씨들이 존재한다.

바로 ! 그 굵은 글씨들이 규칙이다.

다시 6 ~ 9 번 정삼각형들만 정리를 한번 해보자.

6번 정삼각형 = 5번 정삼각형의 한변의 길이 + 3번 정삼각형의 한변의 길이(1)

7번 정삼각형 = 6번 정삼각형의 한변의 길이 + 2번 정삼각형의 한변의 길이(1)

8번 정삼각형 = 7번 정삼각형의 한변의 길이 + 1번 정삼각형의 한변의 길이(1)

9번 정삼각형 = 8번 정삼각형의 한변의 길이 + 4번 정삼각형의 한변의 길이(2)

그런데 ! 위에서 빨강색 글씨로 표현된 부분들을 다시한번 잘 보면... 파도반 수열을 이루고 있다는 것을 확인할 수 있다.

확인을 더 하고 싶으면 각자 더 많은 정삼각형들을 그려보면서 확인해보면, 파도반 수열이라는 것을 확인할 수 있을 것이다.

즉 ! 위의 정삼각형들을 다시 적어보면

F[6] = F[5] + 1

F[7] = F[6] + 1

F[8] = F[7] + 1

F[9] = F[8] + 2

F[10] = F[9] + 2

이런식으로 진행될 것이다. 그럼 위의 식을 일반화 시켜보자.

5번 정삼각형까지는 규칙이 존재하지 않는다. 규칙은 6번 정삼각형부터 적용된다. 다음과 같이 !

F[N] = F[N - 1] + F[N - 5] !

위와 같은 규칙이 존재하게 된다.

따라서 이를 점화식으로 해서 정답을 도출할 수 있다.

[ 소스코드 ]

#include <iostream>
 
#define endl "\n"
#define MAX 110
using namespace std;
 
int N;
long long DP[MAX];
 
void Input()
{
    cin >> N;
}
 
void Solution()
{
    DP[1] = DP[2] = DP[3] = 1;
    DP[4] = DP[5] = 2;
    for (int i = 6; i <= N; i++)
    {
        DP[i] = DP[i - 1] + DP[i - 5];
    }
    cout << DP[N] << endl;
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Input();
        Solution();
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}