BOJ 10571 다이아몬드

이 문제는 smart elephant문제와 비슷한 문제(거의 똑같을지도..)이다.
다이아몬드의 중량과 선명도가 주어지면 중량이 늘어나고, 선명도가 줄어들게 다이아몬드를 나열했을 때 최대 길이를 구하는 문제이다.

풀이는 중량 기준으로 오름차순으로 정렬한 목록에서 선명도의 가장 긴 줄어드는 부분 수열의 길이를 구하면 된다. (반대로 선명도 기준으로 내림차순으로 정렬하고 중량의 LIS를 구해도 된다... LIS가 좀 더 익숙하니 이게 더 나을 수도...)

하나 주의할 점은 중량 기준으로 오름차순으로 정렬할 때, 만약 중량이 같다면 선명도가 내림차순 기준으로 정렬되도록 해줘야 할 것이고, 또한 smart elephant에서는 중량이 같고 선명도가 줄어드는 것도 허용이 안되기 때문에 가장 긴 줄어드는 부분 수열을 구할 때, 중량이 같지 않은 경우만 허용하는 조건을 넣어줬어야 했다.
하지만 이 문제는 그냥 다이아몬드의 가치가 높아지기만 하면 되는데, 중량이 같아도 선명도가 낮아지면 가치가 높아지는 것으로 볼 것 같으니 굳이 그런 조건은 안 넣어줘도 될 것 같다. (참고로 smart elephant에서는 중량, 선명도 대신, 코끼리의 무게와 지능이었음)

입력받는 부분에서 좀 애먹었는데, 예를 들어 1.5가 들어오면 이것을 정수로 변환한답시고 1*10+5*10을 해놓고 왜 15가 안나오지...하고 있었다... 1*10+5*1인데... 고쳤더니 예제는 잘 나온다. 근데 WA를 받았다...

흠... 아까 내가 처음에 고민했던 문제인 것 같다. 문제 원문을 보니
find the longest subsequence of diamonds for which the weight and clarity are both becoming strictly more favorable to a buyer. 라고 되어있다.
both becoming strictly!! -> 이 부분때문에 아마도 중량이 같을 때 선명도가 낮아지는 경우를 선택하면 안되는 것 같다. 결국 smart elephant랑 똑같다.

다시 고쳐서 제출해 봐야겠다.
계속 틀리다 먼저 푼 친구의 도움을 얻어 겨우 통과시켰다. 바로 이 문제는 smart elephant랑 다른 것이 입력으로 주어진 순서를 지켜야 한다. 그러니까 입력으로 주어진 것에서 골라내서 맞추는 게 아니라 입력으로 주어진 순서를 지키면서 무게가 증가하고, 선명도가 낮아지는 것 부분 수열을 찾아야 한다. 그래서 sort를 제거하고 제출해서 맞았다.

이 문제는... 계속 틀릴 때는 내가 문제를 제대로 이해한 것이 맞는지도 생각해봐야 한다는 교훈을 준 문제이다.