1029번 - 그림 교환
dp로 풀이하는 경우, 3가지 조건을 memo해야 합니다
: 같은 경로를 지나려고 해도, 여태까지 지나온 경로에 의해 결정된 최저 가격 값에 의해 원래 지날 수 있던 경로도 못 지날 수 있으므로 최저 가격이 다르면 다른 case입니다.
: 중복 소유가 불가능하기 때문에 자명하게 필요합니다. 비트마스킹을 이용합니다.
: 현재까지 소유했던 상인들 집합이 동일해도, 현재 소유중인 상인에 따라 경로가 달라지므로 필요합니다.
질문 게시판을 보니 1번을 고려하지 못하신 분들이 많은 것 같은데 저는 3번을 생각을 못했네요. 각각에 대해 반례 하나씩 남깁니다.
댓글을 작성하려면 로그인해야 합니다.
shyou1119 9달 전 1
dp로 풀이하는 경우, 3가지 조건을 memo해야 합니다
1. 최저 가격
: 같은 경로를 지나려고 해도, 여태까지 지나온 경로에 의해 결정된 최저 가격 값에 의해 원래 지날 수 있던 경로도 못 지날 수 있으므로 최저 가격이 다르면 다른 case입니다.
2. 현재까지 소유했던 상인들 집합
: 중복 소유가 불가능하기 때문에 자명하게 필요합니다. 비트마스킹을 이용합니다.
3. 현재 소유중인 상인
: 현재까지 소유했던 상인들 집합이 동일해도, 현재 소유중인 상인에 따라 경로가 달라지므로 필요합니다.
질문 게시판을 보니 1번을 고려하지 못하신 분들이 많은 것 같은데 저는 3번을 생각을 못했네요. 각각에 대해 반례 하나씩 남깁니다.