7194

static int s, t, a, b;
 
static int solution(void)
{
    scanf("%d %d %d %d", &s, &t, &a, &b);
    int ret = 0;
 
    if (b == 1)
    {
        if ((t - s) % a == 0)
            return (t - s) / a;
        else
            return -1;
    }
     
    while (s < t)
    {
        if (!(t % b) && t / b >= s)
            t /= b;
        else
            t -= a;
        ret += 1;
    }
 
    if (s == t)
        return ret;
    else
        return -1;
}

s를 +a 하거나 *b 해서 t를 최대한 빨리 얻을 수 있는지, 얻을 수 있다면 최소 몇번의 연산을 해야하는지 찾는 문제이다.

b가 1이면 곱해도 그 영향이 없으므로 연산에서 제외하여 생각 할 수 있다.

b가 1보다 크다면 여기서 부터는 역추적의 개념으로 가는 것이 편하다.

먼저 b로 나누어 떨어 질 수 있는지 확인을 해보고 나누어 떨어진다면 나누어 준다.

그렇지 않다면 a를 빼주어 s 까지 갈 수 있는지 확인 하는 것이다.

 

그러나 이 코드는 단순히 pass를 위한 코드일 뿐 불완전 하다 볼 수 있다.

여러 반례가 존재 하기 때문이다.

그 중 하나인 s = 10, t = 40, a = 30, b = 2 일 때를 해보면 알 수 있다.

 

그래서 원래 내가 생각한 코드는 아래이다. 아래 코드는 위의 경우에 대해서도 정확한 답을 알려주지만,

테스트해보면 제한시간 초과로 pass되지 않는 코드이다.

static int s, t, a, b;
static stack<pair<int, int>> st;
 
static int solution(void)
{
    scanf("%d %d %d %d", &s, &t, &a, &b);
    pair<int, int> cur;
    int ret = 0;
 
    st.push(pair<int, int>(t, 0));
    while (!st.empty())
    {
        cur = st.top();
        st.pop();
 
        if (cur.first == s)
            break;
 
        if (cur.first < s)
            continue;
 
        int n[3] = { 0, 0, 0 };
        if (!(cur.first % b))
            n[0] = cur.first / b;
        n[1] = cur.first - a;
        if (n[0] < n[1])
        {
            n[2] = n[0];
            n[0] = n[1];
            n[1] = n[2];
        }
        n[2] = cur.second + 1;
 
        for (int i = 0; i < 2; i++)
            st.push(pair<int, int>(n[i], n[2]));
    }
 
    while (!st.empty())
        st.pop();
 
    if (cur.first == s)
        return cur.second;
    else
        return -1;
}

앞서 설명한 코드처럼 역추적을 해나가는데 여기서는 가능한 모든 경우를 다 고려한다.

t 에서 b 로 나눈 값과 t 에서 a를 뺀 값 둘 중에 최대 값을 먼저 스택에 푸쉬함으로서 

s에 더 가까운 값을 먼저 확인해 나가는 것이다.