chowder0018   3년 전

Memoization 기법은 과거에 계산한 값을 불필요하게 여러 번 계산하는 일이 없도록 이를 저장해 두고 필요할 때 재활용하도록 하는 방식을 의미합니다. 따라서, 이 기법은 side effect가 없는 순수 함수에만 사용될 수 있습니다. 다시 말해, 값에 영향을 주는 인자의 조합마다 함숫값을 따로 저장해야 합니다.

이 문제에서 함숫값에 영향을 주는 것은 (1) 현재 그림 소유자, (2) 직전 거래의 가격, (3) 이미 그림을 소유한 사람들입니다.
(1)은 다음 거래의 가격을 결정하기 위해 필요합니다.
(2)는 다음 거래의 가격이 직전 거래의 가격보다 같거나 높은지 비교하기 위해 필요합니다.
(3)은 이미 거래에 참여한 사람을 걸러내기 위해 필요합니다.
따라서 dp 배열은 3차원이 되어야 할 것입니다.



핵심은 함숫값을 유일하게 결정하기에 (1)과 (3)만으로 충분하지 않다는 것입니다.
현재 소유자(1)가 같고 여태까지 그림을 소유한 사람들(3)이 같다고 해서 반드시 최종 거래 가격(2)가 같다는 보장이 없습니다.

이 부분에 오류가 있는 코드를 걸러내기 위한 테스트케이스를 아래에 첨부하였습니다.
테스트케이스를 통해 설명하겠습니다.

1 -> 2 -> 3 -> 4의 경우 최종 거래 가격이 6입니다.
따라서 1 -> 2 -> 3 -> 4 -> 5는 불가능하고 이는 {1, 2, 3} -> 4에 대한 그림 소유자 수의 최댓값을 4로 단정할 것입니다.
하지만, 1 -> 3 -> 2 -> 4의 경우 최종 거래 가격이 4입니다.
따라서 1 -> 3 -> 2 -> 4 -> 5와 같이 그림 소유자의 수가 5인 경우가 존재합니다.
즉, 이것은 (2)에 대한 고려 없이 함숫값을 과소평가한 결과입니다.



2차원 dp로 WA를 받은 코드 중 상당수는 해당 테스트케이스를 통과하지 못함을 확인했습니다.
이 글을 보시는 분들께도 도움이 되면 좋을 것 같습니다.

chowder0018   3년 전

물론 위의 풀이와 다른 방법을 쓰신 분들과는 상관이 없습니다. 

jun83   2년 전

감사합니다

hobag6078   1년 전

dp[(1)현재 그림 소유자][(3) 이미 그림을 소유한 사람들] = "해당 상태로 도달했을 때 그림가격의 최솟값" 으로 설정한다면 2차원 배열로도 해결 가능한 것 같아서 남겨봅니다.

아래는 링크는 제가 해결한 코드 입니다.

https://blog.naver.com/k4nei/2...

leomessi   1년 전

2차원 DP 테이블을 다음과 같이 정의하였을 때 말씀주신 테스트 케이스는 통과하지만 틀렸습니다.

`DP[i][j] = i번 아티스트가 j의 가격으로 그림을 매입하였을 때 이후에 그림을 소유할 수 있는 아티스트의 최대 인원 수` (본인 포함)

다만 i번 아티스트가 j의 가격으로 그림을 매입하는 경우가 여러가지 경우가 있을 수 있기 때문에 올바른 값이 나오지 않았습니다.


아래의 테스트 케이스가 위 DP테이블에 대한 반례입니다.

2번 예술가가 6원으로 그림을 매입하였을 때, 그림이 1->2의 경로로 도달했는지, 1->3->4->5->2 의 경로로 도달했는지 위 테이블로는 확인할 수 없었기 때문입니다.

말씀해주신 덕분에 3차원으로 고쳐서 해결하였습니다. 감사합니다.

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