[C++][백준 14562] 태권왕

문제

접근 방법

현재 점수에서 B만을 사용하여 상대의 점수에 도달하더라도 최악의 경우 99회이므로 시간의 여유는 크다.

조심해야 할 점은 상대의 점수를 넘는 순간이다. 다시 점수를 깎을 방법이 없으므로 영원히 상대의 점수에 도달할 수 없기에 무시해야 하는 경우다.

코드

#include <iostream>
using namespace std;
int C, S, T;
int dfs(int point, int penalty)
{
    if (point > T + penalty)
    {
        return 100;
    }
    else if (point == T + penalty)
    {
        return 0;
    }

    int A = dfs(point * 2, penalty + 3);
    int B = dfs(point + 1, penalty);

    return min(A, B) + 1;
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> C;
    while (C--)
    {
        cin >> S >> T;

        cout << dfs(S, 0) << "\n";
    }
    return 0;
}

풀이

백트래킹을 활용하여 A로 가는 경우, B로 가는 경우를 나누어서 탐색한다.

두 발차기 경로 중 더 낮은 값으로 도달한 경우를 선택하여 반환할 시 최종적으로 정답에는 가장 낮은 값으로 도달한 경우가 출력될 것이다.

만약 상대의 점수를 넘어선 경우가 존재하면 B만으로 도달할 수 있는 값보다 큰 100을 반환하여 해당 값이 선택 안 되게 처리해 준다.