[백준] no9461: 파도반 수열 (DP)

문제

주어진 파도반 수열에서, N번째 수를 구하시오

*파도반 수열 : 삼각형을 시계방향으로 돌아가면서 붙이는 정삼각형의 한 변의 길이를 인접한 두 삼각형의 변의 길이 합으로 정하는 수열

---

원리

방법1. 목표지점의 수 = 목표지점-1번째  +  목표지점 -5번째  -> 백준 문제에서는 안됨

방법2. 목표지점의 수 = 목표지점-2번째  +  목표지점 -3번째  -> 백준 문제 풀이는 이걸로 해야됨

---

풀이방법

예를 들어, 1,1,1,2,2,3,4,5,7,9,12,16,21,... 일때,

방법1.

1,1,1,2,2 까지는 기본 전제로 두고,
N이 5이하일 때는 기본 숫자에서 반환.
N이 6일 때, 2+1=3
N이 13일 때, 16+5=21

방법2.

첫 번째부터 시작하여,
1+1=2 는 한 칸 건너 4번째에 입력
1+1=2 는 한 칸 건너 5번째에 입력
1+2=3 은 한 칸 건너 6번째에 입력
...
7+5=12 는 한 칸 건너 12번째에 입력

 * 주의할 점 : N은 100까지이므로 int도 상관 없지만, 100일 때, P(N)은 int 범위를 넘어가므로 Long 타입을 사용해야한다.

---

나의 코드

1번 방법 풀이 [반복 DP]

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    int T = Integer.parseInt(br.readLine());

    for(int i=0; i<T ; i++) {
        List<Long> list = new ArrayList<>();
        list.add(0L);
        list.add(1L);
        list.add(1L);
        list.add(1L);
        list.add(2L);
        list.add(2L);

        int N = Integer.parseInt(br.readLine());

        if(N<=5) bw.write(""+list.get(N)+"\n");
        else {
            for(int j=5;j<N ; j++ ) list.add(list.get(j) + list.get(j-4));
            bw.write(""+list.get(N)+"\n");
        }
    }
    bw.close();
}

2번 방법 풀이 [반복 DP]

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    int T = Integer.parseInt(br.readLine());
    for(int i=0; i<T ; i++) {
        int N = Integer.parseInt(br.readLine());
        List<Long> list = new ArrayList<>();
        list.add(0L);
        list.add(1L);
        list.add(1L);

        if(N<3) bw.write(""+list.get(N)+"\n");
        else {
            for (int j = 0; j <= N - 3; j++) {
                Long next = list.get(j) + list.get(j + 1);
                list.add(next);
            }
            bw.write(""+list.get(N)+"\n");
        }
    }
    bw.close();
}

---

레퍼런스 코드

DP [재귀 DP]

private static Long[] arr = new Long[101]; // 최대 N은 100이므로

public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    arr[0] = 0L;
    arr[1] = 1L;
    arr[2] = 1L;
    arr[3] = 1L;
    int T = Integer.parseInt(br.readLine());

    while(T-->0) {
        bw.write(""+padovan(Integer.parseInt(br.readLine()))+"\n");
    }
    bw.close();
}

private static Long padovan(int N) {
    if(arr[N] == null) arr[N] = padovan(N-2) + padovan(N-3);
    return arr[N];
}

참고 링크 : https://st-lab.tistory.com/127