728x90
| 1 초 (추가 시간 없음) | 512 MB | 114351 | 75419 | 52026 | 64.454% |
문제
정수 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의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 11보다 작다.
출력
각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력한다.
예제 입력 1
3
4
7
10
예제 출력 1
7
44
274
풀이✔
1️⃣ 문제 분석하기
- 정수 n이 주어질 때, n을 1,2,3의 합으로 나타내는 방법의 수를 구해야함
- 숫자는 1,2,3 만 사용을 해야함.
2️⃣ 요구 조건 구현하기
- 테스트 케이스의 개수 T가 주어짐
- 정수 n이 주어지며, n은 양수고, 11보다 작다.
- n에 따른 총 경우의 수를 출력한다.
3️⃣ 슈도 코드
BufferedReader 생성
int T = BufferedReader 입력
수를 입력받을 배열 생성
최종 값을 입력받을 배열 생성
for(T개수 입력) {
배열 입력받기
동시에 최종 값 입력받기
}
for(출력) {
최종값 입력 받기
}
count()메소드 {
조건을 처리할 로직 작성
}
4️⃣ 코드 작성
package Algorithm.DP;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class B9095 {
public static void main(String[] args) throws IOException {
//3시52분 시작
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
int[] arr = new int[T];
int[] sumArr = new int[T];
for (int i = 0; i <T ; i++) {
arr[i] = Integer.parseInt(br.readLine());
sumArr[i] = Count(arr[i]);
}
for (int i = 0; i <T; i++) {
System.out.println(sumArr[i]);
}
}
private static int Count(int n) {
int[] dp = new int[n + 1];
dp[1] = 1;
if (n >= 2) dp[2] = 2; //각 배열마다 그 인덱스에 맞는, 경우의 수를 넣는다.
if (n >= 3) dp[3] = 4; //각 배열마다 그 인덱스에 맞는, 경우의 수를 넣는다.
//우리는 숫자를 1,2,3만 사용해야 하니 조건은 3까지 경우의 수로 제한한다.
//그렇게 해서 쭉 각 수마다 1,2,3,으로 만들 수 있는 합의 경우의 수를 저장하고 마지막에 최종적으로 더해서 n에 맞는 총 경우의 수를 구하는 로직이다.
//i가 4인 이유는 dp배열은 이미0,1,2,3 인덱스가 꽉차 있다. 그러므로 4부터 시작한다. 이것을 사용하기 위해서 처음 배열에 n+1을 해준 것 이다.
//만약 문제에 숫자,1,2,3,4 4가지를 이용하라고 했다면 위에 if조건에 4까지 들어가고, for문은 5부터 시작했을 것이다.
for (int i = 4; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
//문제가 1,2,3의 활용하여 문제를 찾는 것 이기 때문에 1,2,3을 빼고 위 수들을 배열의 합을 구하는 것이다.
//배열로 하기 싫다면 재귀함수를 이용해도 된다.
}
return dp[n];
}
}
🚨 주요 로직
private static int Count(int n) {
int[] dp = new int[n + 1];
if(n>=1) {
dp[1] = 1;
}
if (n >= 2) {
dp[2] = 2;
}
if (n >= 3) {
dp[3] = 4;
}
for (int i = 4; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
}
return dp[n];
}- int[] dp = new int[n + 1];
- n+1을 한 이유는, dp배열안이 n으로 만하면 0부터 시작하여 한개의 숫자가 모자르기 때문에 +1을 하여, 0을 포함한 1자리를 더 넣는다.
- if(n ≥1) { dp[1] = 1; } if (n >= 2) { dp[2] = 2; } if (n >= 3) { dp[3] = 4; }
- 위 로직은 문제가 1,2,3으로 만 n에 수 합을 만드는 경우의 수 찾는거 이기 때문에 1,2,3으로 만들 수 있는 경우의 수를 미리 찾아서 dp배열 안에 저장을 해둔다.
- 즉, dp 배열마다 그 인덱스에 맞는, 경우의 수 합을 넣는다.
- 문제에서 숫자를 1,2,3만 사용한다 했음으로, 조건은 3까지 경우의 수로 제한한다.
- 위 조건을 바탕으로 입력받는 n 마다 1,2,3,으로 만들 수 있는 합의 경우의 수를 저장하고 마지막에 최종적으로 더해서 n 에 맞는 총 경우의 수를 구하는 로직이다.
- for (int i = 4; i <= n; i++)
- for문 시작이 4인 이유는 dp배열은 이미 0,1,2,3 인덱스가 꽉 차 있다. 그러므로 4부터 시작한다. 이것을 사용하기 위해서 처음 배열에 n+1을 해준 것 이다.
- 만약 문제에 숫자,1,2,3,4 총 4개 숫자를 이용하라고 했다면 위에 if조건에 4까지 들어가고, for문은 5부터 시작했을 것이다.
🔔 젤 중요 로직 🚨
- dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3];
- 문제가 정수 1,2,3의 활용하여 경우의 수 를 찾는 것 이기 때문에 dp배열에서 1,2,3을 뺀 배열 인덱스의 값을 더하여 총 경우의 수를 구합니다.
- 배열로 하기 싫다면 재귀 함수를 이용해도 된다.
- 위 로직을 예시를 그림으로 보여드리겠습니다.
***초기상태***
dp[1] = 1
dp[2] = 2
dp[3] = 4
**n=4일때**
dp[4] = dp[3] + dp[2] + dp[1]
= 4 + 2 + 1
= 7
**n=5 일 때**
dp[5] = dp[4] + dp[3] + dp[2]
= 7 + 4 + 2
= 13
**n=6 일 때**
dp[6] = dp[5] + dp[4] + dp[3]
= 13 + 7 + 4
= 24
**n=7 일 때**
dp[7] = dp[6] + dp[5] + dp[4]
= 24 + 13 + 7
= 44
n=8 일 때
dp[8] = dp[7] + dp[6] + dp[5]
= 44 + 24 + 13
= 81
n=9 일 때
dp[9] = dp[8] + dp[7] + dp[6]
= 81 + 44 + 24
= 149
n=10 일 때
dp[10] = dp[9] + dp[8] + dp[7]
= 149 + 81 + 44
= 274
위 처럼 배열에 이미 계산되어 저장된 값을 누적하여 경우의 수를 구하는 입니다.
5️⃣ 궁금한 점
- DP(Dynamic Programming) 에 대하여 더 알아보고 싶다는 생각이 들었습니다.
- 다양한 문제를 경험하며 DP에 대한 이해도를 높이고자 함.
6️⃣ 핵심 파악하기
- 다이나믹 프로그래밍을 활용해야 한다.
- 재귀함수로도 문제를 풀 수는 있습니다만, 효율이 DP알고리즘보다 좋지 않다고 생각합니다.
728x90