https://www.acmicpc.net/problem/1756
문제 설명이 불충분하여 이해하기부터 무척 어려웠던 문제..
문제를 차근차근 설명해보고자 하니 여러분들은 이글만 읽고도 이해해서 푸실 수 있기를.....
피자 오븐은 이렇게 생겼다.
0. 문제 내 오타
그런데 그림을 자세히 보다보면 헷갈릴 수 있음. 분명 오븐 크기는 5 6 4 3... 이라고 했는데 5칸이 아니라 10칸이고 6칸이아니라 12칸일 것이다.
문제 내용에 오타가 있는데 '지름'이 아니라 '반지름'이 5 6 4 3... 이다. 그래서 그림을 보려면 반절만 봐야한다.
1. 오븐 크기를 재정렬하자.
문제를 본격적으로 풀기 전, 오븐 크기를 재정렬해야한다.
왜냐하면 도우는 위에서 아래로 떨어지는데, 오븐 크기보다 크면 들어올 수가 없다.
좀 더 상세히 설명해보겠다.
그림처럼 5 크기의 도우가 내려온다고 가정해보면
두번째 오븐의 크기가 5 이상으로 아무리 커도 첫번째 오븐인 5에서 걸린다.
그래서 무조건 (이전 오븐의 크기인) 5 이하의 도우들만 내려올 수 있다.
결론적으로, 우리는 이전 오븐 크기를 보고 현재 오븐 크기보다 작으면 그 크기로 변경해야한다.
for i in range(len(oven)-1):
if oven[i] < oven[i+1]:
oven[i+1] = oven[i]그래서 위 코드를 통해 오븐 크기를 변경하면
5 6 4 3 3 2 3 이 5 5 4 3 3 2 2 로 변경된다.
2. 반죽을 넣자
이제 반죽을 넣기만 하면 된다. 그러면 구현해야 할 것을 정리해보자.
- 오븐 크기만큼 순회한다
- 현재 오븐의 크기보다 도우의 크기가 "작다"면 통과
- 크다면 오븐을 다시 순회한다.
이걸 그대로 구현해보았다.
result = 0
oven_idx = len(oven)-1
break_count = 0
# for문을 이용하여 도우를 하나씩 가져온다
for d in dough:
# 1. 오븐 크기만큼 순회한다
while oven_idx >= 0:
# 2. 현재 오븐의 크기보다 도우의 크기가 "작다"면 통과한다
if d <= oven[oven_idx]:
result = oven_idx
oven_idx -= 1
break_count += 1
break
else:
oven_idx -= 1
나는 여기서 break_count라는 변수를 넣어줬는데, 마지막에 출력할 때
진짜 없어서 0인건지, 아니면 첫번째 오븐에 있는건지(리스트는 0부터 시작) 모르기 때문에 break_count를 넣어주어서 break를 몇번하였는지 조사하였다.
(break가 도우의 수와 같다면 첫번째 오븐에 있는 것)
3. 전체 코드
D, N = map(int,input().split())
oven = list(map(int, input().split()))
dough = list(map(int,input().split()))
# 1. oven 을 재정렬한다 -> 이전 오븐을 기준으로 그것보다 큰 도우는 들어갈 수 없음
# ex) 5 6 4 3 6 2 3 -> 5 5 4 3 3 2 2
for i in range(len(oven)-1):
if oven[i] < oven[i+1]:
oven[i+1] = oven[i]
# 2. 반죽을 넣는다.(성공)
result = 0
oven_idx = len(oven)-1
break_count = 0
for d in dough:
while oven_idx >= 0:
print('테스트용 : ', oven_idx, oven[oven_idx])
if d <= oven[oven_idx]:
result = oven_idx
oven_idx -= 1
break_count += 1
print('-----break-----')
break
else:
oven_idx -= 1
if break_count == len(dough):
print(result+1)
else:
print(result)4. 회고
원래는 이분탐색으로 풀어야 하는 문제라고 한다. 아무리 생각해봐도 어떻게 구현해야할지 모르겠어서 막구현을 했는데, 이분탐색으로 구현할 수 있는 방법을 찾아봐야겠다.
