sibaek   2년 전

코드를 작성했는데 계속 틀렸다고 나와서 풀다가 결국 다른 사람이 작성한 코드를 봤습니다.

첨부된 코드는 순수히 제가 작성한 코드입니다.(틀렸습니다)

참고한 다른 몇 명의 코드를 보니 대부분 현재 집을 기준으로 이전 집이 어떠할 때를 판별하여 진행하더군요.

저는 현재 집을 기준으로 다음 집이 어떠할 때를 판별했는데 이 방식이 잘못된 방식인지,

그리고 현재 집에서 채택하여 final에 더한 수의 인덱스는 다음 집에서 사용할 수 없으므로 9999로 처리했는데 이것도 잘못된 방식인지 궁금합니다.

이외에 알고리즘 측면에서 잘못된 부분이 있다면 반례와 함께 설명해 주시면 감사하겠습니다.

djm03178   2년 전

이 코드에 문제점은 i번째 집을 칠하는 색을 매번 하나로 결정하면서 진행하고 있다는 점입니다.

인접한 두 집을 보고 다음 집의 색을 가장 싼 것으로 바로 결정해버리면, 이번 집에서 비록 손해를 보더라도 다음 집에서 더 이득을 볼 수 있는 경우가 있더라도 발견하지 못하게 됩니다.

djm03178   2년 전

반례로는 다음과 같은 것이 있습니다.

sibaek   2년 전

다수의 예외 상황이 있겠네요.

이해가 되었습니다. 감사합니다.

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