#17404: RGB거리 2

https://www.acmicpc.net/problem/17404

새벽감성으로 써 봅니다. 휴가 복귀 생각에 잠이 안 와서…

https://www.acmicpc.net/problem/1149

골드4 RGB 거리는 실버1 RGB거리와 무엇이 다른가! 했더니

맨 마지막 집이 맨 앞 집과 색이 같으면 안된다는 조건이 추가되었을 뿐이군요.

그렇다면 그냥 N-1 번째집까지만 1149번 코드와 똑같이 푼 다음
마지막 N번째 집만 1번째 집 색깔과 다른 색으로 해주면 되네요.

집 선택해주는 for 루프 3번 도는 코드 추가만 시켜주면 완성입니다.


def main(f=None):
    init(f)
    # sys.setrecursionlimit(10**9)
    # ######## INPUT AREA BEGIN ##########

    N = int(input())
    C = []
    for _ in range(N):
        r, g, b = map(int, input().split())
        C.append([r, g, b])

    # ######## INPUT AREA END ############

    dp = [[0, 0, 0] for _ in range(N)]

    cand = 10 ** 9
    for k in range(3):
        for i in range(3):
            if i == k:
                dp[0][i] = C[0][i]
            else:
                dp[0][i] = 10**9
        for i in range(1, N):
            dp[i][0] = C[i][0] + min(dp[i-1][1], dp[i-1][2])
            dp[i][1] = C[i][1] + min(dp[i-1][0], dp[i-1][2])
            dp[i][2] = C[i][2] + min(dp[i-1][0], dp[i-1][1])
        dp[N-1][k] = 10 ** 9
        cand = min(cand, *dp[N-1])
    print(cand)

써보고 보니까 굳이 메모리 저렇게 많이 안 써도 되는 게 기억났는데
귀찮고 어차피 통과되니까 그냥 올려봅니다.

1 Like