[다이나믹 프로그래밍] 1149번 - RGB거리

[백준] 1149번 - RGB거리

(한줄평) 아이디어를 쉽게 떠올릴 수 있었던 문제! 효율적인 코드를 짤 수 있게 고민해볼 수 있는 문제였다

이 문제는 집의 수 n(2 <= n <= 1000)과 n개의 줄에 각 집을 빨강, 초록, 파랑으로 칠하는 비용(1000이하 자연수)가 주어질 때 모든 집을 칠하는 비용의 최솟값을 구하는 문제다. 

 

유사 문제: https://hseungyeon.tistory.com/289

[다이나믹 프로그래밍] ▲ 문제5 - 금광(52:30)

 

(풀이1) dp테이블을 따로 생성, 반복문으로 비용 계산(내 풀이)

풀이 시간: 25분 이내

1) 문제 해결 아이디어

n개의 집 칠하는 비용을 담는 2차원 리스트(graph)를 생성하고 같은 크기의 dp테이블을 0으로 초기화하여 생성한다. 현재 행에 대해 값을 계산할 때 이전행의 값들을 검사하기 때문에 이전행이 없는 0번째 행은 graph의 0번째 행의 값으로 초기화 한다. 그래서 1 ~ (n - 1)번째 행까지 반복문을 돌리며 (현재열과 다른 열들의 값들 중 최솟값 + 현재칸의 값)을 기록한다.

 

<점화식>

첫번째 오류. 틀렸습니다

예제 입력 5개로는 다 맞게 출력이 되었는데 정답을 제출하니 바로 틀렸습니다가 나왔다.

해당칸까지의 최소비용을 계산할 때 (자기자신값, 이전에 선택하지 않았던 색들의 최소값) 중에서 선택하게 하면 문제가 발생한다. 어차피 현재칸의 값은 덮어쓰여질 일이 없기 때문에 자기자신값은 최솟값을 계산하는데 포함시킬 필요가 없다!!!

 

2) 소스코드

import sys
input = sys.stdin.readline

n = int(input())  # 집 수
# n개의 집 칠하는 비용(R, G, B)
graph = [list(map(int, input().split())) for _ in range(n)]
d = [[0] * 3 for _ in range(n)] # i번째 집까지 칠하는 최소 비용

for i in range(n):
  # 초기화
  if i == 0:
    for j in range(3):
      d[i][j] = graph[i][j]
  else:
    for j in range(3):
      d[i][j] = graph[i][j] + min(d[i - 1][(j + 1) % 3],  d[i - 1][(j + 2) % 3])

print(min(d[n - 1]))  # 모든 집을 칠하는 최소 비용

 

(풀이2) 시간 효율이 좀 더 좋은 코드

풀이 시간: 10분 이내

1) 문제 해결 아이디어

같은 행에서 다른 열들의 값을 차례로 계산할 때 이전에 기록된 열의 값이 현재 열의 값을 계산하는데 전혀 영향을 미치지 않는다. 그러므로 집을 칠하는 비용을 저장할 곳과 dp테이블을 따로 설정할 필요는 없다!

처음부터 dp테이블(d)에 값을 입력받고 1번째 행부터 (n-1)번째 행까지 값을 계산하여 기록하면 된다.

또한 위에서처럼 반복문으로 해도되지만 어차피 열의 개수는 3개로 고정되어있으므로 각 열의 값을 구하는 식을 따로 적어주어도 된다!

 

2) 소스코드

import sys
input = sys.stdin.readline

n = int(input())  # 집 수
# n개의 집 칠하는 비용(R, G, B)
d = [list(map(int, input().split())) for _ in range(n)]

# 1행부터 집 칠하는 최소 비용 계산
for i in range(1, n):
  # 현재칸과 다른 열들의 값 중 최소값 선택
  d[i][0] += min(d[i - 1][1], d[i - 1][2])
  d[i][1] += min(d[i - 1][0], d[i - 1][2])
  d[i][2] += min(d[i - 1][0], d[i - 1][1])
print(min(d[n - 1]))  # 모든 집을 칠하는 최소 비용

[참고] https://pacific-ocean.tistory.com/147

[백준] 1149번(python 파이썬)