266. 센티와 마법의 뿅망치
1) 어떤 전략(알고리즘)으로 해결?
힙
2) 코딩 설명
<내 풀이>
from heapq import heappop, heappush
import math
import sys
# 인구수, 센티의 키, 뿅망치 횟수 제한
n,h,t = map(int, sys.stdin.readline().split())
giant=[]
use=0
for _ in range(n) :
target = int(sys.stdin.readline())
heappush(giant, (-target, target))
for _ in range(t):
nowminus, now = heappop(giant)
if abs(now)<h :
heappush(giant, (-abs(now), abs(now)))
break
elif abs(now)==1 :
heappush(giant, (-1, 1))
break
else :
heappush(giant, (-1*(abs(now)//2),abs(now)//2))
use+=1
if giant[0][1] >= h:
print("NO")
print(giant[0][1])
else :
print("YES")
print(use)
< 내 틀렸던 풀이, 문제점>
67%에서 틀리는 풀이 ㅇㅁㅇ
from heapq import heappop, heappush
import sys
# 인구수, 센티의 키, 뿅망치 횟수 제한
n,h,t = map(int, sys.stdin.readline().split())
giant=[]
use=0
for i in range(n) :
target = int(sys.stdin.readline())
heappush(giant, (-target, target))
while giant and giant[0][1] >1 and giant[0][1] > h and t > 0 :
nowminus, now = heappop(giant)
heappush(giant, (nowminus//2, now//2))
t-=1
use+=1
if (t==0 and giant[0][1] >= h) or giant[0][1] >= h:
print("NO")
print(giant[0][1])
else :
print("YES")
print(use)
73
from heapq import heappop, heappush
import math
import sys
# 인구수, 센티의 키, 뿅망치 횟수 제한
n,h,t = map(int, sys.stdin.readline().split())
giant=[]
use=0
for _ in range(n) :
target = int(sys.stdin.readline())
heappush(giant, (-target, target))
while t>0 :
t-=1
nowminus, now = heappop(giant)
if now<h :
heappush(giant, (nowminus, now))
break
elif now==1 :
heappush(giant, (-1, 1))
break
else :
heappush(giant, (nowminus//2,now//2))
use+=1
if giant[0][1] >= h:
print("NO")
print(giant[0][1])
else :
print("YES")
print(use)
- 아아 마이너스인 경우를 고려안해서 틀린 것이었음
else :
heappush(giant, (nowminus//2,now//2))
use+=1- 이 부분에서 무지성으로 저렇게 넣었었음
