[알고리즘 문제] 13250번 주사위 게임 (feat. 탑-다운, 바텀-업)

 

사실 이 문제는 1주일 전에 푼거긴 한데 dynamic programming에서 bottom-up, top-down 기법의 차이를 분석하고 넘어가고자 포스팅하고자 한다. 

13250번: 주사위 게임

 

 

1. 문제 분석

dt[i] = i이상의 사탕을 가져올 때 주사위를 던진 횟수의 기댓값으로 지정했다. 또한 주사위는 1~6 자연수 이기에 해당 범위의 dt값에만 영향을 받는다. 

 

2. Bottom-Up

Bottom-Up은 문제를 작은 단위로 쪼갠 상태에서 부터 큰 단위로 범위를 확장해 나가는 방법이다. 이를 코드로 나타내면 아래와 같다.

#include <bits/stdc++.h>
using namespace std;

double dt[6000100];

int N;

int main()
{
    cin >> N;
    dt[0] = -1;
    for(int i=0; i<=N; i++){
        dt[i] += 1;
        for(int j=1; j<=6; j++) dt[i+j] += dt[i] / 6;
    }
    printf("%.16lf",dt[N]);
}

 

3. Top-Down

Top-Down방법은 원래 문제를 풀기 위해 작은 단위로 쪼개 나가고 이미 계산한 경우 그 결과를 이용해 문제를 풀어나가는 방법이다. 이는 dfs와  memoization기법을 이용한다. 이 때 memoization기법은 이미 구한 값을 다시 한번 더 구하지 않고 활용하는 방법을 말한다. 코드는 아래와 같다.

#include <bits/stdc++.h>
using namespace std;

double dt[6000100];
int N;

double f(int candy)
{
    if(candy <= 0) return 0;
    if(dt[candy]) return dt[candy];
    double sum = 0;
    for(int i=6; i>=1; i--) sum += f(candy-i) / 6;
    return dt[candy] = sum + 1;
}

int main()
{
    cin >> N;
    f(N);
    printf("%.16lf",dt[N]);
}

 

 

4. Bottom-Up / Top-down 장단점

	Bottom-Up 기법	Top-Down 기법
시간	for문을 이용하기에 효율적이다.	재귀함수를 이용하기에 비효율적이다.
메모리
목적	기본적인 탐색에서 용이하다.	자료구조와 같이 쓰기 좋다.

 

솔직히 Top-down이 제 입장으론 디버깅도 쉽고 논리도 생각하기 쉽고.. 등등 있지만 시작과 끝 값을 지정하기 힘들다는 부분도 차이점이 될 수가 있다. 여기까지는 취향 차이지만, 위의 목적이 가장 뚜렷한 차이인 것 같다.

 

 

5. 교훈 및 소감

솔직히 이전 까지는 Bottom-Up / Top-down 기법에 연연하지 않고 그냥 마음대로, 생각안하고 사용했었는데 이번 문제를 여러 방법으로 풀어보면서 차이점을 느낄 수 있었다. 그리고 최근에 tree-dp 를 해보면서 이 문제가 떠올라서.. 사실 포스팅 안할라고 했는데 늦게라도 올리게 됬다.