[알고리즘][백준][JAVA] 9095번 : 1,2,3 더하기 / Dynamic Programming, 다이나믹 프로그래밍

다이나믹 프로그래밍 (DP)

해당 문제의 알고리즘을 확인해보면 '다이나믹 프로그래밍' 이라고 되어 있다.

이는 동적 계획법이라고도 불리며, 하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 것으로 특정한 알고리즘이 아닌 하나의 문제해결 패러다임으로 볼 수 있다.

 

이는 큰 문제를 작은 문제로 쪼개서, 그 답을 저장해두고 재활용하는 방식으로 자주 쓰인다. (기억해가면서 풀기)

 

DP를 쓰는 이유

일반적인 재귀 방식 또한 DP와 매우 유사하다.

하지만 둘의 큰 차이점은 일반적인 재귀를 단순히 사용 시 동일한 작은 문제들이 여러 번 반복 되어 비효율적인 계산될 수 있다는 것이다.

 

예를 들어 피보나치 수열을 살펴보자.

피보나치 수열은 다음과 같다.

1, 1, 2, 3, 5, 8, 13, 21, 34, ,,,,

 

피보나치 수열을 구하고 싶을 때 재귀함수로 구현하면 어떻게 될까?

단순하게 return f(n) = f(n-1) + f(n-2) 로 구현 할 수 있다.

 

그런데 f(n-1), f(n-2)에서 각 함수를 1번씩 호출하면 동일한 값을 2번씩 구하게 되고 이로 인해 100번째 피보나치 수를 구하기 위해 호출되는 함수의 횟수는 기하급수적으로 증가한다.

왜냐하면, f(n-1)에서 한 번 구한 값을 f(n-2)에서 또 다시 같은 값을 구하는 과정을 반복하게 되기 때문이다. 

 

그러나 한 번 구한 작은 문제의 결과 값을 저장해두고 재사용 한다면 어떨까? 앞에서 계산된 값을 다시 반복할 필요가 없이 약 200회 내에 계산이 가능해진다.

 

즉, 매우 효율적으로 문제를 해결할 수 있게 된다. 시간복잡도를 기준으로 아래와 같이 개선이 가능하다.
O(n^2) → O(f(n)) 로 개선 (다항식 수준으로, 문제에 따라 다름.)

출처 : https://hongjw1938.tistory.com/47

 

9095번 풀이

다이나믹 프로그래밍의 개념을 고려하면서, 9095번 문제를 풀어보자.

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

9095번: 1, 2, 3 더하기

arr[n] 1차원 배열 을 생성한다. arr[n] 는 정수 n을 1,2,3 의 합으로 나타낼 수 있는 경우의 수를 의미한다.

 

n=1일때

1 

 

-> arr[1]=1

 

 

n=2일때

1 + 1

2

->arr[2]=2

 

 

n=3일때,

1 + 1 + 1

1 + 2

2 + 1

3

->arr[3] = 4

 

 

n=4일때,

1 + 1 + 1 + 1

1 + 2 + 1

2 + 1 + 1

3 + 1

 

1 +1 + 2

2 + 2

 

1 + 3

-> arr[4] = 7

 

n=4일때를 체크해보면, arr[4] = arr[3] + arr[2] + arr[1] 임을 알 수 있고,

이를 통해 arr[n] = arr[n-1] + arr[n-2] + arr[n-3] 이라는 점화식을 이끌어 낼 수 있다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

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

        int [] arr = new int[11];

        // 배열 arr의 초기값 세팅
        arr[1]=1;
        arr[2]=2;
        arr[3]=4;

        // 점화식을 이용해 배열에 값 채우기
        for (int i=4;i<11;i++){
            arr[i] = arr[i-3]+arr[i-2]+arr[i-1];
        }

        for (int i=0;i<T;i++){
            int n = Integer.parseInt(br.readLine());
            System.out.println(arr[n]);
        }
    }
}