[C++]G5 백준 19940 - 피자 오븐

1. 문제 링크

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

소요 시간 : 27분

시도 횟수 : 2

 

 

2. 문제 설명

난이도 : G5

사용 알고리즘 : Greedy

오븐의 시간을 설정하기 위해 버튼을 최소로 눌렀을 때, 문제에 정의된 기준으로(사전 순) 출력

 

3. 풀이 방식

BFS로도 풀릴 것 같이 생긴 문제였다.

하지만 솔브닥에서 그리디로 문제를 검색한 후였고 각 버튼의 횟수를 집계해서 표시해야 하고, 0.25초라는 짧은 시간 제한으로 인해 DP나 그리디로 풀어야겠다 생각했다!

60 이상의 숫자에 대해서는 60으로 우선 나눠주고(큰 숫자부터 덜어내기!), 60 이내에서 최소 버튼 횟수를 찾아가기 위한 기준을 찾는데 대부분의 고민을 했던 것 같다.

 

0에서 올라갈지 60에서 내려올 지 결정하는 기준점으로 35라는 숫자를 찾아내었고,

일의 자리 숫자가 5일 때 올라가는 방향 / 내려가는 방향에 따라 0에서 더할지 10에서 뺄지도 생각해야 했다.

 

#include<iostream>

using namespace std;

int main() {
	int t;
	cin >> t;
	while (t--) {
		int addh = 0, addt = 0, mint = 0, addo = 0, mino = 0;//변수 5개 말고 배열로 표현했다면 좀 더 편했을까?
		int n;
		cin >> n;
		if (n > 60) {//60보다 크면 우선 나눠주기
			addh += n / 60;
			n %= 60;
		}
		if (n>35) {//35보다 크면 60에서 내려오기
			addh++;
			if (n % 10 < 5) {//일의 자리가 5보다 작으면 0에서 더해주기
				addo = n % 10;
				n -= addo;
			}
			else {//5 이상이면 10에서 빼주기
				mino = 10 - (n % 10);
				n += mino;
			}
			mint += (60 - n) / 10;
		}
		else {//35보다 작으면 0에서 올라가기
			if (n % 10 <= 5) {//여기선 5 이하일 때 0에서 더해주기
				addo = n % 10;
				n -= addo;
			}
			else {
				mino = 10 - (n % 10);//5 초과일 때 10에서 빼주기
				n += mino;
			}
			addt += n / 10;
		}
		cout << addh << " " << addt << " " << mint << " " << addo << " " << mino << "\n";//배열이었으면 반복문으로 적었을 듯!
	}
}

 

<오늘의 TMI>
내일이 면접인데 준비하기도 바쁜 와중에 쫄려서 백준 하나 풀고 자신감을 얻는 나.
문제에서 쓰는 알고리즘도 미리 알고 시작했지만 자존감은 올렸죠?그거면 된거야.