[BOJ 19638] 센티와 마법 뿅망치

문제 분석

• 제한 시간 1초: Big-O기준 약 1억 연산
• 인구수 100,000 , 뿅망치 횟수 제한 100,000 -> 모든 인구에게 망치질 하는 거 불가능
• 가장 큰 놈이 센티 보다 작으면 YES다.
• 망치 다써도 센티 보다 큰 놈이 하나라도 있으면 NO다.

풀이 방식

• priority_queue(pq) 사용
• 아래 행위를 망치 제한 만큼 반복
  • 가장 큰 거인 을 망치로 때려 다시 pq에 삽입
  • 가장 큰 거인이 센티 보다 작으면 "YES"출력 후 프로그램 종료
• 제한이 끝났는데 "YES" 출력 못했으면 "NO" 출력

주의 사항

• 거인의 키가 1이면 더이상 줄일 수 없다
• 센티가 처음부터 거인들 보다 더 클수도 있다.

priority_queue<int> giants;
int n, h, t;
int tmp;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> n >> h >> t;
    while (n--) { //거인들 키 pq에 삽입
        int H;
        cin >> H;
        giants.push(H);
    }
    if (h > giants.top()) { //망치 안쓰고도 센티가 제일 큰 경우
        cout << "YES\n0";
        return 0;
    }
    for (int i = 1; i <= t; i++) {
        if (giants.top() != 1) { //거인 키가 1이면 못때림
            tmp = giants.top() / 2; //거인 키를 줄여서
            giants.pop();
            giants.push(tmp); //다시 pq에 삽입
        }
        if (h > giants.top()) { //가장 큰 거인보다 센티가 크게되면 
            cout << "YES\n" << i; //"YES"출력 후
            return 0; //프로그램 종료
        }
    }
    //망치 다썼으면
    cout << "NO\n" << giants.top(); 

    return 0;
}

느낀 점

• priority_queue를 써야한다는 생각이 든 후에는 금방 풀었다.
• 거인 키가 1인 경우엔 줄이지 못한다는 점 이나, 센티가 처음부터 거인들 보다 클 수 있다는 생각은 좀 나중에 들어 그 부분이 아쉽다.
• 이제 pq사용이 조금은 익숙해 진거 같아 뿌듯하다.

시간복잡도

• while문 : O(n)
• pq.push : O(logn)
• pq.top : O(1)
• pq.pop : O(logn)
• for문 : O(n)
  ➣ O(nlogn)