백준 9095번
https://www.acmicpc.net/problem/9095
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.
3
4
7
10
7
44
274
이 문제는 동적계획법을 사용해서 푸는 문제이다
조금 더 정확히 말하면 Memoization을 사용해서 풀었다.
Memoization[] 배열을 만들어서 순차적으로 아래쪽의 작은 문제를 해결해서 위로 올라가서 큰 문제를 해결하는 방식을 선택했다
int T = Integer.parseInt(br.readLine());
int memoization[] = new int[11];
memoization[1] = 1;
memoization[2] = 2;
memoization[3] = 4;
먼저 테스트케이스의 값을 받을 변수 T
를 만들어주고
memoization[]
배열을 만든다 우리는 여기서 1과 2, 3 이 3가지 숫자를 통해서 숫자를 만들어야 하기때문에 뭔저 이 1 2 3에 대한 조합의 숫자를 기록해 둔다.
숫자 4의 경우 조합의 경우의 수가 7이 나오는데, 이 조합은
1의 조합 수, 2의 조합 수, 3의 조합 수를 더한 합이 된다.
즉, 이 방식을 통해서 우리가 문제를 해결하면, 큰 수도 같은 방식의 반복이므로
아래 쪽 부터 문제를 해결한다고 보면된다.
while(T--> 0) {
int num = Integer.parseInt(br.readLine());
if(memoization[i] == 0) {
memoization[i] = memoization[i - 1] + memoization[i - 2] + memoization[i - 3];
}
else {
continue;
}
sb.append(memoization[num]+"\n");
위에서 말한 것 처럼 원하는 숫자의 조합 수를 보려면 아래쪽 조합의 숫자 들의 합이므로 해당 결과 값을 저장할 수 있는 memoization[]
배열에 저장한다.
그리고 해당 값에 도달 했을 때,
StringBuilder에 붙여서 결과값으로 출력하기 위해 저장한다.
import java.io.*; public class Main { public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); int T = Integer.parseInt(br.readLine()); int memoization[] = new int[11]; memoization[1] = 1; memoization[2] = 2; memoization[3] = 4; while(T--> 0) { int num = Integer.parseInt(br.readLine()); if(memoization[i] == 0) { memoization[i] = memoization[i - 1] + memoization[i - 2] + memoization[i - 3]; } else { continue; } sb.append(memoization[num]+"\n"); } System.out.println(sb); } // End of main } // End of class