글 읽기 - 이 문제 힌트좀 부탁드립니다.

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

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

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

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

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

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

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

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

@baekjoon 해결 감사합니다. :)

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

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

Baekjoon Online Judge