[백준][JAVA] - 1, 2, 3 더하기(9095)
문제 소개
🥈 문제 레벨 : 실버3
🔔 문제 유형 : 다이나믹 프로그래밍
💬 풀이 언어 : JAVA
⏱️ 풀이 시간 : 30분
🖇️ 문제 링크 : 백준 문제 링크
📝 문제
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.
1+1+1+1
1+1+2
1+2+1
2+1+1
2+2
1+3
3+1
정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
🤔 문제 분석
문제에서 언급한 것과 같이 1, 2, 3만을 사용해서 값을 표현할 수 있는 경우의 수를 구해야 한다.
0부터 3까지 각각 사용할 수 있는 경우의 수를 확인해보면 아래와 같다.
| 구분 | 경우의 수 | 조합 |
|---|---|---|
| 1 | 1개 | 1 |
| 2 | 2개 |
1 + 1 / 2
|
| 3 | 4개 |
1 + 1 + 1 / 1 + 2 / 2 + 1 / 3
|
1, 2, 3을 이용해 4를 만들 수 있는 경우의 수를 보면 아래와 같다.
- 1을 이용한 조합 : 1개
- 2을 이용한 조합 : 2개
- 3을 이용한 조합 : 4개
4 + 2 + 1로 총 7개의 경우의 수로 구할 수 있다.
5의 경우를 보면 아래로 나눌 수 있다.
- 2을 이용한 조합 : 2개
- 3을 이용한 조합 : 4개
- 4를 이용한 조합 : 7개
즉, (n - 3) + (n - 2) + (n - 1)을 통해 값을 구할 수 있다.
1, 2, 3에 대한 값이 필요하므로 미리 값을
메모제이션(memoization)을 한 뒤, 풀이해야 한다.
😎 최종 코드
메모리 : 11480 KB
시간 : 76 ms
import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
public class Main {
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());
int[] dp;
while (T-- > 0) {
int n = Integer.parseInt(br.readLine());
// n의 값은 11 미만이라고 되어있기 때문에 11로 초기화
dp = new int[11];
dp[0] = 0;
dp[1] = 1;
dp[2] = 2;
dp[3] = 4;
for (int i = 4; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
}
bw.append(dp[n] + "\n");
}
bw.flush();
bw.close();
br.close();
}
}
댓글남기기