1149번 - RGB거리
코드를 작성했는데 계속 틀렸다고 나와서 풀다가 결국 다른 사람이 작성한 코드를 봤습니다.
첨부된 코드는 순수히 제가 작성한 코드입니다.(틀렸습니다)
참고한 다른 몇 명의 코드를 보니 대부분 현재 집을 기준으로 이전 집이 어떠할 때를 판별하여 진행하더군요.
저는 현재 집을 기준으로 다음 집이 어떠할 때를 판별했는데 이 방식이 잘못된 방식인지,
그리고 현재 집에서 채택하여 final에 더한 수의 인덱스는 다음 집에서 사용할 수 없으므로 9999로 처리했는데 이것도 잘못된 방식인지 궁금합니다.
이외에 알고리즘 측면에서 잘못된 부분이 있다면 반례와 함께 설명해 주시면 감사하겠습니다.
이 코드에 문제점은 i번째 집을 칠하는 색을 매번 하나로 결정하면서 진행하고 있다는 점입니다.
인접한 두 집을 보고 다음 집의 색을 가장 싼 것으로 바로 결정해버리면, 이번 집에서 비록 손해를 보더라도 다음 집에서 더 이득을 볼 수 있는 경우가 있더라도 발견하지 못하게 됩니다.
반례로는 다음과 같은 것이 있습니다.
다수의 예외 상황이 있겠네요.
이해가 되었습니다. 감사합니다.
댓글을 작성하려면 로그인해야 합니다.
sibaek 2년 전
코드를 작성했는데 계속 틀렸다고 나와서 풀다가 결국 다른 사람이 작성한 코드를 봤습니다.
첨부된 코드는 순수히 제가 작성한 코드입니다.(틀렸습니다)
참고한 다른 몇 명의 코드를 보니 대부분 현재 집을 기준으로 이전 집이 어떠할 때를 판별하여 진행하더군요.
저는 현재 집을 기준으로 다음 집이 어떠할 때를 판별했는데 이 방식이 잘못된 방식인지,
그리고 현재 집에서 채택하여 final에 더한 수의 인덱스는 다음 집에서 사용할 수 없으므로 9999로 처리했는데 이것도 잘못된 방식인지 궁금합니다.
이외에 알고리즘 측면에서 잘못된 부분이 있다면 반례와 함께 설명해 주시면 감사하겠습니다.