mrcamel   2년 전

저번엔 스택으로 답이 안나오길레

이리저리 생각해보다가 '최장 감소 수열'을 생각해봤습니다

끝나는 부분을 오름차순으로 정렬하고 시작 부분에서 최장 감소 수열 찾기로 하고

'최장 증가 수열'로 만들기 위해 시작부분을 1e9(최대값) - 시작부분 으로 바꾸었습니다 

예제의 경우

7 3 4

1 2 4

3 1 5

4 7 8

5 5 7

6 9 10

2 6 10

999,999,997 4  <

999,999,998 4  <

999,999,999 5 <

999,999,993 8

999,999,995 7

999,999,994 10

999,999,991 10

저번에 yukariko님이 주신 케이스

4 3 4 

5 2 5

2 0 5

3 3 10

1 0 10

999,999,997 4 <

999,999,998 5 <

1,000,000,000 5 <

999,999,997 10

1,000,000,000 10 <

yukariko님이 주신 케이스와 같은 경우도 이제 잘 나오는거 같은데

또 다른 경우가 있을까요?

yukariko   2년 전

저도 LIS 를 이용해서 구현해줬는데 자꾸 틀림이 뜨더라구요..

이 알고리즘을 쓰는게 맞는지 저도 궁금하네요

pl0892029   2년 전

dovelet.com 에서 채점해보세요. 반례데이터를 볼수 있으니 ^_^

mrcamel   2년 전

반례데이터의 n이 500,000이네요;

답과 차이는 2나는데 뭐가 잘못됬는지 감이 안잡혀요 ㅠㅠ

mrcamel   2년 전

덕분에 AC 받았어요ㅎㅎ

제가 lower bound 함수를 잘못 이해하고 있었네요;

감사합니다 추석에 복 많이 받을실꺼에요!

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