본문으로 바로가기
  • DP로 문제를 해결할 수 있다.
  • 임의의 집을 3가지 색으로 칠했을 경우의 수를 모두 구한 다음, 그 중 최소 비용을 출력하면 된다.
#include <cstdio>
#include <algorithm>
using namespace std;

const int R = 0;
const int G = 1;
const int B = 2;

int n;
int a[1000][3];// 집을 색칠하는데 드는 각 비용
int c[1000][3];// 최소 비용을 구하기 위한 배열

int f(int, int);// 임의의 집을 임의의 색으로 칠할 때의 최소 비용

int main() {
  scanf("%d", &n);
  for (int i=0; i<n; i++) {
    scanf("%d %d %d", &a[i][R], &a[i][G], &a[i][B]);
  }
  printf("%d\n", min(f(n-1, R), min(f(n-1, G), f(n-1, B))));
  return 0;
}

int f(int n, int k) {
  if (n == 0) return a[n][k];
  if (c[n][k]) return c[n][k];
  if (k == R) c[n][k] = a[n][k] + min(f(n-1, G), f(n-1, B));
  if (k == G) c[n][k] = a[n][k] + min(f(n-1, R), f(n-1, B));
  if (k == B) c[n][k] = a[n][k] + min(f(n-1, R), f(n-1, G));
  return c[n][k];
}

'Programming > Baekjoon Online Judge' 카테고리의 다른 글

[BOJ] 1225: 이상한 곱셈  (0) 2018.06.11
[BOJ] 1159: 농구 경기  (0) 2018.06.11
[BOJ] 1149: RGB 거리  (0) 2018.06.11
[BOJ] 1100: 하얀 칸  (0) 2018.06.11
[BOJ] 1094: 막대기  (0) 2018.06.11
[BOJ] 1085: 직사각형에서 탈출  (0) 2018.06.11

댓글을 달아 주세요