문제 링크

성능 요약

메모리: 14232 KB, 시간: 108 ms

분류

다이나믹 프로그래밍

제출 일자

2025년 1월 27일 17:43:49

문제 설명

정수 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의 합으로 나타내는 방법의 수를 출력한다.

풀이

느낀점

• DP를 너무 못한다고 느껴서 공부할겸 낮은 난이도부터 풀어보자 했는데, 너무 어려워서 충격이었다.
• 그냥 난이도 낮아도 DP는 다양하게 풀어보고 좀 더 풀이 방향을 잡는 연습을 해야겠다.
• 점화식을 한번에 쓰려고 하지말고, 시행착오를 겪더라도 직접 규칙을 찾아내는 연습을 해야한다.

설계 : 40분 - 참고함

• 분기 나누기 : 1, 2, 3 각 수를 더해 특정 수(S)를 만드는 경우의 수를 생각한다.
• S - 1 를 만들기 위한 경우의 수, S - 2를 만들기 위한 경우의 수, S - 3을 만들기 위한 경우의 수를 모두 더하면 1, 2, 3을 사용해 S를 표현하는 경우의 수를 알 수 있다.
• 즉, dp[i] = dp[i-1] + dp[i-2] + dp[i-3]

코드(Java)

• 구현 시간: 10분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 1 2 3 더하기_9095
 * Date: 2025.01.27
 */

import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		int[] dp = new int[11];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        for (int i = 4; i <= 10; i++) {
            dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        }

        int n = Integer.parseInt(br.readLine());
        for (int i = 0; i < n; i++) {
            int num = Integer.parseInt(br.readLine());
            bw.write(String.valueOf(dp[num]) + "\n");
        }

		bw.flush();
		bw.close();
		br.close();
	}
}