[BOJ/백준][Gold5] 19940 : 피자 오븐 (C++)

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

19940번: 피자 오븐

 

 

[난이도] Gold5
[유형] BFS

[풀이]
간단한 Greedy + BFS 문제입니다.

그냥 BFS를 돌리면 N 범위가 10000000 이고, tc개수가 100이므로 시간초과가 발생합니다.
잘 생각해보면 0에서 N을 만들 때, ADDH 연산 (t+60)을 가장 많이 사는것이 연산 횟수를
줄이는데 유리합니다.

N/60 만큼 ADDH 연산을 사용한 뒤, N%60 을 ADDH 외의 연산으로 만들때의 최적값과,

N/60+1만큼 ADDH 연산을 사용한 뒤, 60-N%60을 ADDH 외의 연산으로 만들때의 최적값을

BFS를 이용해 각각 구해준 뒤, 연산 횟수가 더 적은 케이스를 답으로 출력해주면 됩니다.

예를 들어, N이 134라면 60*2 + 14 와 60*3 - 46 을 비교하는 것과 같습니다.

 

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
using namespace std;
int tc,N,a[]={10,-10,1,-1},visit[80];
vector<int> bfs(int k,int m){
    memset(visit,0,sizeof(visit));
    queue<vector<int>> q;
    visit[0]=1;
    q.push({0,0,0,0,0});
    while(1){
        int sz = q.size(); 
        while(sz--){
            auto cur = q.front(); q.pop();
            if(cur[4]==m) {
                vector<int> r = {k};
                for(int i=0;i<4;i++) r.push_back(cur[i]);
                return r;
            }
            for(int i=0;i<4;i++){
                int nxt = cur[4]+a[i];
                if(nxt<0 || nxt>70 || visit[nxt]) continue;
                visit[nxt]=1;
                auto nv = cur;
                nv[i]++;
                nv[4]=nxt;
                q.push(nv);
            }
        }
    }
}
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d",&N);

        int k = N/60;
        int mod = N%60;

        auto ret1 = bfs(k,mod);
        int cnt1=0;
        for(int i=0;i<5;i++) cnt1+=ret1[i];

        auto ret2 = bfs(k+1,60-mod);
        int cnt2=0;
        for(int i=0;i<5;i++) cnt2+=ret2[i];
        swap(ret2[1],ret2[2]);
        swap(ret2[3],ret2[4]);

        if(cnt1>cnt2){
            for(int i=0;i<5;i++) printf("%d ",ret2[i]);
        }else{
            for(int i=0;i<5;i++) printf("%d ",ret1[i]);
        }
        puts("");
    }
}

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold5/19940.cpp