백준 25597 : 푸앙이 러닝머신

이번주 solved.ac 마라톤문제이다.

 

정지, 1m/s, 4m/s, 8m/s의 버튼 4개가 있는 러닝머신을 통해 T초에 정확히 X의 거리를 가려고 할 때 눌러야할 버튼의 최소횟수와, 버튼을 언제 눌러야하는지를 구해야하는 문제이다.

 

먼저, 정지버튼이 존재함으로 주어진 X의 거리를 최단시간안에 완주하고자할때의 8m/s, 4m/s, 1m/s가 각각 몇번씩 필요한지를 그리디하게 구할 수 있다.

이때 8, 4, 1버튼의 필요횟수를 x, y, z라 할때

8x + 4y + z = X이고 이때 x + y + z > T라면 불가능함으로 -1을 출력하면된다.

만약 가능하다면, x, y, z를 8 -> 4 -> 1순으로 가능한 적은 버튼을 누르도록 버튼을 합쳐 최적의 해를 구해가면 된다.

 

Code

#include <stdio.h>
#include <vector>

using namespace std;
using ll = long long;

int main()
{
    ll n, k;
    scanf("%lld %lld", &n, &k);
    ll res8 = 0, res4 = 0, res1 = 0;
    if(n >= 8) {
        res8 = n / 8;
        n %= 8;
    }
    if(n >= 4) {
        res4 = n / 4;
        n %= 4;
    }
    if(n >= 1) {
        res1 = n / 1;
    }
    ll sum = res1 + res4 + res8;
    if(sum > k) {
        printf("-1");
        return 0;
    }
    if(sum < k) {
        if(res8 > 0 && k - sum >= res8) {
            res4 += (res8 * 2);
            res8 = 0;
            sum = res4 + res1 + res8;
        }
        if(res4 > 0 && k - sum >= res4 * 3) {
            res1 += (res4 * 4);
            res4 = 0;
            sum = res1 + res4 + res8;
        }
    }

    vector <pair<ll, ll>> vec;
    if(res8 > 0) vec.push_back({8, res8});
    if(res4 > 0) vec.push_back({4, res4});
    if(res1 > 0) vec.push_back({1, res1});
    
    printf("%lld\n", vec.size());
    printf("%lld %lld\n", k - sum, vec[0].first);
    ll time = k - sum + vec[0].second;
    for(ll i=1;i<vec.size();i++) {
        printf("%lld %lld\n", time, vec[i].first);
        time += vec[i].second;
    }
    return 0;
}

문제 링크

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