[백준] 9095번 알고리즘 풀이 여러가지 방법 : Programming Story

www.acmicpc.net/problem/9095

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 7가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다.

1+1+1+1

1+1+2

1+2+1

2+1+1

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

이런 식의 문제이다. 시간제한과 메모리 제한등 구체적인 사항은 위의 링크에 들어가서 확인할 수 있다.

1) 다이나믹 프로그래밍 방법 이용하기

import java.util.*;

public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        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];
                }
            }
        }
        while(t-->0){
            int n=sc.nextInt();
            System.out.println(d[n]);
        }
    }
}

d[i]= i를 1,2,3의 합으로 나타내는 방법의 수라고 정의하자

문제에서 n은 11보다 작다고 했으므로, d는 1부터 10까지 구해놓으면 된다.

다이나믹 프로그래밍은 큰 문제를 작은 문제로 쪼개서 나누어 푸는 알고리즘을 뜻한다.

여기서 중요한 식은,

d[i]= d[i-1] + d[i-2] + d[i-3] 이것이다.

i를 1,2,3으로 나타낼 때 마지막에 1을 사용하였다면 그 개수는 d[i-1]과 같을 것이고, 2를 사용하였다면 그 개수는 d[i-2]와 같을 것이고 3을 사용하였다면 d[i-3]과 같기 때문이다.

따라서 2중 for문으로 j는 1부터 3까지 돌리면서 i-j>=0일 시에 d[i-j]를 더해주면 되는 것이다.

2) 브루트포스 재귀 방법을 사용해서 풀기

import java.util.*;

public class Main{
    static int recur(int sum, int goal){
        if (sum>goal){
            return 0;
        }
        if (sum==goal){
            return 1;
        }
        int ans=0;
        for(int i=1; i<=3; i++){
            ans+=recur(sum+i,goal);
        }
        return ans;
    }
    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(recur(0,n));
        }
    }
}

이는 recur(int sum, int goal) 이라는 재귀함수를 사용하여 푸는 방법이다.

현재까지의 합을 sum으로 표현하고, 만들고자 하는 숫자의 합을 goal로 표현하는 것이다.

그럴 때, sum>goal 인 경우는 불가능한 경우이며,

sum과 goal이 같아지는 경우는 문제의 해답을 찾은 경우이니 1을 return하며 ans에다가 더해주게 된다.

1을 사용하는 경우 recur(sum+1, goal)이고,

2을 사용하는 경우 recur(sum+2, goal)이며,

3을 사용하는 경우 recur(sum+3, goal)이다.

따라서 for문을 돌면서 각각의 경우을 체크해주게 된다.

1번 방법에서는 i-j>=0 이라는 장치를 사용했는데 여기서는 sum>goal일 경우 0을 return해주게 됨으로 그러한 장치가 필요없다는 것을 알 수 있다.