백준 1149번 - RGB거리

문제 바로가기

🙄 문제 이해

n개의 집을 3개의 색을 사용해 색칠할 때, 겹치지 않게 색칠하는 문제입니다.

여기서 겹치지 않게 색칠한다는 것은 아래와 같습니다.

• n-1번째 집과 n번째 집은 색이 달라야 함.
• n번째 집과 n+1번째 집은 색이 달라야 함.

말이 어렵게 되어있지만, 실제로 따져보면 결국 바로 이전 집에서 사용한 색을 사용하면 안된다는 말과 같습니다.

다시말하자면, 1번 집에서 빨간색을 사용했다면 2번 집은 빨간색을 제외한 초록색, 파란색만 칠할 수 있는 것입니다.

그리고 이 초록색과 파란색 중 더 비용이 저렴한 색을 칠하는 것을 반복합니다.

📝 문제 풀이

DP테이블을 2차원 배열로 생성합니다.
DP테이블의 첫 행을 첫번째 집에 각 색을 칠하는 비용으로 먼저 채워놓고,
다음 집에 이전 집에서 칠한 색을 제외한 색 중 더 저렴한 색을 칠합니다.

첫 행을 제외한 나머지 행에 대해서 이 과정을 수행하므로 1부터 n-1까지 반복하고, 추가로 각 과정에서 현재 집을 해당 색으로 칠하는 비용을 더해줍니다.

마지막 행에서 누적된 값들 중 가장 적은 비용을 출력합니다.

💻 Python 코드

#백준 1149 RGB거리

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

dp = [[0]*3 for _ in range(n)]
dp[0] = arr[0] #첫 행은 비용 그대로

for i in range(1,n):
    # 현재 열을 제외한 i-1행의 열들 중 최솟값 + 현재 칸 비용
    dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + arr[i][0]
    dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + arr[i][1]
    dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + arr[i][2]

print(min(dp[n-1]))