[일반] 망했다

[p플랫(urd05)]

내 감각은 옳았고 내 본능은 틀린 것이었어.

1솔은 초심으로 돌아가라는 계시인 것인가. 

그래도 블루는 지켰네 어휴

[데자와민트초코닥터페퍼솔의눈(chlwnsgud7)]

B 무엇

[p플랫(urd05)]

난 억울하다 내 코드는 분명히 맞다!!!!

[익명(222.96)]

B번 다이나믹임

[p플랫(urd05)]

???ㄷㄷㄷ 이게 dp가 된다고요? 나 투포인터 비스무리한 걸로 짰는데...div2 말하는 거 맞죠?

[익명(222.96)]

ㅇㅇ mxpos(i)= 1~i까지의 수들이 가지고 있는 인덱스 중에서 가장 큰 인덱스 mnpos(i)= 1~i까지의 수들이 가지고 있는 인덱스 중에서 가장 작은 인덱스 이렇게 하고 mxpos(i)-mnpos(i)+1이 i이면 해당 구간엔 1~i만 포함이 되어있는 거임

[p플랫(urd05)]

그럼 제 풀이 검사 좀 해주세요. 부분수열의 l과 r을 들고다니면서 (그 부분수열의 최댓값)+1이 있는 위치까지 부분수열을 늘이는 걸 반복해서 최댓값으로 나온 적이 있는 숫자만 1을 출력했거든요?

[익명(222.96)]

그러면 최악의 경우에 N^2 아님?

[p플랫(urd05)]

투포인터 방식이라 O(N) 나옴. 한 번 갱신할 때마다 모든 원소를 세는 게 아니라 새로 생긴 숫자만 세서

[익명(222.96)]

n개의 수에 대해서 전부 투포인터를 쓴다는 거니까 O(TN^2)일걸? 내가 말한 다이나믹 방식은 O(TN)임

[p플랫(urd05)]

아무리 봐도 O(N) 뜰 수 밖에 없는 코드인데... 코드 올려볼게요.

[데자와민트초코닥터페퍼솔의눈(chlwnsgud7)]

반례) 2 6 1 5 7 4 3

[데자와민트초코닥터페퍼솔의눈(chlwnsgud7)]

마지막으로 제출한 코드 기준

[p플랫(urd05)]

잘못을 깨달았습니다... 2시간만 일찍 깨달았어야 하는데.

[데자와민트초코닥터페퍼솔의눈(chlwnsgud7)]

ㅠ

[데자와민트초코닥터페퍼솔의눈(chlwnsgud7)]

나도 투포인터인줄 알았는데