문제 링크

분류

그리디 알고리즘(Greedy Algorithm)

풀이

그리디 알고리즘을 통해 문제를 해결할 수 있다.

먼저, 버튼을 통해 늘릴 수 있는 시간이 10초, 30초, 60초, 600초로 배수 관계이다. 따라서 그리디 알고리즘을 이용할 수 있다.

또한, 버튼을 누르는 순서는 버튼을 누르는 횟수에 관계 없으므로 $S$초에 대하여 버튼을 누르는 최소 횟수는 다음과 같다.

\[\lfloor \frac{S}{600} \rfloor + \lfloor \frac{S\%600}{60} \rfloor + \lfloor \frac{S\%60}{30} \rfloor + \lfloor \frac{S\%30}{10} \rfloor + 1\]

다만, 조리 시작 버튼의 경우 처음 눌렀을 때와 나중에 눌렀을 때의 값이 다르게 나오므로 처음 눌렀을 때와 나중에 눌렀을 때의 경우를 나누어 생각하여 계산하여야 한다. 그리고 이 둘의 최솟값을 출력하면 된다!

코드

#include <bits/stdc++.h>

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    string s;
    cin >> s;
    ll S, tmp1 = 0, tmp2 = 99999, cnt = 0;

    S = (s[0] - '0') * 600 + (s[1] - '0') * 60 + (s[3] - '0') * 10;

    tmp1 = S / 600 + (S % 600) / 60 + (S % 60) / 30 + (S % 30) / 10 + 1;
    if (S >= 30) {
        S -= 30;
        tmp2 = S / 600 + (S % 600) / 60 + (S % 60) / 30 + (S % 30) / 10 + 1;
    }
    cnt = min(tmp1, tmp2);
    cout << cnt;
}