미소를뿌리는감자의 코딩
[백준 2024/02/28] 1149번 RGB거리 본문
728x90
https://www.acmicpc.net/problem/1149
1. 접근 방법
dp으로 접근해야겠다고 생각이 들었다.
그 이유로는, 각 단계별 작은 값을 선별해야하기 때문이다.
포인트는 배열에, 선택한 값 + 기존 배열에 저장되어 있는 값을 더한 수 새로 넣어주어야 한다는 점이다.
이렇게 구성해야지, 다음 배열에서 값을 고를 때, 지금까지 골라온 총 값 중에서 최솟값을 선택할 수 있기 때문이다.
2. 코드
def find_min_cost(N, costs):
dp = [[0 for _ in range(3)] for _ in range(N)]
for i in range(3):
dp[0][i] = costs[0][i]
for i in range(1, N):
dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + costs[i][0]
dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + costs[i][1]
dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + costs[i][2]
return min(dp[N - 1])
costs = []
n = int(input())
for _ in range(n):
line = list(map(int, input().split()))
costs.append(line)
min_cost = find_min_cost(n, costs)
print(min_cost)
728x90
'코딩 테스트 > 백준' 카테고리의 다른 글
[백준 2024/03/20] 9461번 파도반 수열 (0) | 2024.03.20 |
---|---|
[백준 2024/03/19] 9184번 신나는 함수 실행 (0) | 2024.03.19 |
[백준 2024/02/28] 5705번 Hexagonal Tiles (1) | 2024.02.28 |
[백준 2024/02/27] 2579번 계단 오르기 (0) | 2024.02.27 |
[백준 2024/02/26] 1956번 운동 (1) | 2024.02.26 |