[BOJ/Gold 2] 백준 17234 Scoring Hack(C++)

문제 링크

https://www.acmicpc.net/problem/17234

17234번: Scoring Hack

 

 

문제

0점에서 시작해 매 턴 점수를 획득해 나가는 게임이 있다. 각 턴에서 플레이어가 게임 에서 승리하면 a점을 얻고, 지면 b점을 얻는다. 점수의 총합이 n점 이상이면 게임이 끝나게 된다.

포스텍의 한 학생이 이 게임을 해킹하는 데 성공했다. 그래서 각 턴에서 승리할지, 질지 자유롭게 결정할 수 있다. 심지어는 원하는 턴에서 점수를 a점이나 b점 올리는 대신 두 배로 바꾸는 것도 가능하다. 예를 들면 a가 3이고 b가 2이며 현재 점수가 10이라고 할 때, 다음 턴의 점수로 가능한 것에는 12, 13, 또는 20이 있다. 하지만 만약 학생이 n+a점 이상의 점수로 게임을 끝내게 되거나, 각 턴이 끝났을 때 점수를 두 배로 올린 턴이 전체 턴의 10%를 초과하면 학생은 게임 운영진의 의심을 받게 되고, 게임에서 퇴출당하게 된다.

이 학생이 운영진의 의심을 받지 않고 게임을 끝내는 데 필요한 최소한의 턴을 구하라.

입력

n, a, b 세 개의 정수가 띄어쓰기를 사이에 두고 주어진다. (1 ≤ n ≤ 500, 1 ≤ b ≤ a ≤ 100)

출력

이 학생이 운영진의 의심을 받지 않고 게임을 끝내는 데 필요한 최소한의 턴을 출력한다.

예제 입력 1

10 4 3

예제 출력 1

3

예제 입력 2

50 3 2

예제 출력 2

10

힌트

첫 번째 예제의 경우 매 턴마다 4점씩 점수를 올리면 세 턴 만에 10점을 넘기는 것이 가능하다.

두 번째 예제의 경우 일곱 번의 턴 동안 3점씩 올리고, 두 번의 턴 동안 2점씩 올리고, 마지막 턴에서 점수를 두 배로 올리면 10번의 턴 만에 50점에 도달할 수 있다.

단 예제에서 제시된 방법이 최소 횟수를 얻을 수 있는 유일한 방법은 아니다.

알고리즘 분류

• 그래프 탐색

풀이

특정한 경우를 방문했다는 3차원 배열 Visited[T][X][D]를 선언한다. 이것은 T번째 턴까지 점수 2배를 D번 사용해서 X점까지 도달했음의 유무를 의미한다.

(T, X, D)가 (0, 0, 0)부터 시작해서 BFS 수행을 통해 답을 찾는다. 이 때, A점을 더하거나, B점을 더하거나, 2배만큼 올린다는 3가지의 방법을 통해 점수를 계속해서 증가시킨다.

현재 점수 X가 N점 이상에 도달하고, N + A점 미만이며 D가 T의 10% 이하라는 2가지 조건을 만족했을 때의 최소의 턴을 구한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <algorithm>
#define MAX 1111
#define INF 1e9
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, A, B;
bool Visited[MAX][MAX][11];
int Answer = INF;

void input() {
    cin >> N >> A >> B;
}

bool checking(int Score, int Total_Turn, int Double_Turn) {
    if (Score >= N + A) {
        return false;
    }
    return true;
}

void BFS() {
    queue<pair<pair<int, int>, int> > Q;
    Q.push(make_pair(make_pair(0, 0), 0));
    Visited[0][0][0] = true;

    while (!Q.empty()) {
        int NowT = Q.front().first.first;
        int NowX = Q.front().first.second;
        int NowD = Q.front().second;
        Q.pop();

        if (NowX >= N) {
            if (checking(NowX, NowT, NowD)) {
                Answer = min(Answer, NowT);
            }
        }
        if (!Visited[NowT + 1][NowX + A][NowD] && (NowX < N)) {
            Visited[NowT + 1][NowX + A][NowD] = true;
            Q.push(make_pair(make_pair(NowT + 1, NowX + A), NowD));
        }
        if (!Visited[NowT + 1][NowX + B][NowD] && (NowX + B < N + A)) {
            Visited[NowT + 1][NowX + B][NowD] = true;
            Q.push(make_pair(make_pair(NowT + 1, NowX + B), NowD));
        }
        if (!Visited[NowT + 1][NowX * 2][NowD + 1] && (NowX * 2 < N + A) && (NowD * 10 <= NowT - 9)) {
            Visited[NowT + 1][NowX * 2][NowD + 1] = true;
            Q.push(make_pair(make_pair(NowT + 1, NowX * 2), NowD + 1));
        }
    };
}

void settings() {
    BFS();
}

void find_Answer() {
    cout << Answer << "\n";
}

int main() {
    FASTIO
    input();
    settings();
    find_Answer();

    return 0;
}