[0622] 알고리즘

1149. RGB거리

  다이내믹 프로그래밍 문제. 반복문을 사용하여 풀었다.

  각 집까지의 경로의 최소값을 구하는데, row값이 같으면 같은 색을 칠하는 것이 되기 때문에 색이 다른 두 값을 비교해 더 작은 값을 골라 최소값을 구하는 방식.

 

#include <iostream>
#include <algorithm>

int main()
{
    std::cin.tie(NULL);
    std::ios_base::sync_with_stdio(false);

    int n, min;

    std::cin >> n;    

    int rgb[1001][3];
    int memory[1001][3] = { 0 };

    for (int i = 0; i < n; i++)
    {
      //비용 입력 받기
      std::cin >> rgb[i][0] >> rgb[i][1] >> rgb[i][2];
    }

    for (int i = 0; i < n; i++)
    {
      for (int j = 0; j < 3; j++)
      {
        if (i == 0) memory[i][j] = rgb[i][j];
        else
        {
          if (j == 0)
          {
            memory[i][j] = rgb[i][j] + (memory[i-1][1] > memory[i-1][2] ? memory[i-1][2] : memory[i-1][1]);
          }
          else if (j == 1)
          {
            memory[i][j] = rgb[i][j] + (memory[i-1][0] > memory[i-1][2] ? memory[i-1][2] : memory[i-1][0]);
          }
          else if (j == 2)
          {
            memory[i][j] = rgb[i][j] + (memory[i-1][1] > memory[i-1][0] ? memory[i-1][0] : memory[i-1][1]);
          }
        }
      }
    }
    
    min = memory[n-1][0];
    if (memory[n-1][1] < min) min = memory[n-1][1];
    if (memory[n-1][2] < min) min = memory[n-1][2];

    std::cout << min << '\n';

    return 0;
}

  

  비교적 간단하게 풀긴 했는데 남들 코드에 비해 상당히 더러워보인다는게 흠이다... 사실 2중 for문을 사용하지 않고도 정리할 수 있을 것 같은데, 우선은 금방 통과했음에 만족하기로...