16144번 - 드로잉
문제 접근 방식은 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이라 생각하고 구현하였습니다.
이게 오차때문에 발생한 문제인지, 아니면 알고리즘 상에 추가로 확인할 것이 있는 건지 고민해봤지만 답이 나오질 않아 질문드립니다.
반례나 조언 주시면 감사드리겠습니다.
안됐다
빠큐드세욘
댓글을 작성하려면 로그인해야 합니다.
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이라 생각하고 구현하였습니다.
이게 오차때문에 발생한 문제인지, 아니면 알고리즘 상에 추가로 확인할 것이 있는 건지 고민해봤지만 답이 나오질 않아 질문드립니다.
반례나 조언 주시면 감사드리겠습니다.