bwnabi   4년 전

DP(DFS)를 이용해서 풀었고, 반례를 찾아서 해봐도 잘 안되네요..

왜 안 되는지 궁금합니다.

추가로 필요한 정보 있으시면 댓글로 남겨주세요

djm03178   4년 전

혹시나 하는 생각인데요, 비용의 범위가 주어지지 않았기 때문에 그 비용이 0xffffff보다 큰 경우를 고려해야 할 수도 있습니다. 0xffffff면 1677만 7215인데, int형의 한계치는 아직 멀었죠. 이 안에서는 값이 다 나올 수 있다고 보셔야 할 것 같습니다. limits.h의 INT_MAX 같은 걸 사용하시는 게 안전합니다.

bwnabi   4년 전

좋은 답변 감사합니다.
하지만 아쉽게도 INT_MAX를 사용해도 마찬가지로 틀렸다고 나오네요.. ㅠ

djm03178   4년 전

그러면 반례를 찾아드릴게요.

4

1 2 3

1 2 3

1 2 3

1 2 3

정답은 6인데, 7을 출력하네요.

bwnabi   4년 전

여기서부터가 문제인건가요..
왜 정답이 6인지를 모르겠네요..

1 2 3 1 이 되어야 양옆에 색상이 중복이 안되지않나요?
1 2 1 2 라면 가운데 있는 숫자 2의 이웃이 1로 같은 색상이 되니까요. 1도 마찬가지구요

djm03178   4년 전

문제의 서술이 약간 애매모호하기는 한데, 그런 뜻이 아닙니다.
"또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다."
이걸 잘 해석하셔야 됩니다. '이웃'은 같은 색으로 칠할 수 없습니다.
"집 i의 이웃은 집 i-1과 집 i+1이다."
그렇다면 집 i-1과 집 i+1이 i의 이웃이기 때문에 같은 색으로 칠할 수 없는 걸까요? 그렇지 않습니다. 여기서 같은 색으로 칠할 수 없는 건 서로 '이웃'인 것들끼리 뿐입니다.
따라서 위 예시에서 1 2 1 2 같은 선택이 가능합니다.

bwnabi   4년 전

... 언어의 문제였군요?
덕분에 해결했습니다....;
코드가 더 쉬워졌어요..

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