gmroh06   2년 전

일단 반례는 찾았습니다.

20
322 831 212 232 545 698 260 265 324 215 701 75 156 605 851 993 425 887 691 593

답은 8인데 7이라고 출력합니다. 

아무리 생각해봐도 도저히 모르겠어서 질문해봅니다.

wizardrabbit   2년 전

안녕하세요!

좀 더 간결하면서 틀린 원인을 쉽게 파악할 수 있는 반례입니다:

preview
입력:
7
4 5 6 7 1 2 3
정답:
4
출력:
3

해당 문제의 점화식에 의하면 n번째 원소에서 구한 값은 n번째 원소가 증가하는 수열의 마지막 원소가 될 때의 최댓값이겠죠? 만약 n번째 원소 이전에 자신보다 작은 값이 없는 경우 수열을 이을 수 없게 되므로, 자기 자신 혼자를 수열로 하는 증가하는 수열이 생기니 값은 1이 되는 것이고요.

여기서 주의해야 할 점은 가장 긴 증가하는 수열이 항상 수열의 마지막 원소와 이어져 있다고 장담할 수는 없다는 것입니다. 첨부된 반례를 보면 아시겠지만, 가장 긴 증가하는 수열은 인덱스 0번~3번 까지의 원소를 이은 것입니다. 그렇기 때문에 정답은 인덱스 3을 마지막으로 하는 수열이 되어, m[3]이 정답인 것입니다. 올려주신 코드는 항상 배열 m의 마지막 값을 정답으로 채택하고 있어요. 이는 수열의 마지막 원소를 잇는 증가하는 수열 중에서만 최댓값을 구하게 되는 것이죠.

수열의 마지막 원소뿐만 아니라 다른 원소가 증가하는 수열의 마지막 원소일 경우도 모두 체크해 보세요. 도움이 되었기를 바랍니다!

gmroh06   2년 전

오오..감사합니다^^

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