백준 10879번 Speak your mind!

문제

문제 분석

복잡해 보이지만, 결국 요점은 입력을 2의 제곱의 덧셈 뺄셈으로 나타내는 것이다. 현재 값이 A라고 할 때 A를 X(2의 제곱수) - Y(나머지) 혹은 X'(2의 제곱수) + Y'(나머지)로 나타내고, 그 중에서 작은 값을 선택하면 된다. 이를 점화식으로 나타내면 다음과 같다.

 

N(A) = min((N(X/2)+N(A-X/2)+4), (N(X)+N(X-A)+4))

 

나는 이를 DP + DFS로 풀었다. 좀 더 디테일 하게 설명해보자면,  DP를 확인하여 값이 있으면 그 값을 리턴하고, 없으면 재귀 호출로 쭉 내려가서 값을 계산하여 그를 사용하는 방식 말이다. 내가 이렇게 한 이유는 A보다 큰 값이 문제 해결에 쓰이기 때문이었다(A = X - Y). 그런데 다시 보니, X는 A보다 크더라도 2의 제곱이 분명하므로 별다른 연산 없이 DP에 값이 존재하고, Y는 A보다 작다. 따라서 DFS를 이용한 재귀호출보다는 그냥 쌩 DP만 이용해서 풀었어도 됐을 것 같았다. 실제로, 다른 분들의 결과를 보니 400ms였던 나의 알고리즘에 비해 40ms에 분포해있었고, 모두 쌩 DP로 푼 경우였다.

 

가장 햇갈렸던 점은 0에 대한 처리이다. 처음에는 걍 안해줬다가, 0의 재귀 호출이 반복되면서 메모리 초과 오류가 떴고, 0이 문제인것 같아서 0으로 초기화해줬더니 틀렸다고 떴다. 생각해보니 0은 문장에 단어가 없는 것이 아닌 -1 + 1이라는 특수한 경우였고, 이를 규칙에 따라 6으로 초기화 해주었더니 문제가 해결돼었다.

 

코드

// code
#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<string>
#include<list>
#include<vector>
#include<stack>
#include<queue> // priority_queue 포함
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>

#include<algorithm>
#include<math.h>
#include<climits> // 자료형 limit포함

using namespace std;

typedef long long int lld;
typedef unsigned long long int uld;
typedef unsigned int ui;

const int MY_INT_MAX = 2000000000;

int DP[50001] = {0};


int dfs(int param_d)
{
    if(DP[param_d] != 0 || param_d == 0)
        return DP[param_d];

    int tmp_exp = 1;
    while(param_d / tmp_exp > 0)
        tmp_exp *= 2;
    
    int return_val = MY_INT_MAX;
    if(tmp_exp == 65536)
        return_val = min(return_val, (DP[tmp_exp/2]+1) +  dfs(tmp_exp - param_d) + 4);
    else
        return_val = min(return_val, DP[tmp_exp] +  dfs(tmp_exp - param_d) + 4);
    return_val = min(return_val, DP[tmp_exp/2] +  dfs(param_d - tmp_exp/2) + 4);
    DP[param_d] = return_val;
    return return_val;
}

void solution()
{
    // code
    int n;
    cin >> n;
    int init_d = 1;
    int init_count = 1;
    while(init_d <= 50001)
    {
        DP[init_d] = init_count;
        init_d *= 2, init_count++;
    }
    DP[0] = 6;

    for(int i=0; i<n; i++)
    {
        int target_d;
        cin >> target_d;
        target_d = abs(target_d);
        int out_val = dfs(target_d);
        cout << out_val << endl;
    }
}

int main ()
{
    iostream::sync_with_stdio(0); // 이제 C stdio의 입출력 사용 불가
    cin.tie(NULL);
    cout.tie(NULL); // 개행도 \n로 하도록 하자.
    solution();
    return 0;
}

개선점?

점화식으로 나타내보는것이 매우 중요한것 같다. 재귀호출로 구현은 매우 쉬웠지만, 이것을 점화식으로 직접 써보지 않아서 쌩 DP로 풀 수 있는 직관을 얻지 못했던 것 같다.

아이디어 -> 점화식 -> 알고리즘 -> 알고리즘 복잡도 평가

요런 방식으로 풀어야할것 같다.