[BOJ] 1149 RGB거리 - JAVA

1. 문제

https://www.acmicpc.net/problem/1149

1149번: RGB거리

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

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

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

---

2. 풀이

• 배열 번호를 구분하기 쉽게 하기 위해 int R, G, B 변수에 각각 해당하는 배열 번호를 넣었다.
• 14~16: 집을 칠하는 색 비용을 입력받는다.
• 23~25: 1부터 i까지 색을 칠한 비용을 알기 위해 i번째 집에 R, G, B 각각 색을 칠하면 얼마가 드는지 계산한다. 
  • 1번째 집(i=0)이라면 총 비용은 1번째 집에 색칠하는 데 드는 값과 똑같다.
  • i번째 집에 빨간 색(R)을 칠하려면 i-1집이 초록색(G)이나 파란색(B)이어야 한다. i-1집이 초록색일 때의 총 비용, 파란색일 때의 총비용을 비교해서 더 작은 쪽을 선택한다. 그 비용에 i번째 집의 빨간색을 칠하는 값을 더한다. 

public static void main(String[] args) throws IOException {
   BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
   StringTokenizer st;

   int R = 0, G = 1, B = 2;
   int N = Integer.parseInt(in.readLine());

   int[][] color = new int[N][3];
   int[][] cost = new int[N][3];

   for(int i=0;i<N;i++){
      st = new StringTokenizer(in.readLine());

      color[i][R] = Integer.parseInt(st.nextToken());
      color[i][G] = Integer.parseInt(st.nextToken());
      color[i][B] = Integer.parseInt(st.nextToken());

      if(i==0) {
         cost[0] = color[0];
         continue;
      }

      cost[i][R] = Math.min(cost[i-1][G],cost[i-1][B])+color[i][R];
      cost[i][G] = Math.min(cost[i-1][R],cost[i-1][B])+color[i][G];
      cost[i][B] = Math.min(cost[i-1][R],cost[i-1][G])+color[i][B];

   }

   System.out.println(Math.min(cost[N-1][0],Math.min(cost[N-1][1],cost[N-1][2])));
}

---

3. 결과

위의 코드는 본문에 있는 것과 동일하고, 아래 코드는 한 줄만 다르다.

//수정 전 코드
System.out.println(cost[N-1][0]>cost[N-1][1]? Math.min(cost[N-1][1], cost[N-1][2]):Math.min(cost[N-1][0],cost[N-1][2]));

//본문 코드
System.out.println(Math.min(cost[N-1][0],Math.min(cost[N-1][1],cost[N-1][2])));

 

그런데 Math.min() 함수 코드는 다음과 같다.

public static int min(int a, int b) {
    return (a <= b) ? a : b;
}

 

내가 쓰든 내부적으로 삼항 연산자를 쓰는 것은 동일한데 왜 이렇게 차이가 날지 생각해봤는데 값에 대한 접근 속도 때문이 아닐까 싶다. 수정 전 코드를 사용하면 배열에 총 4번 접근한다. 대신 수정 후 코드를 사용하면 함수의 반환 값을 사용하기 때문에 배열에 3번만 접근한다.

배열에 적게 접근하기 때문에 속도가 빨라지고 반환 값을 임시로 저장하기 위해 메모리 사용이 조금 는 것 같다.