피자 오븐( BOJ 19940 )

문제 : https://www.acmicpc.net/problem/19940

19940번: 피자 오븐

 

문제 파악하기

전자 오븐의 버튼을 최소로 누르는 방법을 출력하는 문제입니다. 버튼은 총 5개가 있으며, 각각의 경우에 따라 누르는 방법을 달리 해야하기 때문에 최적의 조건을 떠올려야 하는 문제입니다.

 

문제 해결하기

전자 오븐의 버튼은 총 5개 있습니다. 그 중에서 가장 무식하게 사용하기 쉬은 버튼은 바로 ADDH(t+60) 입니다. 60분 만큼 증가시키는 방법은 ADDH(t+60) 버튼을 누르는 게 가장 효율적이기 때문입니다. 따라서 우리는 일단 ADDH 버튼을 누를 수 있는 만큼 먼저 누른 다음에, 남은 분을 처리하면 됩니다.

 

이제 남은 일은 0 ~ 59분을 만들 수 있는 가장 효율적인 방법을 찾으면 됩니다. 이 때, 사용할 수 있는 방법은 크게 2가지 있습니다. 첫 번째, 나올 수 있는 모든 경우를 조건식으로 표현하는 방법입니다. 쉽게 말해, 조건문을 잘 설계하면 문제를 해결할 수 있습니다. 여기서 중요한 점은 MINT(t-10)와 MINO(t-1)을 잘 활용해야 한다는 것입니다. MINT는 십의 자리 숫자가 6에 가까울 때, MINO는 일의 자리 숫자가 10에 가까울 때 효과적으로 사용할 수 있습니다. 예를 들어 45라는 숫자를 보면, 45를 만드는 가장 효과적인 버튼은 { 1, 0, 1, 0, 5 } 입니다. 45라는 숫자는 40 혹은 50에서 만들 수 있으며, 40과 50 중에서 더 쉽게 만들 수 있는 숫자는 50입니다. 그 이유는 40은 총 버튼을 3번 눌러야 하지만 50은 2번만 누르면 만들 수 있기 때문입니다. 따라서, 우리는 우리가 만들고자 하는 숫자의 십의 자리와 일의 자리를 파악하여 전체 횟수를 파악하는 알고리즘을 설계할 수 있습니다. 일의 자리가 5보다 크다면 더 ADDT(t+10)와 MINO(t-1)를 활용해야 하며, 십의 자리가 3보다 크다면 ADDH(t+60)과 MINT(t-10)을 활용해야 합니다. 예외적으로 30 ~ 34까지는 ADDT(t+10)와 ADDO(t+1)을, 35~40까지는 ADDH(t+60)와 MINT(t-10), 그리고 MINO(t-1)를 사용해야 올바른 결괏값을 얻을 수 있습니다.

 

두 번째, 0부터 59까지 나올 수 있는 모든 경우를 직접 구하는 방법입니다. 여기서 말하는 직접이란, 0에서 모든 버튼을 눌러보고, 그 다음 숫자에서 모든 버튼을 눌러보면서 가능한 모든 경우의 수를 구하는 방법입니다. 이 방법은 무식하지만 문제를 정확하게 해결할 수 있다는 장점을 가지고 있습니다. 큐 혹은 함수를 사용해 모든 경우를 구한 다음, 입력이 들어올 때마다 해당 값을 바로 호출해서 계산하면 우리는 원하는 결괏값을 얻을 수 있습니다.

 

소스코드

첫 번째, 조건문을 활용하여 문제를 해결한 소스코드입니다.

#include <iostream>
using namespace std;
 
int T, N;
 
int main() {
    // 입력
    scanf("%d", &T);
    while(T--) {
        int ans[5] = {0,};
 
        scanf("%d", &N);
 
        // ADDH 실행
        ans[0] += N/60;
        N %= 60;
 
        // 조건문
        if(N <= 35) {
            if(N%10 > 5) {
                ans[1] += N/10 + 1;
                ans[4] += 10 - N%10;
            }
            else {
                ans[1] += N/10;
                ans[3] += N%10;
            }
        }
        else {
            ans[0]++;
 
            if(N%10  >= 5) {
                ans[2] += 6 - (N/10+1);
                ans[4] += 10 - N%10;
            }
            else {
                ans[2] += 6 - N/10;
                ans[3] += N%10;
            }
        }
 
        // 출력
        for(int i=0;i<5;i++) printf("%d ", ans[i]);
        printf("\n");
    }
    
}

 

두 번째, BFS 탐색을 활용하여 모든 경우의 수를 구해 문제를 해결한 소스코드입니다.

#include <iostream>
#include <string>
#include <queue>
using namespace std;
 
int T, N;
int d[5] = {60, 10, -10, 1, -1};
 
string dp[65];
queue< int > q;
 
bool cmp(string a, string b) {
    int la, lb;
    la = lb = 0;
 
    for(int i=0;i<5;i++) {
        la += (a[i]-'0');
        lb += (b[i]-'0');
    }
 
    if(la != lb) return la<lb;
    else return a<b;
}
 
int main() {
    // 전처리
    for(int i=0;i<=60;i++) dp[i] = "99999";
    dp[0] = "00000";
    q.push(0);
    
    // BFS 탐색 
    while(!q.empty()) {
        int cur = q.front();
        q.pop();
 
        for(int k=4;k>=0;k--) {
            // 다음 위치
            int nxt = cur+d[k];
            if(nxt<0 or nxt>60) continue;
 
            string tmp = dp[cur];
            tmp[k]++;
 
            // 현재 값이 기존 값보다 작은 경우
            if(cmp(tmp, dp[nxt])) {
                dp[nxt] = tmp;
                q.push(nxt);
            }
        }
    }
 
    
    // 입력
    scanf("%d", &T);
    while(T--) {
        int ans[5] = {0,};
 
        scanf("%d", &N);
 
        // ADDH 실행
        ans[0] += N/60;
        N %= 60;
 
        // 미리 구한 dp[N] 더하기
        for(int i=0;i<5;i++) ans[i] += (dp[N][i]-'0');
 
        // 출력
        for(int i=0;i<5;i++) printf("%d ", ans[i]);
        printf("\n");
    }
    
}

후기

처음에는 조건문으로 해결하려고 했다가 나중에 BFS 방식으로 해결한 문제입니다. 풀고 보니 문제는 어렵지 않았지만 조건을 생각하고 설계하는데 조금 머리아팠던 문제입니다. 조건문을 연습하기에 적격인 문제라고 생각합니다.