알고리즘/문제풀이

구현(센티와 마법의 뿅망치/S1) - 19638번

문승주 2022. 12. 14. 21:12
반응형

1. 문제

센티는 마법 도구들을 지니고 여행을 떠나는 것이 취미인 악당이다.

거인의 나라에 도착한 센티는 자신보다 키가 크거나 같은 거인들이 있다는 사실이 마음에 들지 않았다.

센티가 꺼내 들은 마법 도구는 바로 마법의 뿅망치로, 이 뿅망치에 맞은 사람의 키가 ⌊ 뿅망치에 맞은 사람의 키 / 2 ⌋로 변하는 마법 도구이다. 단, 키가 1인 경우 더 줄어들 수가 없어 뿅망치의 영향을 받지 않는다.

하지만 마법의 뿅망치는 횟수 제한이 있다. 그래서 센티는 마법의 뿅망치를 효율적으로 사용하기 위한 전략을 수립했다. 바로 매번 가장 키가 큰 거인 가운데 하나를 때리는 것이다.

과연 센티가 수립한 전략에 맞게 마법의 뿅망치를 이용한다면 거인의 나라의 모든 거인이 센티보다 키가 작도록 할 수 있을까?

 

2. 입력

첫 번째 줄에는 센티를 제외한 거인의 나라의 인구수 N (1 ≤ N ≤ 105)과 센티의 키를 나타내는 정수 Hcenti (1 ≤ Hcenti ≤ 2 × 109), 마법의 뿅망치의 횟수 제한 T (1 ≤ T ≤ 105)가 빈칸을 사이에 두고 주어진다.

두 번째 줄부터 N개의 줄에 각 거인의 키를 나타내는 정수 H (1 ≤ H ≤ 2 × 109)가 주어진다.

1 10 1
20

 

2 10 3
16
32

 

2 10 3
127
8

 

1 1 100000
1

 

3. 출력

마법의 뿅망치를 센티의 전략대로 이용하여 거인의 나라의 모든 거인이 센티보다 키가 작도록 할 수 있는 경우, 첫 번째 줄에 YES를 출력하고, 두 번째 줄에 마법의 뿅망치를 최소로 사용한 횟수를 출력한다.

마법의 뿅망치를 센티의 전략대로 남은 횟수 전부 이용하고도 거인의 나라에서 센티보다 키가 크거나 같은 거인이 있는 경우, 첫 번째 줄에 NO를 출력하고, 두 번째 줄에 마법의 뿅망치 사용 이후 거인의 나라에서 키가 가장 큰 거인의 키를 출력한다.

NO
10

 

YES
3

 

NO
15

 

NO
1

 

4. 코드

import sys
import heapq

n, h, t = list(map(int, sys.stdin.readline().split()))
# 음수로 배열을 입력받는다
giants = [-int(sys.stdin.readline()) for _ in range(n)]

# 리스트를 힙으로 변경
heapq.heapify(giants)

check = "NO"
for i in range(t + 1):
  # 힙의 최소값의 절댓값 
  max = abs(giants[0])
  if max >= h:
    if i == t or max == 1:
      result = max
      break
    # 힙의 최대값을 변경
    heapq.heapreplace(giants, -(max // 2))
  else:
    check = "YES"
    result = i
    break

print(check)
print(result)

 

5. 풀이설명

① 변수 n, h, t를 입력받는다.

 

② 음수로 giants 배열을 입력받는다.

 

③ giants 리스트를 heapify 함수로 힙으로 변경한다. (내림차순 정렬)

 

④ check 변수를 "NO"로 생성한다.

 

⑤ 반복문 실행시 giaint[0] (최소값)의 절댓값을 max에 대입한다.

- max가 h(센티의 키)보다 크거나 같을경우 heap의 최소값을 절댓값으로 치환하여 2로 나누고 변경한다. 이때

  마지막 반복문이거나 max 값이 1이면 결과값에 max 값을 대입하고 반복문을 종료한다.

- max가 h보다 작을 경우

  check 값을 "TRUE"로 변경 결과값에 i를 대입하고 반복문을 종료한다.

 

⑥ result와 check를 출력한다.

 

6. 느낀점

처음에는 배열을 사용하여 문제를 풀었는데 시간초과로 실패하였다. 구글링후 힙 자료구조의 오름차순 정렬을 이용해서 문제를 풀었다.

 

 

 

 

 

 

 

 

반응형