Koala - 10기/코딩테스트 준비 스터디
[백준/Python] 17179 : 케이크 자르기
허수민
2023. 4. 1. 16:27
17179번: 케이크 자르기
첫 번째 줄에 자르는 횟수가 담긴 목록의 길이 N과 자를 수 있는 지점의 개수 M, 그리고 롤 케이크의 길이인 정수 L이 주어진다. (1 ≤ N ≤ M ≤ 1,000, 1 < L ≤ 4,000,000) 다음 M줄에 걸쳐 자를 수 있는
www.acmicpc.net
소스코드
코드설명
- N,M,L과 M개의 자를 수 있는 지점을 나타내는 정수 리스트 pnt, N명의 예상 친구 수를 나타내는 정수 리스트 frd 입력
- frd 내의 자르는 횟수마다 반복
- 자를 수 있는 케이크의 길이를 기준으로 설정해 start는 1, end는 가장 긴 L, 답을 저장할 ans는 0으로 설정
- mid는 start와 end 중간값, count는 fun(mid)의 반환값
- pnt 리스트 내의 정수 기준으로 자를 것이므로 현재 정수 i와 temp의 차가 mid보다 크거나 같다면 자를 수 있으니 자른 횟수 count를 1증가, temp를 현재 정수 i로 변경
- mid보다 작다면 현재 정수 i만 pnt내의 다음 정수로 변경, 나머지 그대로
- pnt 내 마지막 정수와의 차까지 구한 후 count의 값을 반환
- count의 값이 친구 수 i와 비교
- i가 count보다 작다면 mid의 크기가 작다는 의미이므로 start를 mid+1로 변경, ans를 현재 ans의 값과 mid 중 더 큰 수로 변경
- i가 count보다 크거나 같다면 mid의 크기가 크다는 의미이므로 end를 mid-1변경
- start가 end보다 커지면 while문 종료 후 답 ans 출력