notoonull   6년 전

RGB거리 문제의 설명이 다음과 같습니다.

(RGB거리에 사는 사람들은 집을 빨강, 초록, 파랑중에 하나로 칠하려고 한다. 또한, 그들은 모든 이웃은 같은 색으로 칠할 수 없다는 규칙도 정했다. 집 i의 이웃은 집 i-1과 집 i+1이다. 처음 집과 마지막 집은 이웃이 아니다.

각 집을 빨강으로 칠할 때 드는 비용, 초록으로 칠할 때 드는 비용, 파랑으로 드는 비용이 주어질 때, 모든 집을 칠할 때 드는 비용의 최솟값을 구하는 프로그램을 작성하시오.)

1) 각 비용의 최소값에 대한 설명이 없습니다. 비용에 0이 들어가는 테스트 케이스가 존재하나요?

2) 각 비용의 최대값에 대한 설명이 없습니다. 비용을 모두 더했을 때 2147483647를 넘는 테스트 케이스가 존재하나요?


입력에 대한 설명은 다음과 같습니다.

(첫째 줄에 집의 수 N이 주어진다. N은 1,000보다 작거나 같다. 둘째 줄부터 N개의 줄에 각 집을 빨강으로 칠할 때, 초록으로 칠할 때, 파랑으로 칠할 때 드는 비용이 주어진다.)

3) 설명에 N의 최소값이 명시되어 있지 않습니다. N에 0이 들어오는 테스트 케이스가 있나요?

djm03178   6년 전

명시되어야 있어야 한다고 생각하지만, 일단 테스트 케이스 상에 비용의 합이 32비트 int형을 넘어가는 경우는 없는 것으로 보이며, N이 0인 케이스도 없다고 보시면 될 것 같습니다.

djm03178   6년 전

비용이 0인 경우가 있는지는 문제 푸는 데에 아무 지장이 없으리라고 생각합니다. 심지어 음수가 있더라도 문제는 없을 듯합니다.

notoonull   6년 전

답변 감사합니다. 비용의 최소값은 memoization 변수 초기값이랑 헷갈렸네요. 다시 보니 상관이 없네요. 감사합니다.

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