백준 9461 파도반 수열

9461번: 파도반 수열Baekjoon Online Judge

Solution 1. memoization

• 14220 kb / 124 ms

• 수열을 적다보니, 1-5까지의 수 이후부터는 p(n) = p(n-1) + p(n-5) 라는 규칙을 발견했다.

• 그대로 재귀함수를 작성했고, cache 배열에 memoization 방식으로 캐싱을 적용하여 반복 연산이 되지 않도록 하였다.

• 그러나, 최초에 int[] cache 의 타입을 int 로 설정했더니, 틀렸다는 결과값이 나왔다. 알고리즘 상 오류가 있는 줄 알고 살펴보다가, N의 범위가 1부터 100까지로 한정되어있다는 것을 보고 long[] 타입으로 바꾸어보았더니, 성공했다.

package practice.algorithm.dp;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

/**
 * https://www.acmicpc.net/problem/9461
 * 파도반수열
 * - memoization 방식
 * */
public class Bj9461 {
    private static long[] cache;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        while (t > 0) {
            t--;

            int n = Integer.parseInt(br.readLine());
            cache = new long[n+1];
            Arrays.fill(cache, -1);

            long result = p(n);
            sb.append(result).append("\n");
        }

        System.out.println(sb);
    }

    private static long p(int n) {
        if (cache[n] > -1) {
            return cache[n];
        }

        if (n <= 3) {
            cache[n] = 1;
            return 1;
        }

        if (n == 4 || n == 5) {
            cache[n] = 2;
            return 2;
        }

        cache[n] = p(n-1) + p(n-5);
        return cache[n];
    }


    /**
     * 규칙찾기
     * 1
     * 1
     * 1
     * 2 = 1+1
     * 2
     * 3 = 2+1
     * 4 = 3+1
     * 5 = 4+1
     * 7 = 5+2
     * 9 = 7+2
     * 12 = 9+3
     * 16 = 12+4
     * 21 = 16+5
     * p(1)~p(5) = 1, 1, 1, 2, 2
     * p(n) = p(n-1) + p(n-5)
     * */
}

Solution 2. bottomup

• 14176 kb / 124 ms

• 같은 문제를 bottom-up 방식으로도 바꾸어 풀어보았다.

• 이 방식에서는 N값의 범위가 1부터 100까지로 한정되어있다는 것을 염두해두어 cache 배열의 크기를 고정하도록 처리하였다. 1부터 5까지의 값이 입력되는 N값에 좌지우지되지 않도록 배열 크기를 고정시켰다.

package practice.algorithm.dp;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.lang.reflect.Array;
import java.util.Arrays;

/**
 * https://www.acmicpc.net/problem/9461
 * 14176 kb / 124 ms
 * 파도반수열
 * - bottom-up 방식
 * */
public class Bj9461_2 {
    private static long[] cache;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();
        while (t > 0) {
            t--;

            int n = Integer.parseInt(br.readLine());
            cache = new long[101];
            Arrays.fill(cache, -1);

            long result = p(n);
            sb.append(result).append("\n");
        }

        System.out.println(sb);
    }

    private static long p(int n) {
        cache[1] = cache[2] = cache[3] = 1;
        cache[4] = cache[5] = 2;

        for (int i = 6; i <=n; i++) {
            cache[i] = cache[i-1] + cache[i-5];
        }

        return cache[n];
    }


    /**
     * 규칙찾기
     * 1
     * 1
     * 1
     * 2 = 1+1
     * 2
     * 3 = 2+1
     * 4 = 3+1
     * 5 = 4+1
     * 7 = 5+2
     * 9 = 7+2
     * 12 = 9+3
     * 16 = 12+4
     * 21 = 16+5
     * p(1)~p(5) = 1, 1, 1, 2, 2
     * p(n) = p(n-1) + p(n-5)
     * */
}