[일반] c 어케푸나요

[졷급식(gubshig)]

진짜 모르겠음..

중간에 lis인가? 싶었는데 아닌거같고

[익명(125.131)]

lis 마즘

[졷급식(gubshig)]

그냥 n - lis 에요?

[익명(125.131)]

n/2, n/2+1이 어디있는지 찾고 각각 x y라고 하면 x왼쪽 어딘가에 a[x]-1이 있는가? y오른쪽 어딘가에 a[y]+1이 있는가? 둘다 만족하면 그 위치로 전이시키고 이걸 계속 반복 그럼 최선의 방법은 찾은 위치들 빼고 한번씩 연산 수행해주는거

[dd(61.83)]

나는 이분탐색 했음

[dd(61.83)]

어딘가 틀렸을 수도 있는데, 1. (1,n)은 앞에서 한 번이라도 주어진 연산을 수행했으면 반드시 마지막에 쌍으로 해줘야함 2. (2, n-1)도 마찬가지.. 3. [1, k] , [n - k +1, n]만을 연산한다고 치면 [k + 1, n - k]은 순서대로 놓여있어야 됌 ex) n = 8, k = 2 => 1,2,7,8,3,4,5,6이면 됨 k개의 연산만 사용해서 가능한지 <=> 처음/마지막 k개를 빼고 원래 순서인지 찾기

[익명(1.233)]

나도 이렇게 함

[개발뉴비(coderhs)]

난 O(N).. n=7인 경우로 설명을 하면 초기값을 7//2 = 3으로 두고 4의 위치를 기록 -> (3,5)의 위치를 기록하고 이 구간이 4의 위치를 포함하고 있는가 검사함 -> (2,6)의 위치를 기록하고 이 구간이 (3,5)를 포함하고 있는가 검사함 이런 식으로 검사 통과할 때마다 초기값을 1씩 깎고 결과가 답.