99클럽 코테 스터디 21일차 TIL
오늘의 학습 키워드
힙
과제
문제
센티는 마법 도구들을 지니고 여행을 떠나는 것이 취미인 악당이다.
거인의 나라에 도착한 센티는 자신보다 키가 크거나 같은 거인들이 있다는 사실이 마음에 들지 않았다.
센티가 꺼내 들은 마법 도구는 바로 마법의 뿅망치로, 이 뿅망치에 맞은 사람의 키가 ⌊ 뿅망치에 맞은 사람의 키 / 2 ⌋로 변하는 마법 도구이다. 단, 키가 1인 경우 더 줄어들 수가 없어 뿅망치의 영향을 받지 않는다.
하지만 마법의 뿅망치는 횟수 제한이 있다. 그래서 센티는 마법의 뿅망치를 효율적으로 사용하기 위한 전략을 수립했다. 바로 매번 가장 키가 큰 거인 가운데 하나를 때리는 것이다.
과연 센티가 수립한 전략에 맞게 마법의 뿅망치를 이용한다면 거인의 나라의 모든 거인이 센티보다 키가 작도록 할 수 있을까?
입력
첫 번째 줄에는 센티를 제외한 거인의 나라의 인구수 N (1 ≤ N ≤ 105)과 센티의 키를 나타내는 정수 Hcenti (1 ≤ Hcenti ≤ 2 × 109), 마법의 뿅망치의 횟수 제한 T (1 ≤ T ≤ 105)가 빈칸을 사이에 두고 주어진다.
두 번째 줄부터 N개의 줄에 각 거인의 키를 나타내는 정수 H (1 ≤ H ≤ 2 × 109)가 주어진다.
출력
마법의 뿅망치를 센티의 전략대로 이용하여 거인의 나라의 모든 거인이 센티보다 키가 작도록 할 수 있는 경우, 첫 번째 줄에 YES를 출력하고, 두 번째 줄에 마법의 뿅망치를 최소로 사용한 횟수를 출력한다.
마법의 뿅망치를 센티의 전략대로 남은 횟수 전부 이용하고도 거인의 나라에서 센티보다 키가 크거나 같은 거인이 있는 경우, 첫 번째 줄에 NO를 출력하고, 두 번째 줄에 마법의 뿅망치 사용 이후 거인의 나라에서 키가 가장 큰 거인의 키를 출력한다.
예제 입력 1 복사
1 10 1
20
예제 출력 1 복사
NO
10
예제 입력 2 복사
2 10 3
16
32
예제 출력 2 복사
YES
3
예제 입력 3 복사
2 10 3
127
8
예제 출력 3 복사
NO
15
예제 입력 4 복사
1 1 100000
1
예제 출력 4 복사
NO
1
풀이 과정
import sys,from heapq import *:- 시스템 모듈과 힙 큐의 모든 함수를 가져옵니다
- 입력 처리와 최대 힙 구현에 사용됩니다
input = sys.stdin.readline:- 더 빠른 입력 처리를 위해 readline을 사용합니다
n, h, t = map(int, input().split()):- n: 거인의 수
- h: 센티의 키
- t: 최대 시도 가능 횟수를 입력받습니다
titan = []:- 빈 리스트를 생성합니다
- 최대 힙으로 사용될 공간입니다
- 거인들의 키 입력 부분:
- 각 거인의 키를 입력받아 음수로 변환하여 최대 힙에 추가합니다
- 최소 힙을 최대 힙처럼 사용하기 위한 테크닉입니다
- 반복문에서:
- t번까지 시도할 수 있으며
- 두 가지 조건을 모두 만족할 때만 연산을 수행합니다:
- 거인의 키가 1이 아니고 (
-titan[0] != 1) - 거인의 키가 센티보다 크거나 같을 때 (
-titan[0] >= h)
- 거인의 키가 1이 아니고 (
heapreplace를 사용해 최댓값을 꺼내고 반으로 나눈 값을 바로 넣습니다- 연산 횟수(cnt)를 1 증가시킵니다
- 최종 결과 출력:
- 만약 가장 큰 거인의 키가 여전히 센티 이상이면:
- "NO"와 그 거인의 키를 출력
- 모든 거인의 키를 센티보다 작게 만들었다면:
- "YES"와 수행한 연산 횟수(cnt)를 출력
- 만약 가장 큰 거인의 키가 여전히 센티 이상이면:
제출 코드 (python)
import sys
from heapq import *
input = sys.stdin.readline
n, h, t = map(int, input().split())
titan = []
for _ in range(n):
heappush(titan, -int(input()))
cnt = 0
for _ in range(t):
if -titan[0] != 1 and -titan[0] >= h:
heapreplace(titan, -(-titan[0] // 2))
cnt += 1
if -titan[0] >= h:
print("NO")
print(-titan[0])
else:
print("YES")
print(cnt)오늘의 회고
- 전에 사용한 heapq모듈을 이용해서 다시 한번 풀어 보았다.