k번째 답을 출력하는 문제들의 경우, 일단 각 답들을 만들 수 있는 경우의 수를 세어 보는 게 좋아요.
LIS 문제를 풀었다면 다음과 같은 점화식을 아실 텐데요,
C[i] = i번째 숫자에서 시작하는 LIS 의 최대 길이
이거랑 비슷한
D[i] = i번째 숫자에서 시작하는 LIS 의 개수
를 생각해 보시면 좋을 거예요. 예를 들어 A = { 5, 8, 7, 10, 12 } 라고 하면, D = { 2, 1, 1, 1, 1 } 가 되겠죠? 이거가 힌트가 될꺼에요~
hyida
대충 어떤식으로 접근해야될까요;;
아무리 봐도 감이 안잡히네요. 중복하는 숫자가 없다는 점을 이용해야되나요?
도와주세요..ㅠㅜ
15년 전