[BOJ]1,2,3더하기 4(15989)

www.acmicpc.net/problem/15989

15989번: 1, 2, 3 더하기 4

난이도 - 실버1

시간 제한메모리 제한제출정답맞은 사람정답 비율

1 초 (추가 시간 없음)

512 MB

2126

1378

1056

66.541%

문제

정수 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

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main{
    static int T, M;

    static List<Integer> list;
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        st = new StringTokenizer(br.readLine());
        T = Integer.parseInt(st.nextToken());
        list = new ArrayList<>();
        int max = 0;
        for(int i =0; i< T; i++){
            st = new StringTokenizer(br.readLine());
            M = Integer.parseInt(st.nextToken());
            list.add(M);
            max = max>M? max:M;
        }
        int[][] dp = new int[max+1][3];
        dp[1][0]=1;
        dp[2][0]=1;dp[2][1]=1; 
        dp[3][0]=1;dp[3][1]=1;dp[3][2]=1;

        for(int i =4; i<= max; i++){
            dp[i][0] = dp[i-1][0];
            dp[i][1] = dp[i-2][0] + dp[i-2][1];
            dp[i][2] = dp[i-3][0] + dp[i-3][1] + dp[i-3][2];
        }
        for(int a:list){
            System.out.println(dp[a][0]+dp[a][1]+dp[a][2]);
        }

    }

}

풀이

  간단히 조합을 생각하지 않으면 dp[i] +=dp[i-1]+dp[i-2]+dp[i-3]을 하면된다.

 하지만 조합을 생각해야 하기 때문에 생각을 조금 다르게 해봐야 한다.

 

조합을 하는 법은 1은 i-1의 1로 이루어진 것에 1을 i에 더하는 것 2는 i-2의 1로이루어진 것과 2로 이루어진 것을 더하는 것 3은 i-3의 1, 2, 3으로 이루어진것에 3을 더하는 것

 즉 마지막에 각 1,2,3으로 이루어지도록 조합을 만드는 것이다. 이때 모든 수는 오름차순으로 이루어 진다는 것을 염두해 두면 dp[n][0]는 무조건 1이 된다.

dp[n][1]은 1로 이루어 진 수와 2로 이루어진 수를 더하면 된다. 3으로 이루어진 수를 더하면 오름차순이 안되기 때문이다.

 

따라서 위와 같은 식이 나온다.