728x90
반응형
1149번: RGB거리
문제
https://www.acmicpc.net/problem/1149
풀이
칠해야 하는 집의 수 N이 주어진다. 이후 각 집에 대하여 빨강, 초록, 파랑으로 칠했을 때의 비용이 한 줄에 주어진다. i번째 집의 색은 i-1, i+1번째 집의 색과는 달라야 한다. 조건에 맞게 모든 집을 칠했을 때 비용의 최솟값을 구하는 문제다.
dp를 사용해 풀 수 있다. dp[1001][3] 크기의 0으로 초기화된 이중 배열을 만든다. 1001은 몇 번째 집인지를 의미하고 3은 R, G, B 중 하나로 칠했을 각각의 경우의 가격을 의미한다. i번째 집의 비용이 입력될 때, 빨간색을 칠할 경우엔 i-1번째 집에 초록색, 파란색을 칠한 경우 중 최솟값에 더한 값을 저장한다. 파란색인 경우엔 빨간색, 초록색 중 최솟값, 초록색인 경우엔 빨간색, 파란색 중 최솟값에 가격을 더한다.
마지막 집까지 색칠한 후, 마지막 집에 칠한 색깔이 빨간색, 초록색, 파란색인 각 경우에 대하여 최솟값을 출력하면 된다.
코드
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int n;
cin >> n;
int dp[1001][3] = {0};
for (int i = 1; i <= n; i++) {
int r, g, b;
cin >> r >> g >> b;
dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + r;
dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + g;
dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + b;
}
cout << min(min(dp[n][0], dp[n][1]), dp[n][2]) << '\n';
return 0;
}
728x90
반응형
'Problem Solving > BOJ' 카테고리의 다른 글
[백준 / BOJ] C++ 1153 네 개의 소수 (0) | 2023.02.11 |
---|---|
[백준 / BOJ] C++ 1152 단어의 개수 (0) | 2023.02.11 |
[백준 / BOJ] C++ 1145 적어도 대부분의 배수 (0) | 2023.02.11 |
[백준 / BOJ] C++ 2565 전깃줄 (0) | 2023.02.10 |
[백준 / BOJ] C++ 11722 가장 긴 감소하는 부분 수열 (0) | 2023.02.09 |