BJ9461 파도반 수열

풀이

n번째에 붙게되는 정삼각형의 한 변의 길이는 n-1번째의 최대 길이이다.

길이는 6각형의 각 변의 길이로 경우의 수를 나눌 수 있다고 생각하였다.

1. 0번째는 0, 1번째는 1을 기록해두고 1번째 6가지 변에 0,1,0,1,0,1을 담는다

   (한개의 정삼각형이 있는 경우 6가지 변의 길이.)

2. n번째 경우의 수에 대한 메모를 확인한다.

   1. 메모가 되어있지 않다면 n-1번째 경우의 수가 메모가 되어있는지 확인한다.

      1. 메모가 되어있지 않다면 재귀함수를 이용해 거기 먼저 메모하도록 한다.
      2. 메모가 되어있다면 n-1번째 6가지 변이 기록되어 있다는 것을 의미하므로 그 중 가장 긴 변을 찾아 n번째에 기록하고 n번째 6가지 변을 update한다.

   2. 메모가 되어 있다면 메모를 리턴한다.

      (1번째는 1이 기록되어있고 6가지 변이 모두 담겨있기 때문에 재귀함수의 기저조건이 된다.)

코드

//! 2020.03.12
// TODO BJ9461_파도반수열
#include<cstdio>
using namespace std;

const int MAX = 105;
long long DP[MAX];
long long P[MAX][6];
int N,T;

int findMax(int n){
    int idx = -1;
    long long maxVal = -1;
    for(int i=0;i<6;i++){
        if(P[n][i]>maxVal){
            idx = i;
            maxVal = P[n][i];
        }
    }
    return idx;
}

long long getResult(int n){
    long long& ret = DP[n];
    if(ret!=-1) return ret;

    if(DP[n-1]==-1){
        getResult(n-1);
    }

    int nextSide = findMax(n-1);
    ret = P[n-1][nextSide];

    for(int i=0;i<6;i++)
        P[n][i] = P[n-1][i];

    int idx1 = (nextSide+1)%6;
    int idx2 = (nextSide+5)%6;

    P[n][idx1] += ret;
    P[n][idx2] += ret;
    P[n][nextSide] = 0;

    // printf("N : %d\n",n);
    // for(int i=0;i<6;i++) printf("%d ",P[n][i]);
    // printf("\n");

    return ret;
}

int main(){
    scanf("%d",&T);
    for(int i=0;i<MAX;i++) DP[i] = -1;
    DP[0] = 0;
    DP[1] = 1;
    for(int i=1;i<=5;i+=2) P[1][i] = 1;

    for(int t=0;t<T;t++){
        scanf("%d",&N);
        printf("%lld\n",getResult(N));
    }
    return 0;
}

실수

1. 재귀함수의 기저조건과 함수의 기능을 명확히 규정하지 않고 코드를 구현했더니 굉장히 많이 꼬였다.
2. 자료형의 범위가 100번째 넘어가면 int를 훨씬 넘을 수 있다는 사실을 생각하지 못하고 자료형을 잘못 사용해 오답이 발생했다.