jnk98   1년 전

일단 제 풀이 방법을 간단히 설명 드리자면,

1. 길이 2L 이상인 해는 절대 존재하지 않는다.

왜냐하면, 길이 2L 인 해가 존재한다고 가정할 경우, 비둘기집이 원리(?) 에 의해 길이가 L이면서 평균이 더 크거나 같은 해가 항상 존재하기 떄문이다.

( 문제에서는 같은 평균일 경우 짧은 길이를 요구한다.)

2. 1.번에 의해 N번 루프를 돌리면서 L~2L-1 까지 전부 검사를 하면 좋지만, 10^8 루프이므로 시간 초과를 받을 것이 뻔하다.

그래서 제가 생각한 것이

1. 길이 L 인 평균값을 스캔해서 Max 가 나오는 지점을 전부 저장해 둔다. (여러개일 수 있으므로)

2. 1.번에서 구한 지점에서 좌우로(사실 우측만 해도 될 것 같기는 함) 영역을 2L 까지 늘리면서 2차 스캔을 한다.

입니다.

제가, 만든 테스트 케이스는 다 통과 되는데 , "틀렸습니다" 가 나오네요..ㅠ.ㅠ

질문 : 알고리즘이 잘못된걸까요? 아니면 생각 못한 특이 케이스가 있는걸까요?

august14   1년 전

저 방법으로 길이가 같을 때는 시작 지점을 최대한 앞으로 해야한다는 조건이 만족되지 않을 것 같네요.

그리고 길이가 L인데 1의 개수가 최대인 구간의 개수가 매우 많을 수도 있지 않을까요?

jnk98   1년 전

저 방법으로 길이가 같을 때는 시작 지점을 최대한 앞으로 해야한다는 조건이 만족되지 않을 것 같네요.

=> Max 값을 이전 Max 값보다 커지는 경우에만 Update 하도록 함으로써 해결했다고 생각합니다.

그리고 길이가 L인데 1의 개수가 최대인 구간의 개수가 매우 많을 수도 있지 않을까요?

=> 그래서 배열에 저장해 놓고 각각의 케이스에 대해서 2차 스캐닝을 돌리도록 했습니다.

august14   1년 전

Max 값을 이전 Max 값보다 커지는 경우에만 Update 하도록 함으로써 해결했다고 생각합니다.

=> 그렇네요 제가 잘못 봤습니다. 문제는 그게 아니고 더 짧은 길이인 부분을 찾을 수 없다는 점이네요

그래서 배열에 저장해 놓고 각각의 케이스에 대해서 2차 스캐닝을 돌리도록 했습니다.

=> 그러면 N*L로 도는거랑 어떤 점이 다른 것인가요?

jnk98   1년 전

Max 값을 이전 Max 값보다 커지는 경우에만 Update 하도록 함으로써 해결했다고 생각합니다.

=> 그렇네요 제가 잘못 봤습니다. 문제는 그게 아니고 더 짧은 길이인 부분을 찾을 수 없다는 점이네요

=> L 이 최소 길이 이므로 더 짧은 경우는 생각할 필요가 없을 듯..



그래서 배열에 저장해 놓고 각각의 케이스에 대해서 2차 스캐닝을 돌리도록 했습니다.

=> 그러면 N*L로 도는거랑 어떤 점이 다른 것인가요?

=> 좋은 지적이십니다. 최악의 경우 N*L로 도는 알고리즘과 같아집니다.

그러나, 모든 수가 '1' 인 경우를 제외하고는 최악의 경우는 없다고 봤습니다. (제 생각일 뿐이지만 ^^)

그리고, 모든 수가 '1'이면 2차 스캔을 할 필요가 없습니다.

august14   1년 전

1

25 5

1100001100000000000110001


그리고 최악의 경우는 좀더 생각해보세요.. max_index가 N-L에 가깝게 나오는 경우가 있습니다.

jnk98   1년 전

25 5

1100001100000000000110001

위의 경우 소스코드에 넣어서 돌리면

1 8

이 나옵니다. 맞는거 아닌가요? (4/8 가 최대 값이 맞는거 같은데요..ㅠㅠ)


max_index가 N-L에 가깝게 나오는 경우에 대해서는 좀 더 생각해 보겠습니다. ^^

august14   1년 전

20 25입니다.

jnk98   1년 전

아~ 그렇네요.. 감사합니다.

틀린 원인이 뭔지 알겠네요..ㅋ

jnk98   1년 전

@august14 님이 제시하신 반례를 보고, 2차 스캔에서 length가 더 짧아지는 경우에 대해 고려해서 반례에 대해서는 해결을 했는데 그래도 "틀렸습니다" 가 나오네요.. 고려하지 못한 부분이 더 있는 듯..ㅠ.ㅠ

댓글을 작성하려면 로그인해야 합니다.