[백준(BOJ)] 19638번 센티와 마법의 뿅망치 C++

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

19638번: 센티와 마법의 뿅망치

 

어떤 문제인가?

때리면 키가 키/2가 되는 뿅망치를 n번 때려 거인들의 키가 센티보다 작게 할 수 있는지 여부

 

할 수 있다 -> 뿅망치 사용 횟수 출력

할 수 없다 -> 가장 큰 거인의 키 출력

 

간단하게 정리해보면 위와 같다.

 

접근 방법

문제에서 키가 가장 큰 거인부터 때리라고 알려줬다.

그러면 일단 거인들을 키가 큰 순서대로 정렬해야 했다.

키를 다 입력하고 정렬을 한다면 시간 초과가 발생할 것 같아서 우선순위 큐를 사용하기로 결정했다.

priority_queue<int, vector<int>, less<int>> giant;

int N, H, T;
cin >> N >> H >> T;

for (int i = 0; i < N; i++) {
    int h;
    cin >> h;
    giant.push(h);
}

문제의 조건에 맞게 변수들을 선언하고 입력받는다.

그리고 N번만큼 거인들의 키를 입력받고 우선순위 큐에 추가한다.

 

for (int i = 0; i < T; i++) {
    int h = giant.top();

    if (h < H) {
        cout << "YES\n";
        cout << i << "\n";
        return 0;
    } else if (h > 1) {
        giant.pop();
        giant.push(h / 2);
    }
}

이제 반복문을 통해 연산을 할 것이다.

 

1. 만약 우선순위 큐의 top(가장 큰 거인의 키)가 센티의 키보다 작다면

더 이상 반복할 필요가 없으니 YES와 반복 횟수인 i를 출력해준다.

 

2. 1의 경우가 아니고 우선순위 큐의 top(가장 큰 거인의 키)가 1보다 크다면

우선순위 큐를 pop 하고 기존의 top/2를 추가해준다.

 

 

if (giant.top() >= H) {
    cout << "NO\n" << giant.top();
} else {
    cout << "YES\n" << T << "\n";
}

뿅망치 사용 횟수를 다 쓴 후에 반복문을 탈출한다.

이때 우선순위 큐의 top(가장 큰 거인의 키)가 센티의 키보다 크다면 실패한 것이다.

따라서 우선순위 큐의 top(가장 큰 거인의 키)을 출력해준다.

 

성공했다면, 이 경우에는 뿅망치 사용 횟수를 다 사용해서 성공한 것이니

입력받은 뿅망치 사용횟수 T를 출력하면 끝이다!

 

무엇이 어려웠는가?

이 문제 같은 경우는 문제에서 로직을 다 준 것이나 마찬가지라서 구현 부분에선 어려운 부분이 없었다.

문제를 읽고 우선순위 큐를 사용해야겠다고 생각했다면 쉽게 풀 수 있을 것이다.

 

 

배운 점

점점 문제의 조건과 제한 시간을 보고 자료구조를 선택하려고 노력하는 것이 보인다.

앞으로도 더 열심히 하자! 파이팅!