시나위

1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 알고리즘 스터디의 첫 문제이다. 이 문제의 알고리즘은 Dynamic Programming 이다. 이웃하는 집의 색이 같지 않게 하면서 모든 집을 칠해야하고, 이 때의 최소 비용을 구해야한다. 제일 처음 생각했던 건 Greedy 방식이다. 매순간 마다 최소 비용을 선택하되 이웃하는 집의 색이 같지 않게 칠하면 된다. 3 1 100 100 100 100 100 1 100 100 위와 같은 입력에서 입력이 1번 집은 최소 비용이 1인 빨강을 선택..

https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 원형배열에서 동적계획법을 사용하는 문제이다. 첫번째집에 색깔을 고정시켜놓고 구했다. import sys; input = sys.stdin.readline N = int(input()) INF = 2_000_000 rgb = [list(map(int, input().split())) for _ in range(N)] memo = [[0 for _ in range(3)] ..

www.acmicpc.net/problem/1149 1149번: RGB거리 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net N = int(input()) total = [[0]*3 for _ in range(N + 1)] for i in range(1, N + 1): x, y, z = list(map(int, input().split())) if i == 1: total[i] = [x, y, z] else: total[i][0] = min(total[i - 1][1], total[i - 1][2]) + x to..