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

문제

풀이

설명

다이나믹프로그래밍

D[i] = i를 1,2,3의 합으로 나타내는 방법의 수
D[i] = D[i-1] + D[i-2] + D[i-3]

i번째의 값을 구하기 위해 i-1, i-2, i-3의 각각 1,2,3를 더하여 i값을 만들어낸다.

재귀

n <= 10 이기 때문에
총 경우의 수는 3^n이다.

go(count, sum, goal)

• 숫자 count개로 합 sum을 만드는 경우의 수

부르트포스로 문제를 풀기 위해서 3가지 경우를 고려해야함
1. 불가능한 경우 (sum > goal)

• 재귀 호출을 계속 해도 정답을 절대 찾을 수 없는 경우

2. 정답을 찾는 경우 (sum == goal)

• 문제의 조건을 위배한 경우

3. 다음 경우 호출 (수i go(count+1, sum+j, goal)

코드

다이나믹프로그래밍

public class Num9095 {

	public static void main(String[] args) {

		Scanner sc = new Scanner(System.in);
		
        int[] d = new int[11];
        d[0] = 1;
        
        for (int i=1; i<=10; i++) {
            for (int j=1; j<=3; j++) {
                if (i-j >= 0) {
                    d[i] += d[i-j];
                }
            }
        }
        
        int t = sc.nextInt();
        
        while (t-- > 0) {
            int n = sc.nextInt();
            System.out.println(d[n]);
        }
	}

재귀

import java.util.*;

public class Main {
    public static int go(int sum, int goal) {
        if (sum > goal) {
            return 0;
        }
        if (sum == goal) {
            return 1;
        }
        int now = 0;
        for (int i=1; i<=3; i++) {
            now += go(sum+i, goal);
        }
        return now;
    }
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            System.out.println(go(0, n));
        }
    }
}

코드설명

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