Boj 19940 c++ 피자오븐

소요시간 33분 45초.

자력으로 풀어낸 두번째 정올 문제. 아이디어를 떠올리는 것이 오래 걸렸다.

문제는 간단했다. 시간을 더하고 빼는 버튼이 있을 때, 버튼을 누르는 횟수를 최소화 하여 특정 시간대를 구해내는 것이다. 버튼은 +60, +10, -10, +1, -1(분)으로 총 다섯 개였다. 즉, 68분을 맞추려면 +60, +10, -1 x 2 만큼의 버튼을 누르는 경우가 최적이므로  출력 값은 1 1 0 0 2가 된다. 이것을 T개의 테스트 케이스에 대해서 출력하면 된다.

 

코드를 작성하기 이전, 이문제는 그리디 문제임을 떠올렸다. 그리고 어느정도의 수학적 규칙성 또한 반영되어있다고 느꼈다. 우선은 문제의 조건에서 가장 중요한 부분을 생각했다. 핵심은 60분 버튼을 최소한으로 눌러야 한다는 것이었다. 

 

때문에, 가장 먼저 한 것은 숫자를 60으로 나누고 그 몫 만을 60번 버튼 횟수에 저장한 것이다. 그리고 나머지 만을 남기면 나머지는 0에서 59사이로 분포하게 된다. 여기서 부터 조건문을 사용하여 최적의 횟수를 구해내야 한다. 때문에, 60의 절반인 30~40에 대한 최적 계산을 직접 해보았다. 시뮬레이션의 결과, 분기점은 35라는 것을 알아내었다. 35 이하의 수는 10을 십의 자리 수 만큼 더한 후, 일의자리를 만드는 것이 최적이다. 하지만 36~59부터는 60에서 -연산을 하는 것이 최적이였다.

 

또한 이 두가지 안에서도 경우가 갈린다. 일의자리수가 10에 가까운지에 따라 달라지기 때문이다. 이로 인해 일의 자리수에 대해서도 예외처리를 해주었다. 이러한 순서로, 60과 10, 1의 순서로 최적의 경우를 구하였다. 이는 동전 0 문제의 연장선으로 약수 관계와 나머지를 이용하여 최적해를 구해낼 수 있었다.

#include <iostream>
#include <cstring>

using namespace std;

int main(){

  int T, N;
  int cnt[5]={0,};

  cin>>T;

  while(T--){
    memset(cnt, 0, sizeof(cnt));
    cin>>N;
    cnt[0]+=N/60;
    N%=60;
    if(N<=35){
       cnt[1]+=N/10;
       N%=10;
       if(N<=5){
            cnt[3]+=N;}
       else{
        cnt[1]++;
        cnt[4]+=10-N;
       }
    }

    else{
        N=60-N;
        cnt[0]++;
        cnt[2]+=N/10;
        N%=10;
        if(N<=5){
        cnt[4]+=N;
        }
        else{
            cnt[2]++;
            cnt[3]+=10-N;
        }
    }
    for(int i=0; i<5; i++){
        cout<<cnt[i]<<" ";
    }
    cout<<"\n";

  }



}