nuclear852   3년 전

문제 접근 방식은 y = a+bx 꼴의 수식을 생각하고 (i, arr[i])에 대해 좌표를 찍었습니다.

그럴 경우,

arr[0] <= a+b < arr[0] + 1

arr[1] <= a+2b < arr[1] + 1 ... 와 같은 수식이 나옵니다.

이런 수식들의 모든 쌍에 대해 쌍끼리 수식을 빼줍니다,

그럴 경우 

    arr[1] - arr[0] - 1  <   b  < arr[1] - arr[0] + 1와 같은 수식들을 얻을 수 있고 이를 일반화시키면

(arr[y] - arr[x] - 1) / (y-x) < b < (arr[y] - arr[x] + 1) / (y-x)와 같은 수식을 얻을 수 있습니다.

위 수식의 좌항을 L,  우항을 R이라 할 때, max(L)이 임의의 R값보다 클 경우 fail, min(R)이 임의의 L값보다 작을 경우 fail이라 생각하고 구현하였습니다.

이게 오차때문에 발생한 문제인지, 아니면 알고리즘 상에 추가로 확인할 것이 있는 건지 고민해봤지만 답이 나오질 않아 질문드립니다.

반례나 조언 주시면 감사드리겠습니다.

mym0404   2년 전

안됐다

nuclear852   2년 전

빠큐드세욘

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