dlwkdgjs   7년 전

아무리 노력해도 안돼네요....살려주세요.

artage7   6년 전

( 복붙 주의..ㅋ)

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 하면 답.

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