15397번 - Looping Playlist
다음의 데이터를 추가해 주세요. 제출번호 101682631이 틀려야 합니다.
101682631은 선형 그리디를 한 뒤 마지막 구간의 시작점에서 선형 그리디를 한 번 더 시도하여 두 결과 중 최솟값을 출력합니다.
아래 데이터를 수열로 나타내면 1 9 3 2 9 8 8 7이고, 여기서 그리디를 두 번 돌리면 다음과 같이 됩니다.
1 9 3 (9 11 1 3 ...) / 2 9 8 8 (2 4 6 8 9 ...) / 7
7 + 1 9 (7 9 11 1 ...) / 3 2 9 (2 3 5 7 9 ...) / 8 8
이제 7 9 11 1 ...의 음계는 8을 포함하지 않으므로 코드가 3을 출력하게 되는데, 여기서 최적은 9 3 2 9 / 8 8 7 1로 나누어서 2를 출력해야 합니다.
이 정도는 되어야 습격자초라기 그리디 풀이를 발견하는거구나
FAN입니다 (새해 복 많이 받으세요)
@aunps 그건 제가 발견한거 아닙니다 (pyb1031님이 원조)
그리고 저 반례는 그냥 스트레스 짜니까 금방 나왔어요 별거아님
댓글을 작성하려면 로그인해야 합니다.
bubbler 10달 전 1
다음의 데이터를 추가해 주세요. 제출번호 101682631이 틀려야 합니다.
101682631은 선형 그리디를 한 뒤 마지막 구간의 시작점에서 선형 그리디를 한 번 더 시도하여 두 결과 중 최솟값을 출력합니다.
아래 데이터를 수열로 나타내면 1 9 3 2 9 8 8 7이고, 여기서 그리디를 두 번 돌리면 다음과 같이 됩니다.
1 9 3 (9 11 1 3 ...) / 2 9 8 8 (2 4 6 8 9 ...) / 7
7 + 1 9 (7 9 11 1 ...) / 3 2 9 (2 3 5 7 9 ...) / 8 8
이제 7 9 11 1 ...의 음계는 8을 포함하지 않으므로 코드가 3을 출력하게 되는데, 여기서 최적은 9 3 2 9 / 8 8 7 1로 나누어서 2를 출력해야 합니다.