13549번 - 숨바꼭질 3
주석에 나온 것처럼 리스트의 길이를 100001로 하면 실패하는데, 200001로 하면 정답이 나옵니다. 그런데 조건문 안에서는 모두 0 이상 100000 이하의 수만 탐색하도록 하였는데, 왜 100001보다 큰 list가 필요한지 궁금합니다.
예를 들어 66,666에서 100,000을 탐색하려고 하면 66,666에서 1씩 커지며 100,000까지 도달하는 시간(33,334초)보다는 133,332로 순간이동 후 1씩 줄어들어 100,000까지 도달하는 시간(33,332초)가 더 적을 수 있습니다. 그래서 100,000보다 더 큰 크기의 그래프가 필요합니다.
100000 이상의 점도 갈 수 있는 문제였군요 감사합니다!
범위의 문제가 아닙니다. 100000을 넘어서 가는 것이 정답인 경우는 없습니다.
2배 하여 100000을 넘어갔다 오는 길이 있다면, 그 전에 감소를 먼저 시킨 뒤에 2배를 하는 것이 반드시 더 이득이기 때문에 범위를 10만으로 제한하더라도 항상 답을 구할 수 있어야 합니다.
이 코드의 문제점은 19번째 줄에 target이 아니라 target * 2를 넣어야 한다는 점입니다. 이 부분만 고치면 10만으로 제한을 잡아도 맞습니다.
상당히 어처구니없는 실수가 있었네요 피드백 감사합니다!!
댓글을 작성하려면 로그인해야 합니다.
aiden2978 2년 전 1
주석에 나온 것처럼 리스트의 길이를 100001로 하면 실패하는데, 200001로 하면 정답이 나옵니다. 그런데 조건문 안에서는 모두 0 이상 100000 이하의 수만 탐색하도록 하였는데, 왜 100001보다 큰 list가 필요한지 궁금합니다.