문제
https://www.acmicpc.net/problem/15989
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다.
- 1+1+1+1
- 2+1+1 (1+1+2, 1+2+1)
- 2+2
- 1+3 (3+1)
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 10,000보다 작거나 같다.
출력
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.
풀이
접근방법
시간제한 1초, 메모리 512MB이다.
(1 ≤ N ≤ 1,0000)
테스트 케이스의 개수가 명확하게 주어져 있지 않고, 1초, 512MB라는 조건(시간은 짧고 메모리가 많이 넉넉한 경우)에서 DP가 아닐까라는 의심을 품고 시작하자.
점화식을 찾는 과정이 매우 오래 걸렸다.
일단 한 번 쭉 살펴보자.
N : 전체 경우의 수 / 방법들...
1 : 1 / 1
2 : 2 / 1+1 2
3 : 3 / 1+1+1 2+1 3
4 : 4 / 1+1+1+1 2+1+1 2+2 3+1
5 : 5 / 1+1+1+1+1 2+1+1+1 2+2+1 3+1+1 3+2
6 : 7 / 1+1+1+1+1+1 2+1+1+1+1 2+2+1+1 2+2+2 3+1+1+1 3+2+1 3+3
7 : 8 / 1+1+1+1+1+1+1 2+1+1+1+1+1 2+2+1+1+1 2+2+2+1 3+1+1+1+1 3+2+1+1 3+2+2 3+3+1
*/N을 만들 때, N-1, N-2, N-3의 계산 결과와 동일한 것들이 있는 것을 발견해야 한다.
N=4인 경우를 생각해보자.
- K로 시작해서 K보다 같거나 작은 수를 이용해서 수식을 만든다고 생각한다.
( 수의 순서만 다른 것은 같은 것으로 친다. 라는 조건이 있기때문)
1. 1로만 4를 만드는 경우.
a. 1로만 만드는 경우는 N-1을 1로 만드는 경우의 수와 같다.
2. 1,2를 포함해서 4를 만드는 경우.
a. 식에 2를 포함시키겠다는 경우 이므로, 즉, N-2를 만드는 경우의 수에 2를 더한것이다
2를 만드는 경우의 수인 (1+1, 2) 에 2를 추가시킨 (1+1+2, 2+2)
3. 1,2,3을 포함해서 4를 만드는 경우.
a. 식에 3을 포함시키겠다는 경우 이므로, 즉, N-3를 만드는 경우의 수에 3을 더한것이다
1를 만드는 경우의 수인 (1) 에 1를 추가시킨 (1+3)즉, 전체 방법의 수 =
N을 1로 시작하여 1이하의 수를 이용해 만드는 방법의 수 +
N을 2로 시작하여 2이하의 수를 이용해 만드는 방법의 수 +
N을 3으로 시작하여 3이하의 수를 이용해 만드는 방법의 수
arr[i][j] : i라는 수를 만들기 위해 j이하의 수를 사용해 만든 방법의 수.
arr[i][1] = arr[i - 1][1];
arr[i][2] = arr[i - 2][1] + arr[i - 2][2];
arr[i][3] = arr[i - 3][1] + arr[i - 3][2] + arr[i - 3][3];
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class Main {
static int N, M;
static StringBuilder sb;
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int[][] arr = new int[10001][4];
arr[1][1] = 1;
arr[2][1] = 1;
arr[2][2] = 1;
arr[3][1] = 1;
arr[3][2] = 1;
arr[3][3] = 1;
for (int i = 4; i <= 10000; ++i) {
arr[i][1] = arr[i - 1][1];
arr[i][2] = arr[i - 2][1] + arr[i - 2][2];
arr[i][3] = arr[i - 3][1] + arr[i - 3][2] + arr[i - 3][3];
}
sb = new StringBuilder();
int T = stoi(in.readLine());
for (int tc = 0; tc < T; ++tc) {
N = stoi(in.readLine());
int sum = arr[N][1] + arr[N][2] + arr[N][3];
sb.append(sum).append("\n");
}
System.out.println(sb);
}
private static int stoi(String s) {
return Integer.parseInt(s);
}
}