[실버1]백준 1149번(RGB거리) - 코테공부 29일차(2025.02.20)

문제유형

수학

풀이 방법 도출 과정

1. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구하는 것이 문제 

- i-1과 i+1 과 i는 각각 색이 같으면 안됨

3. 각 비용이 낮은 것을 찾으면 됨 단, 이동하면서 칠하기 때문에 잘생각해야함

4. 만약 이렇게 있을 경우

5.

26 40 83

49 60 57

13 89 99 

 

1) 26 2) 57 3) 13이렇게 해서 96이렇게 구해나가면 된다.

6. 이 문제는 현재 집을 칠하는 비용을 이전 집들의 최소 비용과 연계하여 계산해야 하므로, 재귀 함수를 활용한 해결이 가능하다. 즉, 집 i를 칠하는 비용은 i-1번째 집까지의 최소 비용을 고려한 결과로 나타낼 수 있다. 이를 통해, 각 집을 칠하는 최소 비용을 구하는 함수를 작성할 수 있다.

시간 복잡도

시간 복잡도는 DP알고리즘 , for문이 있다. 그 결과 시간복잡도는 O(3n)인데 이는 즉O(n)이므로 괜찮은 시간복잡도를 가지고 있다. 

코드 및 간단설명

사칙연산을 활용한 문제이다.

N = int(input())

# DP 테이블 초기화 (0으로 채운 N x 3 배열)
dp = [[0] * 3 for _ in range(N)]

# 비용 입력
lst = [list(map(int, input().split())) for _ in range(N)]

# 첫 번째 집의 비용을 그대로 가져옴
dp[0] = lst[0]

# DP 테이블 갱신
for i in range(1, N):
    for j in range(3):
        dp[i][j] = lst[i][j] + min(dp[i - 1][(j + 1) % 3], dp[i - 1][(j + 2) % 3])

# 최솟값 출력
print(min(dp[N - 1]))

다른 풀이

1) DP 알고리즘 최적화

더욱 더 나은 방법으로 DP를 사용하는 방법이 있다.  

N = int(input())
# 첫 번째 집의 비용을 입력받아 초기 상태로 사용
prev = list(map(int, input().split()))

# 두 번째 집부터 입력받으며 이전 상태만 이용
for _ in range(1, N):
    cost = list(map(int, input().split()))
    # 현재 집의 각 색상에 대해 누적 최소 비용 계산
    curr = [0] * 3
    curr[0] = cost[0] + min(prev[1], prev[2])
    curr[1] = cost[1] + min(prev[0], prev[2])
    curr[2] = cost[2] + min(prev[0], prev[1])
    # 현재 상태를 이전 상태로 갱신
    prev = curr

# 마지막 집의 최소 비용 출력
print(min(prev))