rla7538   3년 전

제가 생각하는 테스트 예제를 돌려봣을때도 맞게 나오는데

어디가 틀렸는지 모르겠습니다... ㅠㅠ

artage7   2년 전

dp로 푸셨으면 점화식이든 뭐든 적어주시지... 전 자바 몰라서 보기 힘드네요.

해결하셨는지는 모르겠으나

가장 긴 부분 수열 시리즈를 푸셨다면...


1 5 2 1 4 3 4 5 2 1 가 있을 때  ( 굵은 숫자가 정답의 기준이 되는 수 )


10번 인덱스 부터 1번 인덱스 까지 감소하는 가장 긴 수열을 dp로 구합니다.

그러면 10번 -> 1번 방향으로 가장 긴 감소 수열이 구해지니깐

 예제 정답의 기준인 8번 인덱스 부터 1번 인덱스 까지의 가장 긴 감소하는 수열의 길이(dp[8][0])이 구해질 것이고.


똑같은 방법으로

1번 인덱스 부터 10번 인덱스 까지 감소하는 가장 긴 수열을 dp로 구합니다.

그러면 1번 -> 10번 방향으로 가장 긴 감소 수열이 구해지니깐

에제 정답의 기준인 8번 인덱스 부터 10번 인덱스 까지의 가장 긴 감소하는 수열의 길이(dp[8][1])을 구할 수 있습니다.

두개를 더하고 8번 위치는 두번 더해지니깐 -1 하면 답.


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