kjk9704   11달 전

이 문제는 브루트 포스 없이 조합론 공식을 유도하여 문제를 해결할 수 있습니다.

우선 좋은 구간이 될 수 있는 샘플 데이터를 만들어 봅니다.

1 2
1 -> 1(0 * 2 + 1)
2 -> 1(1 * 1 + 0)

1 2 3
1 -> 2(0 * 3 + 2)
2 -> 3(1 * 2 + 1)
3 -> 2(2 * 1 + 0)

1 2 3 4
1 -> 3(0 * 4 + 3)
2 -> 5(1 * 3 + 2)
3 -> 5(2 * 2 + 1)
4 -> 3(3 * 1 + 0)

1 2 3 4 5
1 -> 4(0 * 5 + 4)
2 -> 7(1 * 4 + 3)
3 -> 8(2 * 3 + 2)
4 -> 7(3 * 2 + 1)
5 -> 4(4 * 1 + 0)

1 2 3 4 5 6
1 -> 5(0 * 6 + 5)
2 -> 9(1 * 5 + 4)
3 -> 11(2 * 4 + 3)
4 -> 11(3 * 3 + 2)
5 -> 9(4 * 2 + 1)
6 -> 5(5 * 1 + 0)

1 2 3 4 5 6 7
1 -> 6(0 * 7 + 6)
2 -> 11(1 * 6 + 5)
3 -> 14(2 * 5 + 4)
4 -> 15(3 * 4 + 3)
5 -> 14(4 * 3 + 2)
6 -> 11(5 * 2 + 1)
7 -> 6(6 * 1 + 0)

좋은 구간이 예시로 최대 범위가 [1, 7]이고 target이 1인 경우 0 * 7 + 1, target이 2인 경우 1 * 6 + 2, ...으로 나올 수 있습니다.

이것을 변형하여 좋은 구간의 최대 범위가 [lo, hi]이고 목표값을 T라고 가정한다면 공식을 다음과 같이 유도됩니다.

answer = (T - lo) * (hi - T + 1) + (hi - T)

이렇게 일반화를 할 수 있습니다.

단, 조심해야 할 예외 사항가 2가지 있습니다.

예시로 L = [1, 4, 6, 9, 10], target = 4처럼 target이 L 안에 포함된 원소인 경우 무조건 좋은 구간은 없으므로 answer = 0이 됩니다.

또한 L = [1, 4, 6, 9, 10], target = 5인 경우 좋은 구간이 될 수 있는 최대 범위가 [5, 5]가 되며 이 때 좋은 구간이 성립될려면 lo < hi가 되어야 하나 lo >= hi이므로 좋은 구간 조건이 성립하지 않습니다. 따라서 이 경우도 answer = 0으로 합니다.

그리고 target < L[0]도 가능하면서 동시에 target은 자연수이므로 A = [0] + L로 해서 target < L[0]인 경우도 좋은 구간을 구할 수 있도록 배열을 재정의합니다.

마지막으로 이 배열을 제대로 활용할려면 정렬은 필수이고 [lo, hi]를 구하기 위해 이진 탐색을 하면 구할 수 있습니다.

이렇게 하면 브루트 포스로 하는 경우 O(N^2) 걸리는 문제가 O(log N)으로 해결할 수 있어 S의 원소가 최대 10^18인 경우도 빠르게 해결할 수 있습니다.

(여기서 최악의 경우는 L = [1, 10^18], target = 5 * 10^17인 경우 브루트 포스로 하면 매우 많은 연산이 필요하나 O(log N)의 이진 탐색으로 lo = 2, hi = 10^18 - 1이라는 것을 알게 되고 여기에 공식을 대입해서 O(1)으로 바로 답을 구할 수 있게 됩니다.)

icecreamer   11달 전

작성된 코드는 정렬이 들어가기 때문에 O(NlogN)입니다만, x이하의 가장 큰 수, x이상의 가장 작은 수를 찾는 것은 O(N)에도 가능합니다. (min, max를 구할 때 굳이 정렬하지 않아도 되는 것과 동일합니다.)

인풋을 x, 인접 작은 수를 A, 인접 큰 수를 B라고 하면. 구간의 시작점은 A+1, A+2...x로 총 x-A개가 가능하며, 구간의 끝점은 x,x+1...B-1로 총 B-A개가 가능합니다.

이 중에서 시작점과 끝점이 동일한 경우인 한 가지 경우의 수를 제외해주면 예외처리도 없이 풀이가 가능하겠네요

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