백준 - 9095 - 1, 2, 3 더하기

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

9095번: 1, 2, 3 더하기

1. 백트래킹을 이용한 구현

import java.util.Scanner;

/**
 * 9095
 */
public class 일이삼더하기1 {
    private static int count;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = Integer.parseInt(sc.nextLine());
        for (int i = 0; i < T; i++) {
            int targetNumber = Integer.parseInt(sc.nextLine());
            count = 0;
            backtracking(targetNumber, 0);
            System.out.println(count);
        }
    }

    private static void backtracking(int targetNumber, int sum) {
        if (sum == targetNumber) {
            count++;
        } else if (sum > targetNumber) {
            return;
        }

        for (int i = 1; i <= 3; i++) {
            backtracking(targetNumber, sum + i);
        }
    }
}

2. 다이나믹 프로그래밍을 이용한 구현

import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		int[] inputs = new int[t];
		int[] results = new int[t];
		for(int i=0; i<t; i++) {
			inputs[i] = sc.nextInt();
		}
		
		for(int i=0; i<t; i++) {
			int n = inputs[i];
			int[] dp = new int[n+1];
			dp[0] = dp[1] = 1;
			if(n > 1)	dp[2] = 2;
			for(int j=3; j<=n; j++) {
				dp[j] += dp[j-1];
				dp[j] += dp[j-2];
				dp[j] += dp[j-3];
			}
			results[i] = dp[n];
		}
		
		for(int i=0; i<t; i++) {
			System.out.println(results[i]);
		}		
	}
}

알고리즘

백트래킹을 이용하여 특정수를 만들기 위해 필요한 조합을 뽑는 알고리즘을 구현하였습니다.

처음에는 sum과 targetNumber가 같을때 return을 했는데 무한 루프에 빠지고 말았습니다.

이유는 targetNumber가 4일 때, sum이 3인 상태에서 i가 3일 때, sum + i 를 다음 뎁스에서 진행되게 되면 4가 아닌 바로 6이되버립니다. 그러면 return되지 않는 경우가 발생하는 거지요,

즉, sum이 targetNumber보다 큰 경우가 발생하고 이 경우 더 이상 진행할 의미가 없기 때문에 return을 해줘야합니다.

 

그리고 예전에 다이나믹 프로그래밍 공부할때 구현했던 소스가 있어서 같이 올려봅니다.