[백준] 1092번 배
-
풀이
- 크레인 리스트, 박스 리스트 내림차순 정렬
- 모든 크레인에 대해 이동 가능한 무게의 박스 각각 저장
- 모든 크레인을 돌면서 이동 가능한 무게의 박스 중아직 이동하지 않은 박스 이동
- 3번을 모두 이동할 때까지 반복
-
소감
- 혼자 시도했던 풀이가 시간 초과가 나서 검색해서 나온 풀이를 참고했다
- 정답 풀이와 다른 점은
- 나는 이동이 안 된 박스를 찾을 때 전체 박스에 대해 탐색을 했고
- 정답은 가능한 무게의 박스만 탐색을 해서 그런 것 같다
틀린 코드
def init():
n = int(input(''))
crane_list = list(map(int, input('').split(' ')))
m = int(input(''))
box_list = list(map(int, input('').split(' ')))
return n, m, crane_list, box_list
def get_box_idx(crane_idx, box_idx, box_excluded):
while box_idx < m:
if not box_excluded[box_idx]:
if crane_list[crane_idx] >= box_list[box_idx]:
return box_idx
box_idx += 1
return -1
def get_time():
if max(crane_list) < max(box_list):
return -1
crane_list.sort(reverse=True)
box_list.sort(reverse=True)
crane_excluded = [False] * n
box_excluded = [False] * m
count = 0
while True:
crane_idx = 0
box_idx = -1
finished = False
while crane_idx < n and box_idx < m:
box_idx = get_box_idx(crane_idx, box_idx+1, box_excluded)
if crane_idx == 0 and box_idx < 0:
finished = True
break
box_excluded[box_idx] = True
count += 1
crane_idx += 1
if finished:
break
return count
n, m, crane_list, box_list = init()
result = get_time()
print(result)
맞은 코드
def get_time():
# 이동이 불가능할 경우
if max(box_list) > max(crane_list):
return -1
# 내림차순으로 정렬
crane_list.sort(reverse=True)
box_list.sort(reverse=True)
# 각 크레인 별 이동 가능 박스 저장
crane_dict = dict()
for i in range(n):
for j in range(m):
if crane_list[i] >= box_list[j]:
if crane_list[i] not in crane_dict:
crane_dict[crane_list[i]] = []
crane_dict[crane_list[i]].append(j)
answer = 0
move_count = 0
moved = [False] * m
# 모두 다 옮길 때까지 반복
while move_count < m:
answer += 1
# 모든 크레인에 대해
for i in range(n):
if crane_list[i] in crane_dict:
# 이동 가능한 박스 반복
for j in crane_dict[crane_list[i]]:
if not moved[j]:
moved[j] = True
move_count += 1
break
return answer
n = int(input(''))
crane_list = list(map(int, input('').split(' ')))
m = int(input(''))
box_list = list(map(int, input('').split(' ')))
result = get_time()
print(result)
Author And Source
이 문제에 관하여([백준] 1092번 배), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다
https://velog.io/@leehj8896/백준-1092번-배
저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념
(Collection and Share based on the CC Protocol.)
def init():
n = int(input(''))
crane_list = list(map(int, input('').split(' ')))
m = int(input(''))
box_list = list(map(int, input('').split(' ')))
return n, m, crane_list, box_list
def get_box_idx(crane_idx, box_idx, box_excluded):
while box_idx < m:
if not box_excluded[box_idx]:
if crane_list[crane_idx] >= box_list[box_idx]:
return box_idx
box_idx += 1
return -1
def get_time():
if max(crane_list) < max(box_list):
return -1
crane_list.sort(reverse=True)
box_list.sort(reverse=True)
crane_excluded = [False] * n
box_excluded = [False] * m
count = 0
while True:
crane_idx = 0
box_idx = -1
finished = False
while crane_idx < n and box_idx < m:
box_idx = get_box_idx(crane_idx, box_idx+1, box_excluded)
if crane_idx == 0 and box_idx < 0:
finished = True
break
box_excluded[box_idx] = True
count += 1
crane_idx += 1
if finished:
break
return count
n, m, crane_list, box_list = init()
result = get_time()
print(result)
def get_time():
# 이동이 불가능할 경우
if max(box_list) > max(crane_list):
return -1
# 내림차순으로 정렬
crane_list.sort(reverse=True)
box_list.sort(reverse=True)
# 각 크레인 별 이동 가능 박스 저장
crane_dict = dict()
for i in range(n):
for j in range(m):
if crane_list[i] >= box_list[j]:
if crane_list[i] not in crane_dict:
crane_dict[crane_list[i]] = []
crane_dict[crane_list[i]].append(j)
answer = 0
move_count = 0
moved = [False] * m
# 모두 다 옮길 때까지 반복
while move_count < m:
answer += 1
# 모든 크레인에 대해
for i in range(n):
if crane_list[i] in crane_dict:
# 이동 가능한 박스 반복
for j in crane_dict[crane_list[i]]:
if not moved[j]:
moved[j] = True
move_count += 1
break
return answer
n = int(input(''))
crane_list = list(map(int, input('').split(' ')))
m = int(input(''))
box_list = list(map(int, input('').split(' ')))
result = get_time()
print(result)
Author And Source
이 문제에 관하여([백준] 1092번 배), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@leehj8896/백준-1092번-배저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)