문제: https://www.acmicpc.net/problem/1654
재미있게 푼 문제였다. 문제를 읽으면서 이분탐색을 해서 최대값을 찾아야할지, 그리디로 풀 수 있을지 고민했다.
"N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다." 라는 말 때문에 최선의 선택을 하면서 분기점이 넘어가는 순간을 찾으면 되겠다고 생각해서 그리디로 풀어보았다.
k, n = map(int, input().split())
cables = [int(input()) for _ in range(k)]
cables.sort()
divide_num = sum(cables)//n
while True:
c_num = 0
temp_list = [0, 0, 0]
for i in range(k):
c_num += cables[i]//(divide_num)
print(cables[i], cables[i]//divide_num, cables[i]% divide_num)
if cables[i] % divide_num >= temp_list[2]:
temp_list[0] = i
temp_list[1] = cables[i]//divide_num
temp_list[2] = cables[i]% divide_num
print(temp_list)
if c_num < n:
divide_num = cables[temp_list[0]]//(temp_list[1]+1)
print(divide_num)
else:
print(divide_num)
break
그런데 계속 오답이라고 떴다ㅜㅜ.. 엣지케이스도 넣어보고 다른 예시도 넣어보았는데 감이 안잡혔다.
질문 게시판의 반례들을 한 3페이지 넘어갈때까지 대입해봐도 다 맞았다..
그러다 이 반례를 보고 틀린 부분을 찾았다.
25 421
25468
42380
34638
19901
35751
24933
15368
854
24429
35451
32479
22039
24149
45061
34767
5716
13347
11121
19624
12193
34154
24840
40357
5152
42609
답이 1443이 나와야하는데, 내 코드는 1429가 나오고 있었다.
코드 상 1461 다음의 최대값을 찾은 것이 1429가 되고 있었다.
여기서 그리디로 풀 게 아니라, 이분탐색을 적용해 전체 수에 대해 탐색을 해야한다는 것을 알았다.
k, n = map(int, input().split())
cables = [int(input()) for _ in range(k)]
start, end = 1, max(cables)
while start <= end:
c_num = 0
divide_num = (start + end) //2
for i in range(k):
c_num += cables[i] // divide_num
if c_num < n:
end = divide_num - 1
else:
start = divide_num + 1
print(end)
이분탐색으로 다시 짠 코드이다.
이분탐색 개념은 잘 알고있지만 코드로 짜는건 익숙하지 않았는데, 이참에 연습을 며칠동안 해보면 좋을 것 같다.
'코딩테스트' 카테고리의 다른 글
[Python] 백준 14502번 - 연구소 (0) | 2023.07.12 |
---|---|
[Python] 백준 18870번 - 좌표 압축 (0) | 2023.07.11 |
[Python] 백준 5427번 - 불 (0) | 2023.06.29 |
[Python] 백준 2583번 - 영역 구하기 (0) | 2023.06.14 |
[Python] 백준 12904번 - A와 B (1) | 2023.06.13 |