#1. 문제
https://www.acmicpc.net/problem/1149
#2. 풀이
1. DP
동적 프로그래밍은 문제에 주어진 입력 크기에 따라 중복되는 하위 문제를 재귀적으로 해결하고, 이 결과 값들을 기억하는 것으로 중복 계산을 피해 최적화를 수행하고 효율적으로 최적해를 찾아냅니다.
2. 현재 문제에 대한 세 가지 경우!
- 먼저, 현재 집에 대하여 3가지 경우에 대한 최소 비용을 각각 기억해 줍니다. 이를 위해, 2차원 컨테이너를 통해 빨간색을 칠했을 경우, 초록색을 칠했을 경우, 그리고 파란색을 칠했을 경우를 모두 저장합니다.
- 현재 집이 "R"일 경우, 이전 집의 "G"와 "B"의 비용 중 더 작은 비용을 현재 집의 "R"경우에 더해줍니다.
- 최종적으로, N번째 집의 R, G, 그리고 B 경우의 비용 중 최소 비용을 결과로 출력해 줍니다.
#3. 코드
/*
@링크: https://www.acmicpc.net/problem/1149
* @문제: 1~N번 집을 몇 가지 조건을 준하며 빨강, 초록, 파랑으로 칠하는 최소 비용
1. DP[i] != DP[i-1] && DP[i] != DP[i+1]
2. DP[i] != DP[i+1], if i = 2
3. DP[i] != DP[i-1], if i = N
* @설명
1. 2차원 vector 컨테이너, vector<vector<int>> dp(2, vector<int>(3,0)) 사이즈 선언
2. 현재 집에 대하여 빨간색 칠할 경우 이전 집의 초록색 칠할 경우와 파란색 칠할 경우 중 최소 비용을 더해준다.
*/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int N;
cin >> N;
vector<vector<int>> dp(2, vector<int>(3, 0));
for(int i=0; i<N; ++i)
{
int r, g, b;
cin >> r >> g >> b;
int current = i%2;
int prev = (i-1+2)%2;
dp[current][0] = min(dp[prev][1], dp[prev][2]) + r;
dp[current][1] = min(dp[prev][0], dp[prev][2]) + g;
dp[current][2] = min(dp[prev][0], dp[prev][1]) + b;
}
cout << min(dp[(N-1)%2][0], min(dp[(N-1)%2][1], dp[(N-1)%2][2]));
return 0;
}
'문제 풀이 > BOJ 문제 풀이' 카테고리의 다른 글
[BOJ]#17431_단어 뒤집기 2, string, stack (0) | 2024.08.02 |
---|---|
[BOJ알고리즘, C++]#3190_뱀, deque, map (1) | 2024.07.03 |
[BOJ알고리즘, C++]#11779_최소비용 구하기2, 최단 경로, 길 찾기, 다익스트라, BFS, 너비 우선 탐색 (0) | 2024.06.25 |
[BOJ알고리즘, C++]#6497_전력 난, 최소 신장 트리, 크루스칼 (0) | 2024.06.25 |
[BOJ알고리즘, C++]#1219_오민식의 고민, 최단 경로, 최대 경로, 길 찾기, 벨만-포드 (2) | 2024.06.25 |