📃 문제
백준 18111번 마인크래프트
알고리즘 - 구현
문제 요약
세로N, 가로M, 인벤토리내 재고수 B를 입력받는다.
N x M 크기 집터는 (0,0) ~ (N-1, M-1) 인 셈이다.
이 집터의 땅의 높이를 일정하게 바꿔야 한다.
- (i,j)의 블럭을 제거하여 인벤토리에 넣는다 : 2초
- 인벤토리에서 블록 하나 꺼내어 (i,j)에 오린다 : 1초
땅 고르기 작업에 거리는 최소 시간과 그 경우 땅의 높이가 가장 높은 것 출력한다.
예제 해석
3 4 99 0 0 0 0 0 0 0 0 0 0 0 12 0
1층인 블록을 하나 없애는게 2초이고
나머지 0 층을 모두 1층으로 올리려면 11초
3 4 1 64 64 64 64 64 64 64 64 64 64 64 631 64
63층을 하나 올리는게 1초
나머지 64층을 모두 한층 내리면 22초
3 4 0 64 64 64 64 64 64 64 64 64 64 64 6322 63
위와 같은 집터지만, 인벤토리에 재고가 없다!
따라서 하나 올리는게 불가능하다!!
인벤토리 재고도 주의해야한다 !!!!!!!!!!!!!!
💡 시도 과정
1) 이분탐색 ( 😵 )
지금 < 만드려는 수 : 차이만큼인벤에서 꺼내와야함. 근데 인벤에 있는만큼만 가능..
- ( 만들려는 수 - 지금 ) > 인벤 이면, 반복 멈추고 만들려는수를 낮춰야함.그러려면 m = e
- 인벤에서 꺼내올 수 있으면: 시간 += 꺼내온만큼, 인벤 -= 꺼내온만큼
지금 > 만드려는 수 : 빼야됨.
- 시간 += 뺀만큼x2, 인벤 += 뺀만큼
주의 1 : 인벤 재고가 있는지
2 3 0 1 1 1 9 9 9라면
1층인 땅 확인시에 인벤 재고가 없어서 채울수가 없다 ..
하지만 9층을 먼저 검사한다면 인벤 재고가 쌓여서 가능할 것이다.
-> 정렬이 필요하다 ?! 그리고 2차원으로 생각할 필요가 없다!
주의 2 : 최소시간인 경우 만들 수 있는 땅의 높이가 가장 높은! 것을 출력한다.
1 3 68 0 0 1 >> 2 10층으로 만드는 경우, 1층으로 만드는 경우 모두 2초가 걸리지만 더 높은 층인 1을 출력해야 한다!!
--> time==result인 경우 조건 추가
여기까지 코드 ⇩
최저층 ~ 최고층 범위에서 이분탐색 진행.
만드려는 층수 : m, 지금 조사하고 있는 땅의 층 each
import sys
input = sys.stdin.readline
n, m ,b = map(int, input().split())
li = []
for i in range(n):
li += list(map(int,input().split()))
li.sort(reverse=True)
e, s= li[0], li[-1]
result = 1000000
resultHeight = 0
while s<=e:
m = (s+e) //2
b2 = b #입력받은 인벤토리재고 b는 수정하면 안된다.
time = 0
flag = ''
for each in li:
if each < m : # 만드려는 층보다 낮으면
if (m - each) > b2 : # 인벤토리 재고가 부족한경우
flag = 'out of b'
break
else: # 인벤토리에서 가져올 수 있는 경우
time += (m-each)
b2 -= (m-each)
elif e > m : # 만드려는 층보다 높으면
time += (each-m) *2
b2 += (each-m)
if flag == 'out of b': # 인벤토리 초과인 경우 만들 층을 높인다. #### "문제점 "
e = m-1
else:
if time <result:
result = time
resultHeight = m
s = m+1 #
elif time == result :
resultHeight = max(m, resultHeight)
s = m+1
else:
e = m-1 #
print(result, resultHeight)
주의 3 : 위 코드에서 "문제점" 처럼, 이분탐색을 진행 중에 인벤토리 초과인 상황에서 만드려는 층을 높이면 안된다.
만드려는 층수가 높아지면, 인벤토리에서 가져오는 작업이 1초라서 개선이 될거라고 생각했지만, 그 작업이 몇개의 땅에 대해 발생할지 등 다른 영향이 있기 때문에 예외가 있다 !!!!!!!!!
2) 딕셔너리 사용
만드려는 층에 대하여 모든 땅을 확인해야하기 때문에 시간초과를 우려하여 딕셔너리를 사용해보았다.
주의 4 : 최소 시간이 같은 경우 더 높은 층을 h에 저장해두어야한다. time == mini 조건 추가!
주의 5 : mini 값의 초기화
실패한 코드에선, 인벤토리에 재고가 부족한 경우 걸리는 시간time을 9999정도의 값을 반환하게 했지만, 0 ≤ B ≤ 6.4 × 107 의 조건이 있다.. 재고 부족 경우에 걸리는 시간 경우의 수를 주의해야한다.
최종코드🩷
import sys
input = sys.stdin.readline
n, m ,b = map(int, input().split())
li = {}
for i in range(n):
row = list(map(int,input().split()))
for r in row:
if r in li:
li[r] +=1
else:
li[r] = 1
li = sorted(li.items(), reverse=True)
e, s = li[0][0], li[-1][0]
def checkTime(m): # 높이를 m으로 모두 맞추는데 드는 시간 return. 인벤이 부족해서 못만드는 경우라면 999999 반납
b2 =b
time = 0
flag = ""
for each in li:
if each[0] < m :
if (m - each[0]) * (each[1]) > b2 :
# 여기 지금 층을 인벤 다가져와서 해결 못한다면 어쨋거나 못만드는거니까 짤임
flag = 'out of b'
break
else:
time += (m-each[0]) * (each[1])
b2 -= (m-each[0]) * (each[1])
elif each[0] > m :
time += (each[0]-m)*(each[1]) *2
b2 += (each[0]-m)*(each[1])
if flag == "out of b":
return 9990909090909090999, m #9999 막 이정도로 해놓은게 문제였따 ^^
else:
return time,m
mini = 9990909090909090999
h = 0
for i in range(s, e+1): # 전체탐색
time, height = checkTime(i)[0], checkTime(i)[1]
if time <= mini:
h = height
mini = time
elif time == mini:
h = max(h,height)
print(mini, h)반례 모음
게시글에서 모으고 제가 만든 것 등등 이곳저곳에서 모아본 반례 모음임둥
3 4 11
29 51 54 44
22 44 32 62
25 38 16 2
>> 250 35
.
4 4 36
15 43 61 21
19 33 31 55
48 63 1 30
31 28 3 8
>> 355 32
.
3 4 0
64 64 64 64
64 64 64 64
64 64 64 63
>> 22 63
.
1 3 68
0 0 1
>> 2 1
.
3 4 11
29 51 54 44
22 44 32 62
25 38 16 2
>> 250 35
.
2 2 35
20 10
190 40
>> 350 40
.
7 7 6000
30 21 48 55 1 1 4
0 0 0 0 0 0 0
15 4 4 4 4 4 8
20 40 60 10 20 30 2
1 1 1 1 1 1 9
24 12 33 7 14 25 3
3 3 3 3 3 3 32
>> 879 10
.
2 2 68
120 90
250 170
>> 290 170
문법 정리
- 딕셔너리를 value값 기준으로 정렬
li = sorted(li.items(), reverse=True)
