[백준 1149] RGB 거리

RGB 거리(1149)

문제 출처 : https://www.acmicpc.net/problem/1149

N개의 집에 빨강, 파랑, 초록색으로 지붕을 칠해야 하는 문제입니다. 이 때 비용이 최소가 되고, 지붕의 색이 겹쳐지지 않아야 합니다.

어떤 지붕이 빨간색이면 그 앞과 뒤의 집은 빨간색이면 안됩니다. 이렇게 모든 지붕에 색을 칠할 때 최소값을 구하는 문제 입니다. 그럼 다음과 같은 함수를 만들 수 있습니다.

solve(n, c)

이 함수는 n번째 집의 지붕에 c라는 색으로 칠했을 때 드는 최소 비용 입니다. c는 빨강은 0, 파랑은 1, 초록은 2로 입력받도록 합니다.

코드 작성하기

간단한 DP문제이기 때문에 바로 코드를 작성해 보겠습니다.

입력 받기

N = int(input())

cost = [[0, 0, 0]]
for _ in range(N):
    cost.append(list(map(int, input().split())))

먼저 집의 개수 N을 입력 받습니다. 숫자를 계산하기 쉽게 하기 위해 0번째 집을 만들어 [0, 0, 0]으로 넣었습니다. 다음으로 빨강, 파랑, 초록색으로 지붕 색깔을 칠할 때 드는 비용을 cost에 입력 합니다. 숫자가 0부터 시작하는 것이 익숙하다면 굳이 초기값 [0, 0, 0]을 넣어 길이를 맞추어 줄 필요가 없습니다.

출력하기

rst = min(solve(N, 0), solve(N, 1), solve(N, 2))
print(rst)

N개의 집이 존재하고, 각각 빨강, 파랑, 초록색으로 칠했을 경우 각각의 최소 비용을 얻어 이 중 가장 작은 값을 출력하도록 합니다.

solve 함수 1

그럼 이 문제의 핵심인 solve 함수를 구현해 보겠습니다.

def solve(n, c):
    rst = 10e6
    for i in range(3):
        if i == c:
            continue
        rst = min(rst, solve(n - 1, i))
        
    return rst + cost[n][c]

지붕의 종류는 세가지이기 때문에 반복문을 세 번 반복합니다. n - 1번째는 바로 앞의 집입니다. 이 때 같은 색깔의 지붕이 연속으로 있으면 안됩니다. 따라서 현재 지붕색 c와 n - 1번째의 지붕의 색인 i값이 같으면 continue로 넘어갑니다. 그렇게 자신과 같은 색을 제외한 나머지 두 지붕의 색의 최소값을 rst에 저장합니다. 최소값을 구하기 위해 초기값은 10의 6승으로 하였습니다. 집의 개수 최대가 1,000이고 비용의 최대가 1,000이기 때문에 초기값은 1,000 * 1,000인 10의 6승으로 합니다.

마지막으로 rst의 값은 n - 1 번째 집까지의 최소 비용 입니다. 여기에 n번째 집의 지붕 색깔인 c의 가격을 더해줍니다. n번째 지붕의 색은 cost[n][c]에 있기 때문에 최종적으로 리턴해주어야 하는 값은 rst + cost[n][c]가 됩니다.

solve 함수 2

위의 코드는 종료조건, 메모이제이션 처리가 없습니다. 이 두가지를 추가해 주겠습니다.

dp = [[0] * 3 for _ in range(N + 1)]
# solve(n, c) : n번째 집이 c라는 컬러로 칠했을 때 최소 rkqt
def solve(n, c):
    # 종료조건
    if n == 1:
        return cost[n][c]
    
    if dp[n][c]:
        return dp[n][c]

    rst = 10e6
    for i in range(3):
        if i == c:
            continue
        rst = min(rst, solve(n - 1, i))
        
    dp[n][c] = rst + cost[n][c]
    return dp[n][c]

먼저 종료 조건입니다. n의 길이가 1이 되었을 때 현재 지붕의 색깔에 맞게 비용을 지불 합니다. 현재 색깔의 지붕 가격인 cost[n][c]를 리턴하면 됩니다.

다음으로 메모이제이션 처리 입니다. dp[n][c]를 확인해서 기존 값이 있으면 해당 값을 리턴하고, 없으면 계산을 합니다. 계산으로 최소값을 구하면 dp[n][c]에 넣어줍니다.

전체 코드

전체 코드를 확인해 보겠습니다.

N = int(input())

cost = [[0, 0, 0]]
for _ in range(N):
    cost.append(list(map(int, input().split())))

dp = [[0] * 3 for _ in range(N + 1)]
# solve(n, c) : n번째 집이 c라는 색으로 칠했을 때 최소값 리턴
def solve(n, c):
    # 종료조건
    if n == 1:
        return cost[n][c]
    
    # 메모이제이션
    if dp[n][c]:
        return dp[n][c]

    rst = 10e6
    for i in range(3):
        if i == c:
            continue
        rst = min(rst, solve(n - 1, i))
        
    dp[n][c] = rst + cost[n][c]
    return dp[n][c]

rst = min(solve(N, 0), solve(N, 1), solve(N, 2))
print(rst)