1149번 - RGB거리
안녕하세요.
일단 i번째 집의 색칠하는 비용 중 최솟값이 드는 색을 찾았는데 i-1번째 집의 색과 겹친다면
(I번째 최솟값)이랑 (i-1번째 두번째로 작은값) /( i번째 집의 2번째 작은값)과 (i-1번째 집의 첫번째 작은값)을 비교해 최솟값을 다시 정하는 알고리즘으로 짰습니다.
초보라서 dp이런거 신경안쓰고 막 짜봤는데 게시판에 있는 반례들 다 돌려봤는데 맞게 나옵니다. 근데 제출하면 틀렸습니다가 뜨네요. 어디가 틀린걸까요? 조언해주세요 !
다음의 반례들을 보고 어디가 잘못됐을지 잘 생각해보세요.
와 정말 감사합니다 ㅠㅠ.. 왜 틀린지 모르겠어서 답답했는데 이제 속이 시원하네요
앞집과 비교했을때 비용이 같을 때를 간과했네요
괜히 이 문제가 dp문제가 아니었군요 한수 배워갑니다 감사합니다!
댓글을 작성하려면 로그인해야 합니다.
haeran97 5년 전
안녕하세요.
일단 i번째 집의 색칠하는 비용 중 최솟값이 드는 색을 찾았는데 i-1번째 집의 색과 겹친다면
(I번째 최솟값)이랑 (i-1번째 두번째로 작은값) /( i번째 집의 2번째 작은값)과 (i-1번째 집의 첫번째 작은값)을 비교해 최솟값을 다시 정하는 알고리즘으로 짰습니다.
초보라서 dp이런거 신경안쓰고 막 짜봤는데 게시판에 있는 반례들 다 돌려봤는데 맞게 나옵니다. 근데 제출하면 틀렸습니다가 뜨네요. 어디가 틀린걸까요? 조언해주세요 !