백준 9461번 C++ 파도반 수열

파도반 수열

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

생각하는 과정

그냥 나열해 보면 된다.

규칙은 바로 보이는데 이게 맞나 싶어서 계속 나열해 보았다.

1

1 ->1

1 1 ->1

1 1 1->1+1

1 1 1 2->1+1

1 1 1 2 2->1+2 4차이

1 1 1 2 2 3->1+3 4차이

1 1 1 2 2 3 4->1+4 4차이

1 1 1 2 2 3 4 5->2+5 4차이

1 1 1 2 2 3 4 5 7->2+7 4차이

1 1 1 2 2 3 4 5 7 9->3+9 4차이

1 1 1 2 2 3 4 5 7 9 12->4+12 4차이...

1 1 1 2 2 3 4 5 7 9 12 16->5+16

1 1 1 2 2 3 4 5 7 9 12 16 21->7+21

1 1 1 2 2 3 4 5 7 9 12 16 21 28->9+28

이렇게 나열하다 보면 dp[j]=dp[j-1]+dp[j-5]라는 결론이 나온다.

쪼금 치사한 것 같지만 5항까지는 일일히 나열해주자.

j-5항을 반복해서 더해야 하는 조건이 있기 때문.

느낌상 숫자의 범위 때문인 것 같았다.

역시나 게시판에 검색해보니 long으로 해서 해결했다는 사람이 있었고

dp 배열의 자료형을 long으로 고쳐보았다

???

long long으로 고쳐보았다

int의 범위는 2147483647까지

long의 범위도 똑같다(바보짓 한 것)

unsigned long 4294967295까지(0~)

long long의 범위는 int의 범위와 비교도 안 됨

http://melonicedlatte.com/algorithm/2018/03/04/022437.html

이 분 블로그 가면 자세하게 나와 있다.

ㄹㅇ 내가 맞은 것 같은데 왜 넣자마자 틀리는 건가! 싶으면

범위가 더 넓은 자료형으로 바꿔보자

코드

#include <iostream>
using namespace std;
int main() {
    int T, N;
    cin>>T;
    for(int i=0; i<T; i++) {
        cin>>N;
        long long dp[101];
        dp[0]=dp[1]=dp[2]=dp[3]=1, dp[4]=dp[5]=2;
        for(int j=6; j<=N; j++) {
            dp[j]=dp[j-1]+dp[j-5];
        }
        cout<<dp[N]<<"\n";
    }
    return 0;
}