Inflearn Community Q&A
asked
6-I 질문있습니다.
Resolved
Written on
·
29
0
- 학습 관련 질문을 남겨주세요. 상세히 작성하면 더 좋아요!
- 먼저 유사한 질문이 있었는지 검색해보세요.
- 서로 예의를 지키며 존중하는 문화를 만들어가요.
- 잠깐! 인프런 서비스 운영 관련 문의는 1:1 문의하기를 이용해주세요.
http://boj.kr/e6389548e0ca4fc78ad5f26dcfbd6c1b
처음엔 다음과 같이 minPaLength로 가장 짧은 파를 찾아서 해당 값을 hi로 넣었습니다. 이렇게 진행한 이유는 문제에
'하나의 파닭에는 하나 이상의 파가 들어가면 안 된다.'
라고 적혀있었기 때문입니다.
http://boj.kr/f0fd87d4a5924d068ce2cbf1fa312d84
저 코드를 실패한 이후 다음과 같이 hi를 1e18로 바꿔서 진행했더니 정답이 되었습니다.
이 문제에서 왜 hi를 가장 짧은 파의 길이로 설정하면 안되는지가 궁금합니다.
Answer 2
0
안녕하세요 준님 ㅎㅎ
min으로 하게 되면 다음의 반례를 해결하지 못합니다.
2 5
100
1000
100
이 때는 200을 기반으로 파를 써야하는데 min으로 하게 되면 최대 100으로 밖에 못나누게 되고 -> 로직상 에러가 생깁니다.
감사합니다.
0
안녕하세요, 인프런 AI 인턴입니다.
jjune0427님, “파닭파닭” 문제를 풀면서 이분 탐색을 통한 최적화 문제를 맞닥뜨리셨네요. 문제에서 ‘하나의 파닭에는 하나 이상의 파가 들어가면 안 된다’는 제약은 해당 파를 잘게 자르는 과정에서도 각각의 잘린 파가 최소 하나의 파닭에는 포함되어야 한다는 의미예요. 고로, 모든 파를 완벽한 길이로 잘라서 나누는 최적 방법을 찾아야 하며, hi의 초기 설정이 이 문제의 중요 부분입니다.
변수 설정의 중요성
초기적으로 hi 값을 입려된 배열의 최소값으로 설정하셨습니다. 하지만 이는 문제 해결에 있어 한계가 있습니다. 이분 탐색의 목적은 주어진 길이에서 얼마나 많은 파를 얻을 수 있을지를 파악해 최상의 길이를 찾는 것입니다. 최소값으로 hi를 설정한 경우, 그 이상의 검증 (즉, 파를 더 짧게 자를 때의 가능성) 이 없는 셈이라 하네요.
최대값 설정 이유
따라서 현실적으로 문제에서 허용하는 최대 길이, 즉 1e18과 같은 큰 수치를 hi로 설정해 모든 가능성을 탐색합니다. 이렇게 해야 모든 길이에 대해 충분한 검색을 할 수 있고, 잘못된 잘라짐으로 인한 부족함을 방지할 수 있습니다.
관련하여 유사한 질문의 답변을 확인해 보실 수 있는 링크를 제공하겠습니다:
- 6-I 질문드립니다 - 비슷한 상황에서의 문제 해결 과정과 상세한 설명이 제공됩니다.
- 14627 파닭파닭 문제 질문 - 이분 탐색에서의 길이 설정에 대한 구체적인 설명이 있습니다.
저는 질문자님의 이해를 돕고자 지식공유자님의 기존 답변을 참고하여 유사한 답변 링크를 추천해드리고 있습니다.
현재 베타 기능으로 답변이 만족스럽지 않을 수 있는 점 양해 부탁드립니다. 🙏
추가적으로 궁금한 점이 있으시면, 이어서 질문해 주세요. 곧 지식공유자께서 답변해 주실 것입니다.