BOJ 1149. RGB거리

🙇‍♀️[Silver I] RGB거리 - 1149

문제 링크

성능 요약

메모리: 2032 KB, 시간: 0 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 1월 7일 19:49:50

문제 설명

RGB거리에는 집이 N개 있다. 거리는 선분으로 나타낼 수 있고, 1번 집부터 N번 집이 순서대로 있다.

집은 빨강, 초록, 파랑 중 하나의 색으로 칠해야 한다. 각각의 집을 빨강, 초록, 파랑으로 칠하는 비용이 주어졌을 때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값을 구해보자.

• 1번 집의 색은 2번 집의 색과 같지 않아야 한다.
• N번 집의 색은 N-1번 집의 색과 같지 않아야 한다.
• i(2 ≤ i ≤ N-1)번 집의 색은 i-1번, i+1번 집의 색과 같지 않아야 한다.

입력

첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 같은 자연수이다.

출력

첫째 줄에 모든 집을 칠하는 비용의 최솟값을 출력한다.

🚀풀이

처음에 완전탐색으로 DFS를 이용해서 문제를 풀려고했다.

void DFS(int L, int cost, char ch)
{
	if (L == n - 1)
	{
		res = min(res, cost);
		return;
	}
	else
	{
		if (ch != 'R')
			DFS(L + 1, cost + houses[L + 1].r, 'R');
		if (ch != 'G')
			DFS(L + 1, cost + houses[L + 1].g, 'G');
		if (ch != 'B')
			DFS(L + 1, cost + houses[L + 1].b, 'B');
	}
}

이렇게 로직을 짜니까 시간제한이 나왔다.

오답 버전은 아래와 같다.

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

struct House
{
	int r, g, b;
};

int n, res = 123456789;
vector<House> houses;
void setting()
{
	cin >> n;
	int r, g, b;
	for (int i = 0; i < n; ++i)
	{
		cin >> r >> g >> b;
		houses.push_back({ r, g, b });
	}
}

void DFS(int L, int cost, char ch)
{
	if (L == n - 1)
	{
		res = min(res, cost);
		return;
	}
	else
	{
		if (ch != 'R')
			DFS(L + 1, cost + houses[L + 1].r, 'R');
		if (ch != 'G')
			DFS(L + 1, cost + houses[L + 1].g, 'G');
		if (ch != 'B')
			DFS(L + 1, cost + houses[L + 1].b, 'B');
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	//freopen("input.txt", "rt", stdin);

	setting();
	DFS(0, houses[0].r, 'R');
	DFS(0, houses[0].g, 'G');
	DFS(0, houses[0].b, 'B');

	cout << res;

	return 0;
}

DP를 이용한 풀이는 다음과 같다.

#define _CRT_SECURE_NO_WARNINGS

#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include<iostream>
#include <fstream>
#include <vector>
#include <algorithm>

using namespace std;

int house[1001][3];
int N;
int cost[3];
void solve()
{
    house[0][0] = 0;
    house[0][1] = 0;
    house[0][2] = 0;
    cin >> N;
    for (int i = 1; i <= N; ++i)
    {
        cin >> cost[0] >> cost[1] >> cost[2];
        house[i][0] = min(house[i - 1][1], house[i - 1][2]) + cost[0];
        house[i][1] = min(house[i - 1][0], house[i - 1][2]) + cost[1];
        house[i][2] = min(house[i - 1][1], house[i - 1][0]) + cost[2];
    }
    cout << min(house[N][2], min(house[N][0], house[N][1]));
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    //freopen("input.txt", "rt", stdin);

    solve();
}