2532번 - 먹이사슬
저번엔 스택으로 답이 안나오길레
이리저리 생각해보다가 '최장 감소 수열'을 생각해봤습니다
끝나는 부분을 오름차순으로 정렬하고 시작 부분에서 최장 감소 수열 찾기로 하고
'최장 증가 수열'로 만들기 위해 시작부분을 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,998 5 <
1,000,000,000 5 <
999,999,997 10
1,000,000,000 10 <
yukariko님이 주신 케이스와 같은 경우도 이제 잘 나오는거 같은데
또 다른 경우가 있을까요?
저도 LIS 를 이용해서 구현해줬는데 자꾸 틀림이 뜨더라구요..
이 알고리즘을 쓰는게 맞는지 저도 궁금하네요
dovelet.com 에서 채점해보세요. 반례데이터를 볼수 있으니 ^_^
반례데이터의 n이 500,000이네요;
답과 차이는 2나는데 뭐가 잘못됬는지 감이 안잡혀요 ㅠㅠ
덕분에 AC 받았어요ㅎㅎ
제가 lower bound 함수를 잘못 이해하고 있었네요;
감사합니다 추석에 복 많이 받을실꺼에요!
댓글을 작성하려면 로그인해야 합니다.
mrcamel 6년 전
저번엔 스택으로 답이 안나오길레
이리저리 생각해보다가 '최장 감소 수열'을 생각해봤습니다
끝나는 부분을 오름차순으로 정렬하고 시작 부분에서 최장 감소 수열 찾기로 하고
'최장 증가 수열'로 만들기 위해 시작부분을 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님이 주신 케이스와 같은 경우도 이제 잘 나오는거 같은데
또 다른 경우가 있을까요?