백준 9095번 1,2,3 더하기 (자바) 풀이

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

1 초 (추가 시간 없음)

512 MB

91254

59805

40667

63.913%

문제

정수 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과 2와 3을 써서 각각 몇번을 사용해 해당 수가 나올 수 있는지~~~ 이딴건 다 필요없다.

 

문제에서 원하는 답만 가져다주면 된다는 뜻이다.

 

마찬가지로 문제에서 11보다 작은 수가 나온다고 했으니 11의 크기를 갖는 배열을 생성해준다.

 

그리고 이미 주어진 답들은 죄다 넣어놓아도 좋다.  

하지만 나는 가장 작은 경우의 수부터 위로 올라갈것이기 때문에

주어진 답중 가장 작은 수인 4에 대한 해답을 배열에 넣어놓고,

1 와 2와 3일때의 경우의 수만 직접 구해준다.

 

1일땐 1 하나만 더해지기 때문에 답은 1이 되고

2일땐 1+1 과 +2 가 되기때문에 2

3일땐 1+1+1 과 1+2 2+1 , +3 이 되기때문에 4가 된다.

4일땐 문제에서 알려주었으니 7..

 

오잉? 벌써 패턴이 보인다.

 

dp[N-3]+ dp[N-2] + dp[N-1]

하면 얼추 맞는것 같다.

 

그렇게 반복문을 한번 실행해보고 맞으면 바로 제출하면 된다.

 

참쉽죵?

 

package baekjoon.a9095;

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

public class a9095 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] dp = new int[11];
        dp[1]=1;
        dp[2]=2;
        dp[3]=4;
        dp[4]=7;
        for(int i=0; i<N;i++){
            int n = Integer.parseInt(br.readLine());
            for(int j=4; j<=n;j++){
                dp[j]=dp[j-3]+dp[j-2]+dp[j-1];
            }
            System.out.println(dp[n]);
        }
    }
}