문제 링크 : https://acmicpc.net/problem/15989
15989번: 1, 2, 3 더하기 4
정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 4가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 합을 이루고 있는 수의 순서만 다른 것은 같은 것으로 친다. 1+1+1+1 2+1+1 (1+1+2, 1+2+1) 2+2
www.acmicpc.net
문제
정수 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
3
4
7
10
예제 출력 1
4
8
14
풀이 방법
[1]
1
=> 1가지
(0가지 일 수도 있는지?...)
[2]
1 + 1
=> 1가지
[3]
1 + 1 + 1
2 + 1
=> 2가지
[4]
1 + 1 + 1 + 1
2 + 1 + 1 , 2 + 2
3 + 1
=> 4가지
[5]
1 + 1 + 1 + 1 + 1
2 + 1 + 1 + 1 , 2 + 2 + 1
3 + 1 + 1, 3 + 2
=> 5가지
[6]
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가지
[7]
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
=> 8가지
[8]
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
(2 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 1 + 1 + 1 + 1), (2 + 2 + 2 + 1 + 1), (2 + 2 + 2+ 2)
(3 + 1 + 1 + 1 + 1 + 1), (3 + 2 + 1 + 1 + 1), (3 + 2 + 2 + 1)
(3 + 3 + 1 + 1), (3 + 3 + 2)
=> 10가지
[9]
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
(2 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 2 + 1 + 1 + 1), (2 + 2 + 2+ 2 + 1)
(3 + 1 + 1 + 1 + 1 + 1 + 1), (3 + 2 + 1 + 1 + 1 + 1), (3 + 2 + 2 + 1 + 1), (3 + 2 + 2 + 2)
(3 + 3 + 1 + 1 + 1), (3 + 3 + 2 + 1)
(3 + 3 + 3)
=> 12가지
[10]
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
(2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 2 + 1 + 1 + 1 + 1), (2 + 2 + 2+ 2 + 1 + 1), (2 + 2 + 2+ 2 + 2)
(3 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (3 + 2 + 1 + 1 + 1 + 1 + 1), (3 + 2 + 2 + 1 + 1 + 1), (3 + 2 + 2 + 2 + 1)
(3 + 3 + 1 + 1 + 1 + 1), (3 + 3 + 2 + 1 + 1), (3 + 3 + 2 + 2)
(3 + 3 + 3 + 1)
=> 14가지
[11]
1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
(2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 2 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 2+ 2 + 1 + 1 + 1), (2 + 2 + 2+ 2 + 2 + 1)
(3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (3 + 2 + 1 + 1 + 1 + 1 + 1 + 1), (3 + 2 + 2 + 1 + 1 + 1 + 1), (3 + 2 + 2 + 2 + 1 + 1), (3 + 2 + 2 + 2 + 2)
(3 + 3 + 1 + 1 + 1 + 1 + 1), (3 + 3 + 2 + 1 + 1 + 1), (3 + 3 + 2 + 2 + 1)
(3 + 3 + 3 + 1 + 1), (3 + 3 + 3 + 2)
=> 16가지
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 0 | 0 | 1 | 2 | 4 | 5 | 6 | 8 | 10 | 12 | 14 |
6부터 2씩 증가-> fail!!!
==========================
dp[n,k] : 1,,,k 를 활용해 n을 만드는 방법의 수로 가정하고 각 값을 구해보자.
===========================================
dp[n,1]을 구해보자. |
dp[n,2]을 구해보자. |
dp[n,3]을 구해보자. |
|||
| 1 | 1 | dp[1,2] : 1, 2을 활용해 1을 만드는 방법의 수 1 |
1 | dp[1,3] : 1, 2, 3을 활용해 1을 만드는 방법의 수 1 |
1 |
| 1 + 1 | 1 | dp[2,2] : 1, 2를 활용해 2을 만드는 방법의 수 1 + 1 |
1 | dp[2,3] : 1, 2, 3을 활용해 2을 만드는 방법의 수 1 + 1 2 |
2 |
| 1 + 1 + 1 | 1 | dp[3,2] : 1, 2를 활용해 3을 만드는 방법의 수 1 + 1 + 1 2 + 1 |
2 = dp[3,1] + 1 | dp[3,3] : 1, 2, 3을 활용해 3을 만드는 방법의 수 1 + 1 + 1 2 + 1 3 |
3 |
| 1 + 1 + 1 + 1 | 1 | dp[4,2] : 1, 2를 활용해 4를 만드는 방법의 수 1 + 1 + 1 + 1 2 + 1 + 1 2 + 2 |
3 = dp[4,1] + 2 | dp[4,3] : 1, 2, 3을 활용해 4을 만드는 방법의 수 1 + 1 + 1 + 1 2 + 1 + 1 2+ 2 3 + 1 |
4 = dp[4,2] + 1 |
| 1 + 1 + 1 + 1 + 1 | 1 | dp[5,2] : 1, 2를 활용해 5를 만드는 방법의 수 1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 2 + 2 + 1 |
3 = dp[5,1] + 2 | dp[5,3] : 1, 2, 3을 활용해 5을 만드는 방법의 수 1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 2+ 2 + 1 3 + 1 + 1 3 + 2 |
5 = dp[5,2] + 2 |
| 1 + 1 + 1 + 1 + 1 + 1 | 1 | dp[6,2] : 1, 2를 활용해 6을 만드는 방법의 수 1 + 1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 + 1 2 + 2 + 1 + 1 2 + 2 + 2 |
4 = dp[6,1] + 3 | dp[6,3] : 1, 2, 3을 활용해 6을 만드는 방법의 수 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 = dp[6,2] + 3 |
| 1 + 1 + 1 + 1 + 1 + 1 + 1 | 1 | dp[7,2] : 1, 2를 활용해 7을 만드는 방법의 수 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 + 1 + 1 2 + 2 + 1 + 1 + 1 2 + 2 + 2 + 1 |
4 = dp[7,1] + 3 | dp[7,3] : 1, 2, 3을 활용해 7을 만드는 방법의 수 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 |
8 = dp[7,2] + 4 |
| 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 | 1 | dp[8,2] : 1, 2를 활용해 8을 만드는 방법의 수 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 1 + 1 + 1 + 1 2 + 2 + 2 + 1 + 1 2 + 2 + 2 + 2 |
5 = dp[8,1] + 4 | dp[8,3] : 1, 2, 3을 활용해 8을 만드는 방법의 수 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 1 + 1 + 1 + 1 2 + 2 + 2 + 1 + 1 2 + 2 + 2 + 2 3 + 1 + 1 + 1 + 1 + 1 3 + 2 + 1 + 1 + 1 3 + 2 + 2 + 1 3 + 3 + 1 + 1 3 + 3 + 2 |
10 = dp[8,2] + 5 |
| 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 | 1 | dp[9,2] : 1, 2를 활용해 9을 만드는 방법의 수 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 1 + 1 + 1 2 + 2 + 2 + 2 + 1 |
5 = dp[9,1] + 4 | dp[9,3] : 1, 2, 3을 활용해 9을 만드는 방법의 수 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 1 + 1 + 1 2 + 2 + 2 + 2 + 1 3 + 1 + 1 + 1 + 1 + 1 + 1 3 + 2 + 1 + 1 + 1 + 1 3 + 2 + 2 + 1 + 1 3 + 2 + 2 + 2 3 + 3 + 1 + 1 + 1 3 + 3 + 2 + 1 3 + 3 + 3 |
12 = dp[9,2] + 7 |
| 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 | 1 | dp[10,2] : 1, 2를 활용해 10을 만드는 방법의 수 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 1 + 1 2 + 2 + 2 + 2 + 2 |
6 = dp[10,1] + 5 | dp[10,3] : 1, 2, 3을 활용해 10을 만드는 방법의 수 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 1 + 1 2 + 2 + 2 + 2 + 2 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 3 + 2 + 1 + 1 + 1 + 1 + 1 3 + 2 + 2 + 1 + 1 + 1 3 + 2 + 2 + 2 + 1 3 + 3 + 1 + 1 + 1 + 1 3 + 3 + 2 + 1 + 1 3 + 3 + 2 + 2 3 + 3 + 3 + 1 |
14 = dp[10,2] + 8 |
| dp[15,2] 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 2 + 2+ 1 + 1 + 1 2 + 2 + 2 + 2 + 2 + 2+ 2+ 1 |
8 = dp[15,1] + 14 | dp[15,3] 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 2 + 2+ 1 + 1 + 1 2 + 2 + 2 + 2 + 2 + 2+ 2+ 1 ====== 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 3 + 2 + 1 + 1 + 1 + 1 + 1 + 1 3 + 2 + 2 + 1 + 1 + 1 + 1 3 + 2 + 2 + 2 + 1 + 1 3 + 2 + 2 + 2 + 2 3 + 3 + 1 + 1 + 1 + 1 + 1 3 + 3 + 2 + 1 + 1 + 1 3 + 3 + 2 + 2 + 1 3 + 3 + 3 + 1 + 1 3 + 3 + 3 + 2 |
18 | ||
| dp[20,2] 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 2 + 2+ 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 2 + 2+ 2+ 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 2 + 2+ 2+ 2 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 2 + 2+ 2+ 2 + 2 + 1 + 1 2 + 2 + 2 + 2 + 2 + 2+ 2+ 2 + 2+ 2 |
11 | dp[20,3] 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 2 + 2+ 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 2 + 2+ 2+ 1 + 1 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 2 + 2+ 2+ 2 + 1 + 1 + 1 + 1 2 + 2 + 2 + 2 + 2 + 2+ 2+ 2 + 2 + 1 + 1 2 + 2 + 2 + 2 + 2 + 2+ 2+ 2 + 2+ 2 ============== 3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 3 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 3 + 2 + 2 + 1 + 1 + 1 + 1 + 1 3 + 2 + 2 + 2 + 1 + 1 + 1 3 + 2 + 2 + 2 + 2 + 1 3 + 3 + 1 + 1 + 1 + 1 + 1 + 1 3 + 3 + 2 + 1 + 1 + 1 + 1 3 + 3 + 2 + 2 + 1 + 1 3 + 3 + 2 + 2 + 2 3 + 3 + 3 + 1 + 1 + 1 3 + 3 + 3 + 2 + 1 3 + 3 + 3 + 3 |
|||
- dp[n,1] = 1
- dp[n,2] = n/2(몫만) + 1
- dp[n-3] = dp[n-1, 1] +dp[n-2, 2] + dp[n-3, 3] = 1 + {(n-2)/2} + 1 + dp[n-3,3]
import java.util.Scanner;
public class BOJ_15989_123더하기4 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
int[][] dp= new int[10001][4];
for(int n = 0; n<=10000; n++){
dp[n][0] = 0;
dp[n][1] = 1;
dp[n][2] = n/2 + 1;
}
dp[1][2] = 1; dp[1][3] = 1;
dp[2][2] = 1; dp[2][3] = 2;
dp[3][2] = 2; dp[3][3] = 3;
dp[4][2] = 3; dp[4][3] = 4;
for(int i = 5; i<=10000; i++){
dp[i][3] = 2 + (i-2)/2 + dp[i-3][3];
}
int n;
for(int i = 0; i<T; i++){
n = sc.nextInt();
System.out.println(dp[n][3]);
}
}
}
'Algorithm(BOJ) > DP' 카테고리의 다른 글
| [Java] 백준 10164번 - 격자상의 경로(dp) (1) | 2023.11.13 |
|---|---|
| [Java] 백준 9251번 - LCS (0) | 2023.05.07 |
| [C++] 백준 2748번 - 피보나치 수2 (DP, 자료형 주의) (0) | 2021.08.17 |
| [C++] 백준 17069번 - 파이프 옮기기2 (DP, 3차원 배열) (0) | 2021.08.16 |
| [C++] 백준 10942번 - 팰린드롬? (DP, 다이나믹 프로그래밍) (0) | 2021.08.16 |