컴굥일지
[BOJ/백준 1149][C++] RGB거리 본문
반응형
문제
https://www.acmicpc.net/problem/1149
문제 내용
n개의 집을 빨/초/파 3가지 색으로 칠하려고 한다.
각각의 집을 3가지 색으로 칠할 때의 비용이 주어졌을 때, 모든 집을 칠하는 최소 비용을 구하면 된다.
단, 인접한 집은 서로 색이 달라야 한다.
문제 풀이
dp로 문제를 풀 수 있다.
dp[i][0]은 i번째 집을 칠하기까지 필요한 비용 (단, i번째 집은 빨간색)
dp[i][1]은 i번째 집을 칠하기까지 필요한 비용 (단, i번째 집은 초록색)
dp[i][2]은 i번째 집을 칠하기까지 필요한 비용 (단, i번째 집은 파란색)
이런 식으로 설정하고 문제를 풀면 쉽게 해결할 수 있다.
코드
#include <iostream>
using namespace std;
int main() {
int n;
cin >> n;
int arr[n + 1][3];
for (int i = 1; i <= n; i++) {
for (int j = 0; j < 3; j++)
cin >> arr[i][j];
}
int dp[n + 1][3]; // 빨, 초, 파
dp[1][0] = arr[1][0];
dp[1][1] = arr[1][1];
dp[1][2] = arr[1][2];
for (int i = 2; i <= n; i++) {
dp[i][0] = min(dp[i - 1][1], dp[i - 1][2]) + arr[i][0];
dp[i][1] = min(dp[i - 1][0], dp[i - 1][2]) + arr[i][1];
dp[i][2] = min(dp[i - 1][0], dp[i - 1][1]) + arr[i][2];
}
cout << min(dp[n][0], min(dp[n][1], dp[n][2]));
}
반응형
'알고리즘 > 코테 문제' 카테고리의 다른 글
[BOJ/백준 14888][C++] 연산자 끼워넣기 (0) | 2023.07.27 |
---|---|
[BOJ/백준 2193][C++] 이친수 (0) | 2023.07.25 |
[BOJ/백준 2667][C++] 단지번호붙이기 (0) | 2023.07.22 |
[BOJ/백준 1992][C++] 쿼드트리 (0) | 2023.07.22 |
[BOJ/백준 15903][C++] 카드 합체 놀이 (0) | 2023.07.21 |
Comments