[백준] RGB 거리

RGB 거리 (실 1) : https://www.acmicpc.net/problem/1149

 

 

N개의 집이 주어지고 각 집을 세 가지 색깔로 칠할 시, (단, 색깔은 이전 집을 칠한 색깔과 동일하면 안된다) 모든 집을 칠하는 비용의 최솟값을 구하는 문제.

 

---

 

1. 문제 분석

 

모든 집을 칠하는 최솟값을 구하는 문제이니, 최적화 문제.

1. 그리디한 접근이 가능한가?

 

각 선택에 대하여 최솟값만을 선택한다고 했을 시, 정답이 된다는 보장이 없다. 반례도 충분하다.

따라서, 칠하는 경우의 수와 최솟값를 하나하나 계산해봐야 한다.

 

2. 최적 부분 구조인가?

yes. 이전 선택에 관계없이, 각 부분 문제를 최적으로 풀었을 시 전체의 해답이 나옴. DP 식을 도출해보면 알 수 있음.

집 칠하는 비용의 최솟값을 리턴하는 함수를 getMinCost, 이전에 고른 색깔을 prevSelect, 현재 고른 횟수를 selectCnt라 했을시, 

getMinCost(prevSelect, prevSelect)
= Min(getMinCost(이전 색깔 제외1, prevSelect + 1) + 선택 cost, getMinCost(이전 색깔 제외2, prevSelect + 1) + 선택 cost)

 

2. 완전 탐색

 

#include <iostream>
#include <stdio.h>

using namespace std;

int N, costs[1001][3];

// 집 칠하는 비용의 최솟값을 리턴하는 함수
// selectCnt = 현재까지 고른 집의 갯수
// prevSelect = 이전에 선택한 색의 인덱스
// costSum = 현재까지 비용의 총 합
int getMinCost(int selectCnt, int prevSelect, int costSum)
{
  if (selectCnt == N)
    return costSum;

  int least = 100000000;

  for (int selectIdx = 0; 3 > selectIdx; selectIdx++)
  {
    if (selectIdx == prevSelect) //N번 집의 색깔 != N-1번 집의 색깔 규칙
      continue;

    int cand = getMinCost(selectCnt + 1, selectIdx, costSum + costs[selectCnt][selectIdx]);
    least = min(cand, least);
  }

  return least;
}

int main(void)
{
  int k;

  scanf("%d", &N);

  // 입력으로부터 costs 초기화
  for (int i = 0; N > i; i++)
    for (int j = 0; 3 > j; j++)
    {
      scanf("%d", &k);
      costs[i][j] = k;
    }

  cout << getMinCost(0, -1, 0) << '\n';

  return 0;
}

 

 

3. 최적화 DP화

최적화 DP 레시피(https://sanghoonly.tistory.com/37)를 적용. 완전 탐색 코드에서 메모이제이션을 적용한 것 이외의 큰 차이는 없음.

#include <iostream>
#include <stdio.h>
#include <memory.h>

using namespace std;

int N, costs[1001][3], cache[1001][4];

// 집 칠하는 비용의 최솟값을 리턴하는 함수
// selectCnt = 현재까지 고른 집의 갯수
// prevSelect = 이전에 선택한 색의 인덱스

int getMinCost(int selectCnt, int prevSelect)
{
  if (selectCnt == N)
    return 0;

  int &ref = cache[selectCnt][prevSelect];
  if (ref != -1)
    return ref;

  int least = 100000000;

  for (int selectIdx = 0; 3 > selectIdx; selectIdx++)
  {
    if (selectIdx == prevSelect) //N번 집의 색깔 != N-1번 집의 색깔 규칙
      continue;

    int cand = getMinCost(selectCnt + 1, selectIdx) + costs[selectCnt][selectIdx];
    least = min(cand, least);
  }

  return ref = least;
}

int main(void)
{
  int k;

  scanf("%d", &N);

  memset(cache, -1, sizeof(cache));

  // 입력으로부터 costs 초기화
  for (int i = 0; N > i; i++)
    for (int j = 0; 3 > j; j++)
    {
      scanf("%d", &k);
      costs[i][j] = k;
    }

  cout << getMinCost(0, 3) << '\n';

  return 0;
}