[DP]백준 9095 예제 뿌시기

알고리즘을 공부하면서 똑같은 문제도 여러 가지로 풀 수 있다는 것을 느꼈다.

그리고 각 문제마다 효율적인 방법이 있다.

 

그래서 알고리즘 문제를 풀때 다른 풀이와 내 풀이를 비교하며 어떤게 효율적인지 생각해보는 습관이 좋은 것 같다.

 

 

다음 문제는

백준의 9095번 분제 1,2,3더하기라는 문제이다.

 

n이 11보다 작다는 제한이 주어져서 뭔가 메모이제이션을 이용해서 풀면 굉장히 효율적일 것 같았다.

근데 어떻게 풀지 감이 안와서

 

처음에는 DFS를 이용해서 풀었다.

 

1. DFS 풀이법

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Main {
    static int count;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int tc = Integer.parseInt(br.readLine());

        StringBuilder sb = new StringBuilder();

        while (tc-->0){
            int i = Integer.parseInt(br.readLine());
            count=0;
            sb.append(count(i)).append('\n');
        }
        System.out.println(sb);
    }
    static int count(int i){
        if(i==0) count++;
        if(i>0) count(i-1);
        if(i>1) count(i-2);
        if(i>2) count(i-3);
        return count;
    }
}

1을 더할 경우 2를 더할 경우 3을 경우 세 가지로 나뉘어 가지를 타고 경우의 수를 나눠 들어간 후 해당 숫자가 되면 count를 하나씩 올려주는 것이다.

n의 값이 작고 tc가 작은지 생각보다 시간이 적게 소요됐다.

 

 

---

 

다른 풀이들을 찾아보니 역시나 dp를 이용해서 푼 경우가 많았다.

dp는 규칙을 찾아 점화식을 만들어내는 것이 중요한 것 같다.

 

즉, n번째 수가 이전의 항들과 어떤 규칙이 있는지를 알아내는 것이다.

 

위 문제에서는

n(n>3)을 1과 2와 3의 합으로 나타낼 때

젤 앞에 1이 오는경우, 2가 오는경우, 3이 오는 경우 3가지가 나올 수 있다.

 

따라서 n을 다음과 같이 나타낼 수 있다.

n = 1 + (n-1)

n = 2 + (n-2)

n = 3 + (n-3)

 

위 식에 따르면 n을 1,2,3의 합으로 나타낼 수 있는 모든 경우의 수는

1. 1 과 n-1을 1,2,3의 합으로 나타낼 수 있는 모든 경우의 수

2. 2 와 n-2를 1,2,3 의 합으로 나타낼 수 있는 모든 경우의 수

3. 3 과 n-3을 1,2,3의 합으로 나타낼 수 있는 모든 경우의 수

위 세가지 경우를 합한 경우가 된다.

 

위 규칙을 점화식으로 나타내면 dp[n] = dp[n-1] + dp[n-2] + dp[n-3] 이다.

 

이제 그럼 dp[4] 부터는 계산해서 구할 필요가 없다.

dp[3]까지만 구해주면 된다

 

dp[1] = 1

dp[2] = 2 //1+1, 2

dp[3] = 3 //1+1+1, 1+2, 2+1, 3

로 나타낼 수 있다.

 

이걸 이용해 코드로 나타내면

2.DP를 적용한 풀이법

import java.io.*;

public class Main{
	public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
        int tc = Integer.parseInt(br.readLine());
        
        int dp[] = new int[11];
        dp[1] = 1;
        dp[2] = 2;
        dp[3] = 4;
        
        for(int i = 4; i < 11; i++)
        	dp[i] = dp[i-1] + dp[i-2] + dp[i-3];
        for(int i = 0; i < tc; i++){
        	int t = Integer.parseInt(br.readLine());
        	sb.append(dp[t] + "\n");
        }
        System.out.println(sb);
    }
}

생각보다 시간이 오래걸린다.

dp 이용하는게 더 효율적일 것 같은데

이 방법은 testcase가 많아질수록 효율적이지 않을까 싶다.