백준 - 1149 RGB거리 [DP]

 

1149번: RGB거리

 

1. 문제 요약

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

빨강, 초록, 파랑으로 집을 칠할 때, 연속되지 않게 칠할 수 있으며, 최소 비용을 구하라.

 

2. 접근 방법

먼저 가장 완벽한 알고리즘인 완전탐색으로 구현해 보았습니다.

N = int(input())
rgb = [list(map(int, input().split())) for _ in range(N)]

answer = 1e9

def solution(idx:int, cost:int, color:int):
    global answer
    if idx == N:
        answer = min(answer, cost)
        return

    for i in range(3):
        if i == color:
            continue
        solution(idx+1, cost+rgb[idx][i], i)

solution(0,0,0)
solution(0,0,1)
solution(0,0,2)
print(answer)

재귀함수를 이용하여 모든 경우의 수를 탐색해 줍니다.

물론 예상대로 시간초과가 발생합니다 ㅎㅎ...

 

다이나믹 프로그래밍 방법으로 최적화를 진행하겠습니다.

• 입력받은 rgb 테이블을 순회합니다.
• 이전 인덱스의 현재 색상이 아닌 다른 색상(빨강이면, 초록과 파랑)의 비용 중 작은 값을 현재 값에 더 해줍니다.
• 마지막 인덱스의 최소 비용을 출력합니다.

 

3. 파이썬

N = int(input())
rgb = [list(map(int, input().split())) for _ in range(N)]

for idx in range(1, N):
    # RED 0
    rgb[idx][0] += min(rgb[idx-1][1], rgb[idx-1][2])
    # GREEN 1
    rgb[idx][1] += min(rgb[idx-1][0], rgb[idx-1][2])
    # BLUE 2
    rgb[idx][2] += min(rgb[idx-1][0], rgb[idx-1][1])

print(min(rgb[N-1]))

 

4. 자바

int N = Integer.parseInt(br.readLine());
int[][] rgb = new int[N][3];
for (int i = 0; i < N; i++) {
    StringTokenizer st = new StringTokenizer(br.readLine());
    rgb[i][0] = Integer.parseInt(st.nextToken());
    rgb[i][1] = Integer.parseInt(st.nextToken());
    rgb[i][2] = Integer.parseInt(st.nextToken());
}

for (int i = 1; i < N; i++) {
    // RED 0
    rgb[i][0] += min(rgb[i - 1][1], rgb[i - 1][2]);
    // GREEN 1
    rgb[i][1] += min(rgb[i - 1][0], rgb[i - 1][2]);
    // BLUE 2
    rgb[i][2] += min(rgb[i - 1][0], rgb[i - 1][1]);
}

System.out.println(min(min(rgb[N - 1][0], rgb[N - 1][1]), rgb[N - 1][2]));

 

5. 전체 코드

https://github.com/Ksiyeong/Algorithm/tree/main/%EB%B0%B1%EC%A4%80/Silver/1149.%E2%80%85RGB%EA%B1%B0%EB%A6%AC