C++) BOJ 1149. RGB거리
문제 링크
제한
- 시간 제한 : 0.5 초 (추가 시간 없음)
- 메모리 제한 : 128 MB
문제
-
RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.
-
집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.
- 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
- N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
- i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.
입력
- 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.
출력
- 첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.
👀 풀이
- 처음엔 현재 집까지 칠했을 때 비용과 이번에 칠할 수 있는 색 중 더 가격이 싼 색을 더한 가격을 dp 배열에 합산해서 마지막 인덱스 중 최소값을 출력했는데 마지막 예제가 통과하지 못했다.
- 질문 게시판 보니까 현재 최소값이 최종적으로 최소값이 되지 않을 수 있는 경우 때문이었다. ㅠㅠ
- 근데 문제는 알아도 해결할 방법이 떠오르질 않아서 질문 게시판을 더 찾아봤는데 어떤 분이 주어지는 행렬에서 각 행에 숫자를 하나 골라서 인접하지 않은 수들과의 합 중 최소값을 구하는 것이라고 써 놓은 것을 보고 아이디어를 얻어서 수정하니까 통과되었다.
3
26 40 83
49 60 57
13 89 99
- 여기서 수직 방향으로는 합을 구하지 않고 대각선 방향(\/)에 있는 수들과 현재 행의 수의 합 중 최소를 구하는 것임
- 풀고 나니까 왜 실버1인지 알 거 같기도 했다… 쓸데없이 어렵게 생각해서 시간 날림 ㅠ
결과
- 시간 : 0 ms
- 메모리 : 2044 KB