[알고리즘][Java] 백준(BOJ) 9095 1, 2, 3 더하기_자바

 

DP

9095 1, 2, 3 더하기    https://www.acmicpc.net/problem/9095

9095번: 1, 2, 3 더하기

 

 

문제 풀기 전 공부할 것 : 다이나믹 프로그래밍

 

 

 

 

 

 

 

풀이

<내용>

• n은 양수이며 11보다 작은 수이다.
• 정수 n이 주어졌을 때 1, 2, 3의 합으로 나타내는 규칙을 찾아야 한다.
• 정수 n-1에서 1을 더하면 n이 되고 마찬가지로 (n-2) + 2, (n-3) + 3은 n이다.
• 따라서 정수 n을 1, 2, 3의 합으로 나타내는 방법은 정수 (n-1), (n-2), (n-3)을 1, 2, 3의 합으로 나타내는 방법의 수의 합이다.
• n이 1일 때 1, 2일 때 2, 3일 때 4가지 방법이 있으므로 이를 이용하여 11보다 작을 때 모든 양수에 대한 방법 수를 규칙을 이용하여 배열에 저장한다.
• 그리고 t, n을 Scanner를 이용하여 입력받는다.
• 해당 배열의 n번째 있는 값이 1, 2, 3의 합으로 정수 n을 나타내는 방법의 수이므로 출력한다.

 

 

<코드>

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		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];
		}
		
		
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		
		for (int i=0; i<t; i++) {
			int n = sc.nextInt();
			System.out.println(dp[n]);
		}
		sc.close();

	}

}

 

 

 

 

 

 

 

 

 

같은 문제 파이썬으로 푸는 방법

2021.01.07 - [Algorithm/백준 알고리즘_Python] - [알고리즘][Python] 백준(BOJ) 9095 1, 2, 3 더하기_파이썬

[알고리즘][Python] 백준(BOJ) 9095 1, 2, 3 더하기_파이썬