[DP_백준 9095번 문제_JAVA] 1, 2, 3 더하기

 

인생 두번째 알고리즘 문제 성공!🎇

아직까진 풀고나서 맞는지 아닌지 확신에 차진 않지만

 

다른 분들의 답을 보고 내가 생각하지 못한게 무엇인지를 파악하고 적용할 수 있는 정도가 되었다는 것도

하루만에 장족의 발전이라고 생각한다. 내일은 더 발전하자!🎈

 

---

문제풀이는 완벽하진 않지만 제가 이해한 방식으로 풀이 했습니다. 

코드를 보다가 더 좋은 방식이 있다면 피드백 주시면 정말 감사하겠습니다!🙏🏻

 

---

문제

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

 

---

일단 범위 내 모든 수에 적용되는 공통적인 규칙을 발견하기 위해 몇번 계산을 해 보았다.

 

 5 -> 1+ 4만드는방식
        2+ 3만드는방식
        3+ 2만드는방식

 4 -> 1 + 3만드는방식
        2 + 2만드는방식
        3 + 1
   
 3 -> 1 + 2만드는방식
        2 + 1
        3
 2 -> 1+1 , 2

 

4이상일 때에는 위와 같이 반복되는 것을 보고 아래와 같은 규칙을 도출할 수 있었다.

 

 n -> 1+ (n-1)만드는방식
        2+ (n-2)만드는방식
        3+ (n-3)만드는방식

 

위 규칙을 적용하여 TopDown 방식의 풀이로 코드를 작성해 보았다.

 

 

import java.util.Scanner;

public class Main{
	static int[]d;
	
	public static void main(String args[]){
		
		//문제에 주어졌으므로 미리 만들어 놓기
		d = new int[11];
		
		//알고 있는 초기값은 미리 세팅
		d[0]=1;
		d[1]=1;
		d[2]=2;
		d[3]=4;
		
		//1줄을 제외하고는 여러줄을 반복해서 받고 줘야하므로, 첫줄의 수만큼 반복하여 출력 
		Scanner sc = new Scanner(System.in);
		int num = sc.nextInt();
		for(int i = 0; i<num; i++) {
			int temp = sc.nextInt();
			System.out.println(cal(temp));
		}
		
		sc.close();
	}
	
	public static int cal(int n) {
		
		if(d[n]>0) {
			return d[n];
		}
		
		d[n] = cal(n-1) + cal(n-2) + cal(n-3);
		
		return d[n];
	}
	
}