문제 요약
각 집은 빨강(R), 초록(G), 파랑(B) 중 하나로 칠할 수 있고,
연속된 집은 같은 색을 칠할 수 없다.
모든 집을 칠하는 데 드는 최소 비용을 구하는 문제.
풀이 과정
조건
- 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
- N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
- i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.
위의 조건을 종합해보면, 이웃한 집끼리는 같은 색일 수 없다.
즉, 연속된 집은 같은 색을 칠하지 않으면서 모든 집을 칠하는 데 드는 최소비용을 구하는 문제다.
내가 떠올린 풀이 과정은 다음과 같다.
첫번째 방법, 완전탐색
집이 최대 1,000개까지 있고,
각 집마다 색을 3개 중 하나로 고를 수 있으니까
3^1000 가지 경우의 수가 나온다. 😱
모든 경우를 다 계산해보는 완전탐색은 무리다;;;
“앞에서 계산한 걸 이용해서 이어가는 방식”을 떠올렸다.
x번째 집이 R, G, B로 칠해졌을 때의 최소비용을 각각 계산한다.
🧠 핵심 로직 정리
dp[i][c]를 이렇게 정의했다.
i번째 집까지 칠했을 때,
i번째 집을 색 c로 칠하는 경우의 최소 누적 비용
그러면 자연스럽게 점화식이 나온다:
(R=0, G=1, B=2)
i번째 집을 빨강(R)으로 칠하면
→ 이전 집은 G 또는 B
dp[i][0] = cost[i][0] + min(dp[i-1][1], dp[i-1][2])i번째 집을 초록(G)으로 칠하면
→ 이전 집은 R 또는 B
dp[i][1] = cost[i][1] + min(dp[i-1][0], dp[i-1][2])i번째 집을 파랑(B)으로 칠하면
→ 이전 집은 R 또는 G
dp[i][2] = cost[i][2] + min(dp[i-1][0], dp[i-1][1])문제가 요구하는 정답은
마지막 집을 R/G/B 중 어떤 색으로 칠하든 그 중 최소값이다.
최종 코드
import sys
input = sys.stdin.readline
n = int(input())
# cost[i][c] : i번째 집의 색칠 비용 (0: R, 1: G, 2: B)
cost = [list(map(int, input().split())) for _ in range(n)]
# dp[i][c] : i번째 집까지 칠했을 때, i번째 집을 c색으로 칠하는 최소 비용
dp = [[0] * 3 for _ in range(n)]
# 첫 번째 집은 그대로 초기화
dp[0][0] = cost[0][0]
dp[0][1] = cost[0][1]
dp[0][2] = cost[0][2]
# 두 번째 집부터 DP 진행
for i in range(1, n):
dp[i][0] = cost[i][0] + min(dp[i-1][1], dp[i-1][2]) # 빨강
dp[i][1] = cost[i][1] + min(dp[i-1][0], dp[i-1][2]) # 초록
dp[i][2] = cost[i][2] + min(dp[i-1][0], dp[i-1][1]) # 파랑
# 마지막 집에서 가능한 색 중 최솟값이 정답
print(min(dp[n-1]))GPT의 제안 : cost 배열을 그대로 dp로 재활용하는 방법
GPT :
조금 더 “실전 스타일”로 쓰면, 아예 dp 배열을 따로 만들지 않고 cost를 덮어쓰는 방식도 많이 써.
여기서 cost[i][색]는 “그 집을 그 색으로 칠했을 때의 최소 누적 비용”으로 재정의되는 셈이야.
cost와 dp 두가지 배열로 나누지말고 cost배열 하나만 두는 방법이다.
시행착오
🤔 처음 접근했던 방식
처음에는 이렇게 생각했다.
- i번째 집을 R로 칠하면
→ 이전 집은 G 또는 B여야 한다 - i번째 집을 G로 칠하면
→ 이전 집은 R 또는 B여야 한다 - i번째 집을 B로 칠하면
→ 이전 집은 R 또는 G여야 한다
그래서 색마다 가능한 이전 색을 정리해 둔 able 배열을 사용했고,
1-based 인덱스로 DP 테이블을 만들어서 정답을 구했다.
내가 처음에 작성한 코드는 다음과 같다:
📄 내가 처음 작성한 코드
n = int(input())
dp = [[0 for i in range(4)] for i in range(n+1)]
cost = [[0 for i in range(4)] for i in range(n+1)]
able = [[0], [0,2,3], [0,1,3], [0,1,2]]
for i in range(1, n+1):
cost[i] = [0] + list(map(int, input().split()))
dp[1] = cost[1]
for i in range(2, n+1):
for color in range(1,4): # r, g, b
c1 = able[color][1]
c2 = able[color][2]
dp[i][color] = min(dp[i-1][c1], dp[i-1][c2]) + cost[i][color]
answer = min(dp[n][1], dp[n][2], dp[n][3])
print(answer)📝 이 코드가 아쉬웠던 점
- 1-based 인덱싱을 사용해 배열 크기가 실제보다 크게 잡힘
able배열이 있으면 로직은 직관적이지만, 오히려 코드 가독성은 떨어짐- 색이 3개뿐인데도 색 인덱스가 1,2,3으로 시작해 약간 번거로움
- Python에서는 0-based가 훨씬 자연스러워서 DP 식도 더 단순해질 수 있음
그래서 전체 코드를 좀 더 파이써닉하고 직관적으로 바꿔보기로 했다.
🎯 리팩토링 목표
- 0-based 인덱스로 변경
- DP 배열 크기를 딱 맞게 줄이기
- 불필요한
able제거 - 점화식을 더 명확하게 표현
- 코드 길이도 짧고 읽기 편하게 만들기
위의 요소들을 모두 반영하여 수정한 코드가 '최종 코드'다.
이번 문제를 통해 배운 점
- 이 문제는 미래의 선택(뒤쪽 선택)이 앞쪽 선택의 최적 여부를 완전히 바꿔버릴 수 있는 경우가 아니다. 그래서 앞에서부터 최소값을 누적하는 방법(DP)이 가능.
- 나는 1-based가 코드짤때 편해서 선택한건데 문제마다 0-based가 유리한 경우도 있고, 1-based가 유리한 경우도 있으니 문제 상황을 고려하여 선택하자.
- Keep : 답이나 힌트를 보지 않고 내 힘으로 풀어냈다!
