codeup1 코드업 4040 자바 - 펜션 (CodeUp 4040 java) 문제 : CodeUp4040 어차피 중간에 하루라도 지낼 수 없다면 조건이 만족되지 않는다. 따라서 s부터 시작해서 매번 가장 길게 지낼 수 있는 방에서 지내면 된다. 그러다가 지낼 수 없는 날이 되면 -1, t 이상이 됬다면 변경 횟수를 출력하면 된다. 증명은 간단한데, 매번 가장 길게 지낼 수 있는 방이 아닌 다른 곳에 묵었을 때 더 이득이 되는 경우가 있다면 위의 추론이 틀린 것이다. 하지만 더 짧은 기간 지낼 수 있는 방을 고르더라도 동일한 변경횟수까진 나와서 더 낮은 변경 횟수가 될 수 없음은 직관적으로 알 수 있다. 따라서 그리디하게 선택하면 된다. 그럼 해당하는 날에 어느 방이 가장 길게 묶을 수 있는 방인지 어떻게 알 수 있을까? 이건 날을 거꾸로 진행하면서 몇 일을 지낼 수 있는지 pre.. 2022. 4. 18. 이전 1 다음
