99클럽 코테 스터디_4기 20일차 TIL

TODAY TIL

안녕하세요, 오늘은 재미있는 코딩 문제를 함께 풀어보겠습니다. 이 문제는 센티라는 캐릭터가 마법의 뿅망치를 사용하여 자신보다 키가 큰 거인들을 줄여야 하는 상황입니다. 어떤 전략을 세우고 어떻게 코드를 구현했는지 차근차근 설명하겠습니다.

문제 설명

센티는 여행 중 거인의 나라에 도착했습니다. 그곳에는 자신보다 키가 크거나 같은 거인들이 많았는데, 센티는 이들을 마법의 뿅망치를 이용해 키를 줄이려 합니다. 마법의 뿅망치에 맞으면 키는 ⌊현재 키 / 2⌋로 줄어듭니다. 단, 키가 1이면 더 이상 줄어들지 않습니다. 이 마법의 뿅망치는 사용 횟수 제한이 있습니다.

목표: 센티가 마법의 뿅망치를 전략적으로 사용해 모든 거인이 센티보다 키가 작아지게 할 수 있는지를 판단하고, 그 과정에서 최소 사용 횟수를 출력합니다.

입력 형식

• 첫 번째 줄에 거인의 수 N, 센티의 키 HcentiH_{\text{centi}}Hcenti​, 마법의 뿅망치 사용 제한 T가 주어집니다.
• 두 번째 줄부터 N개의 줄에 각 거인의 키가 주어집니다.

출력 형식

• 마법의 뿅망치를 사용하여 모든 거인의 키가 HcentiH_{\text{centi}}Hcenti​보다 작다면 "YES"와 사용한 횟수를 출력합니다.
• 그렇지 않다면 "NO"와 뿅망치 사용 후 가장 큰 거인의 키를 출력합니다.

문제 풀이 접근법

1. 최대 힙을 이용한 거인 선택:
   • 거인들 중 가장 키가 큰 거인을 빠르게 선택하기 위해 최대 힙을 사용합니다.
   • Python의 heapq 모듈은 기본적으로 최소 힙이므로, 음수로 변환하여 최대 힙처럼 사용합니다.
2. 마법의 뿅망치 사용 전략:
   • 가장 키가 큰 거인을 때리고 줄어든 키를 다시 최대 힙에 넣습니다.
   • 키가 1인 경우는 줄일 수 없으므로 무시합니다.
   • 제한된 사용 횟수 T를 초과하지 않도록 합니다.
3. 결과 판단:
   • 마법의 뿅망치를 사용한 후, 모든 거인의 키가 HcentiH_{\text{centi}}Hcenti​보다 작으면 성공이고, 그렇지 않다면 실패입니다.

코드 구현

 

import heapq

# 입력 처리
N, H_centi, T = map(int, input().split())
giants = []

for _ in range(N):
    height = int(input())
    heapq.heappush(giants, -height)  # 최대 힙을 위해 음수로 저장

# 마법의 뿅망치 사용 횟수 카운트
use_count = 0

# 뿅망치 사용
while use_count < T and -giants[0] >= H_centi:
    tallest = -heapq.heappop(giants)
    
    if tallest == 1:
        # 키가 1이면 더 이상 줄어들 수 없음
        heapq.heappush(giants, -tallest)
        break
    
    # 뿅망치를 사용하여 키 줄이기
    new_height = tallest // 2
    heapq.heappush(giants, -new_height)
    use_count += 1

# 결과 확인
if -giants[0] < H_centi:
    print("YES")
    print(use_count)
else:
    print("NO")
    print(-giants[0])

 

코드 설명

1. 입력 처리:
   • 첫 번째 줄에서 거인의 수, 센티의 키, 마법의 뿅망치 사용 제한을 읽어옵니다.
   • 각 거인의 키를 음수로 변환하여 최대 힙에 저장합니다.
2. 반복문:
   • 최대 TTT번의 반복 동안 가장 키가 큰 거인을 선택하여 키를 절반으로 줄입니다.
   • 줄어든 키는 다시 힙에 삽입하여 다음 최댓값을 구할 수 있도록 합니다.
   • 키가 1인 거인은 더 이상 줄일 수 없으므로 바로 종료합니다.
3. 출력:
   • 모든 거인의 키가 센티보다 작아졌다면 YES와 사용 횟수를 출력합니다.
   • 그렇지 않다면 NO와 가장 큰 거인의 키를 출력합니다.

시간 및 공간 복잡도

• 시간 복잡도: O((T+N)log⁡N)O((T + N) \log N)O((T+N)logN)
• 공간 복잡도: O(N)O(N)O(N)

결론

이 문제는 우선순위 큐를 이용하여 가장 큰 값을 효율적으로 처리하는 방법과 제한된 자원을 최적화하여 사용하는 전략을 익히는 데 유용합니다. 블로그 포스팅을 통해 이와 같은 문제의 해결 방법을 체계적으로 학습해 보세요!

이제 여러분도 센티와 함께 거인의 나라를 정복해 보세요! 😊