pl0892029   2년 전

"A를 선택하면 B, C, D, E 들을 선택할 수 없다."

와 같은 명제들을 얻어냈고, 이러한 경우가 매우 많기 때문에 백트... 보다는 매칭 스타일로 생각해서 접근을 시작했습니다.

그런데 시작점과 도착점의 연결을 어떻게 해야될지 막막합니다. (BFS로 짠다면)

DFS로 짜면 이런 문제가 쉽게 해결되나요?

joonas   2년 전

<RGB거리> https://www.acmicpc.net/problem/1149 혹은 <스티커> https://www.acmicpc.net/problem/9465 와 같이 전형적인 DP를 응용한 것 같아보이네요.

아니면.. 죄송합니다.. 하하

pl0892029   2년 전

joonas

DP라니 ㅎㅎ 발상도 재밌고 좋네요. 감사합니다 많이 생각해볼게요

baekjoon   2년 전

dp로도 풀 수 임ㅅ고, 매칭으로도 풀 수 있어요

pl0892029   2년 전

baekjoon 해결 감사합니다. :)

매칭은 Source와 Sink를 못찾았으므로...DP로 해결했습니다. ㅠㅠ

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