[C++] 25597번 푸앙이와 러닝머신

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

---

 

26/01/17

 

 

랜덤 디펜스하다가 마주한 문제이다. 처음에는 BFS적 접근 방법을 생각했지만, 그리디적 접근임을 후에 알아차렸다.

---

 

문제 접근 방식:

 

 

먼저, $X \leq T$인 경우는 매우 구성하기 쉽다.

그냥 $1$번 조작하면 되고, $T-X$초 시점에 버튼 $1$을 누르면 된다.

$X > T$인 경우가 문제인데, 그리디적으로 생각해보자.(Fractional knapsack을 떠올리자.)

$X$미터를 가장 적은 "시간"으로 가기 위해서는 어떻게 해야할까?

$X$를 $8$로 나눈 값을 $\text{eight}$이라고 하자. 이는 $X$미터를 넘어가지 않는 선에서 초속 $8m / s$로 최대한 많이 뛰었을 때의 초 수이다.

$X-8\cdot\text{eight}$을 $4$로 나눈 값을 $\text{four}$라고 하자. 이는 $X$미터를 넘어가지 않는 선에서 초속 $8m / s$로 최대한 많이 간 후에, 남은 거리를 초속 $4m /s$로 최대한 많이 뛰었을 때의 초 수이다.

마찬가지로, $X-8\cdot \text{eight}-4\cdot \text{four}$을 $\text{one}$이라고 하자. 이는 $X$미터를 넘어가지 않는 선에서 초속 $8m /s$로 최대한 많이 간 후에, 남은 거리를 초속 $4m /s$로 최대한 많이 가고, 거기서 남은 거리를 초속 $1m /s$로 갔을 때의 초 수이다.

이때 우리는 $\text{eight}+\text{four}+\text{one}$이 $X$미터를 가는 최단 시간임을 확인할 수 있다.

따라서 $\text{eight}+\text{four}+\text{one}>T$이라면 $T$초만에 $X$미터를 갈 수 없다.

따라서 이런 경우면 $-1$을 출력하면 된다.


이제 버튼 조작 $1$번 혹은 $2$번만에 갈 수 있는 경우를 생각해보자.

먼저, $\text{time} = \text{int(bool(eight))}+\text{int(bool(four))}+\text{int(bool(one))}$라고 하자.

$\text{time}$은 최소 버튼 조작 횟수의 상한선이다.

즉, $\text{time}$보다 버튼을 더 많이 눌러서 가는 것은 문제 조건에 맞지 않는다.(문제 조건은 버튼의 최소 조작수를 요구하므로)

$\text{time}=1$인 경우라면, 그냥 출력하면 된다.

$\text{time}=2$인 경우라면, 상한이 $2$라는 뜻이다. 이때는 경우가 3가지로 나뉜다.

1. $\text{eight}=0$인 경우. 즉, $\text{four}, \text{one} \neq 0$인 경우
2. $\text{four}=0$인 경우. 즉, $\text{eight}, \text{one} \neq 0$인 경우
3. $\text{one}=0$인 경우. 즉, $\text{eight}, \text{four} \neq 0$인 경우

1번 경우와 2번 경우는 버튼 $1$을 무조건 누를 수 밖에 없다.

왜냐하면 $\text{one} \neq 0$이라는 뜻은 초속 $8m/ s$나 $4m /s$로 달려도 남을 수 밖에 없는 미터(예를 들자면, $3m, 2m, 1m$등등)이 존재한다는 뜻이기 때문이다.

따라서 이 경우는 무조건 $2$번의 버튼 조작을 요구한다.

3번 경우는 $X$가 $4$의 배수라는 뜻이므로, 버튼 $4$만 눌러서 갈 수도 있다.(이 경우 최단 시간($=\text{eight}+\text{four}+\text{one}$)보다 버튼 $8$을 눌러서 몇 초 갔는지(=$\text{eight}$)만큼의 시간이 더 소요될 수 있다.)

이것이 가능하다면 $1$번의 버튼 조작을 통해 갈 수 있다.


$\text{time}=3$인 경우, 상한이 $3$이라는 뜻이다.

이때도 $\text{time} = 2$의 3번 경우처럼, 버튼 $4$를 누르는 대신 버튼 $1$을 눌러서 조금 더 오래 걸리도록 하고 대신에 버튼 조작 횟수를 더 줄일 수 있다.

그것이 가능하다면 버튼 $8$과 버튼 $1$만 눌러서 갈 수 있다.

만약 그게 불가능하다면 그냥 버튼 $8, 4, 1$을 그리디하게 누르는 식으로 구현하면 된다.

---

아래는 내가 위의 접근 방식과 같이 작성한 C++ 코드이다. 더보기를 누르면 확인할 수 있다.

 

// 25597번 푸앙이와 러닝머신
// 애드혹, 많은 조건 분기, 그리디, 해 구성하기
#include <iostream>

using namespace std;
#define fastio ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl '\n'
typedef long long ll;

int main(void){
    fastio
    
    ll X, T; cin >> X >> T;
    if (X <= T){
        cout << 1 << endl;
        cout << T-X << ' ' << 1;
        return 0;
    }
    // X > T인 경우
    ll eight = X / 8;
    ll four = (X - 8*eight) / 4;
    ll one = (X - 8*eight - 4*four);
    if ((eight + four + one) > T){
        cout << -1;
        return 0;
    }
    // 1번 혹은 2번만에 가능한지 판단
    ll time = ((eight) ? 1 : 0) + ((four) ? 1 : 0) + ((one) ? 1 : 0);
    if (time <= 2){
        if (X % 4 == 0 && (X / 4) <= T){
            cout << 1 << endl;
            cout << T-(X/4) << ' ' << 4;
            return 0;
        }
        cout << time << endl;
        if (eight){
            cout << T-eight-four-one << ' ' << 8 << endl;
        }
        if (four){
            cout << T-four-one << ' ' << 4 << endl;
        }
        if (one){
            cout << T-one << ' ' << 1 << endl;
        }
        return 0;
    }
    // 그 외에 2번만에 가능한지 판단
    if (eight + four*4 + one < T){
        cout << 2 << endl;
        cout << T-eight-4*four-one << ' ' << 8 << endl;
        cout << T-4*four-one << ' ' << 1 << endl;
        return 0;
    }
    cout << time << endl;
    cout << T-eight-four-one << ' ' << 8 << endl;
    cout << T-four-one << ' ' << 4 << endl;
    cout << T-one << ' ' << 1 << endl;
    return 0;
}