{% embed url=“https://www.acmicpc.net/problem/9461” %}
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) * */}
Java
복사
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) * */}
Java
복사