후기

문제에 접근한 방식

처음에는 주어진 숙련도 level로 모든 퍼즐을 제한 시간 안에 해결할 수 있는지 계산하는 level_test() 함수를 만들었습니다.

현재 퍼즐의 난이도가 숙련도 이하라면 한 번에 해결할 수 있으므로 현재 퍼즐의 소요 시간만 더했습니다.

time_cur += times[i];

반대로 난이도가 숙련도보다 높다면 diffs[i] - level번 틀리게 됩니다. 한 번 틀릴 때마다 다음 시간이 필요합니다.

현재 퍼즐 풀이 시간 + 이전 퍼즐 풀이 시간

마지막에는 현재 퍼즐을 성공해서 끝내야 하므로 현재 퍼즐 풀이 시간을 한 번 더 더했습니다.

const failCount = diffs[i] - level;
const prevTime = i > 0 ? times[i - 1] : 0;

time_cur += failCount * (times[i] + prevTime);
time_cur += times[i];

이 부분을 하나의 식으로 보면 다음과 같습니다.

time_cur +=
    times[i] +
    failCount * (times[i] + prevTime);

이분 탐색을 사용할 수 있었던 이유

이 문제에서 숙련도가 높아질수록 문제를 틀리는 횟수가 줄어들고, 전체 소요 시간도 줄어듭니다.

예를 들어 숙련도별 결과가 다음과 같다고 생각할 수 있습니다.

숙련도:  1  2  3  4  5  6
통과:    X  X  X  O  O  O

한 번 통과하기 시작하면 그보다 높은 숙련도에서는 계속 통과합니다. 따라서 모든 숙련도를 하나씩 검사할 필요 없이 이분 탐색으로 최초의 O를 찾을 수 있습니다.

이 문제에서 찾는 것은 다음과 같습니다.

제한 시간 안에 퍼즐을 모두 해결할 수 있는 가장 낮은 숙련도