[BOJ] 백준 9095 1, 2, 3 더하기

출처: https://www.acmicpc.net/problem/9095

Approach

n이 크지 않아서 중복조합을 사용할 수 있지만

테스트 케이스 T가 주어지지 않아서 T의 크기에 따라서 결과가 다를 수 있습니다.

 

DP 점화식을 이용한다.

DP[i] = DP[i - 1] + DP[i - 2] + DP[i - 3];

 

DP[1] = 1; / DP[2] = 2; / DP[3] = 4;는 미리 정의

N의 범위가 최대 10 이하이기 때문에 LookUp Table을 구성해서

DP[] 값을 출력한다. DP[1..10]

DP[1]	DP[2]	DP[3]	DP[4]
1 → "1"	1 + 1 → "1" 2 → "1"	1 + 1 + 1 → "1" 1 + 2 → "2" 3 → "1"	1 + 1 + 2 → "3" 1 + 3 → "2" 1 + 1 + 1 + 1 → "1" 2 + 2 → "1"
1	1 + 1 = 2	1 + 2 + 1 = 4	3 + 2 +  1 + 1 = 4 + 2 + 1 = 7

 

다른 문제 [BOJ] 12101 1, 2, 3 더하기 2 

[BOJ] 백준 12101 1, 2, 3 더하기 2

C++

#include <stdio.h>

const int MAX_N = 10 + 1;
int TC, N, DP[MAX_N];

int main()
{
	// freopen("input.txt", "r", stdin);
	DP[1] = 1;
	DP[2] = 2;
	DP[3] = 4;
	for (int i = 4; i <= MAX_N; ++i)
	{
		DP[i] = DP[i - 1] + DP[i - 2] + DP[i - 3];
	}

	scanf("%d", &TC);
	while (TC--)
	{
		scanf("%d", &N);
		printf("%d\n", DP[N]);
	}
}

 

Java

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt();
		int DP[] = new int[10];
		
		int result[] = new int[T];
		
		for(int i=0; i<3; i++){
			DP[i] = i+1;
			if(i == 2){
				DP[i]++;
				break;
			}
		}
		for(int i=3; i< 10; i++){
			DP[i] = DP[i-3] + DP[i-2] + DP[i-1]; 
		}
		
		for(int i = 0; i < T; i++){
			int target = sc.nextInt();
			result[i] = DP[target-1];
		}
		for (int i = 0; i < result.length; i++) {
			System.out.println(result[i]);
		}
	}

}