[C++] 백준 온라인 저지 10162번 전자레인지 풀이

전자레인지 버튼을 몇 번 누르면 가장 적은 횟수로 T초를 정확하게 맞출 수 있는지 구하는 문제

 

---

문제의 조건

 

1. 전자레인지에 데울 냉동식품의 조리시간 T가 주어진다. 

 

2. 전자레인지에는 A, B, C 버튼 세 개가 있다. 

각 버튼을 누르면 5분, 1분, 10초 타이머가 설정된다. 

 

3. 세 버튼만 이용해서 정확하게 T초를 맞춰야 한다. 

 

4. 세 버튼을 이용한 횟수를 모두 출력하는데 누른 적 없는 버튼은 0 출력하면 된다. 

만약 정확하게 T초를 만들 수 없으면 -1만 출력한다. 

 

---

풀이 과정

 

전형적인 그리디 문제입니다. 

출처에 초등부라고 되 있길래 초딩들도 푸는데 혹시 못 푸면 어쩌지..^^;; 했는데 다행히 통과했습니다. 

 

과정

1. 전자레인지 버튼들에 지정된 시간을 저장할 배열과 각 버튼을 누른 횟수를 저장할 배열을 만든다. 

타이머 시간이 긴 순서대로 앞으로 오도록 내림차순 정렬한다. 

 

2. 전자레인지 버튼 시간 배열의 0번째 인덱스부터 남은 시간과 비교해서 

현재 인덱스가 남은 시간보다 적거나 같으면 그만큼 감소시키고 버튼 누른 횟수 증가

아니면 인덱스를 증가시킨다. 

 

3. 위 과정을 마지막 인덱스까지 탐색할 때까지 반복

 

4. 마지막 인덱스까지 탐색했는데 정확하게 T초를 만들지 못 했으면 -1을 출력하고

만들었으면 버튼 누른 횟수를 차례대로 출력한다. 

 

---

 

#include <iostream>
#include <vector>

using namespace std;

int main(int argc, const char * argv[])
{
    int T;
    cin >> T;
    
    vector<int> buttons{300, 60, 10};
    vector<int> counts(buttons.size(), 0);
    int index = 0;
    
    while (buttons.size() > index)
    {
        if (T >= buttons[index])
        {
            int count = T / buttons[index];
            counts[index] = count;
            T -= count * buttons[index];
        }
        else
            index++;
    }
    
    if (0 != T)
        cout << -1;
    else
    {
        for (auto c: counts)
            cout << c << " ";
    }
    
    return 0;
}

 

 

근데 서브태스크는 뭐죵?

오랜만에 100점 맞아서 좋아요!