Algorithm, boj, 1149(RGB거리), dp

DP(다이나믹 프로그래밍)

• 주어진 문제를 여러 개의 부분문제들로 나누어 푼 다음, 그 결과들로 주어진 문제를 푼다
• dp는 겹치는 문제가 발생하기 때문에 메모제이션 등이 필요하다
  

  해결하지 못한 원인

• 누적된 결과로 해결하는 것이기때문에 누적된것은 항상 최선이여야 한다.
• 해결 이론은 탑다운, 구현은 바텀업

내 코드

 package org.baekjoon;

import java.util.Scanner;

public class test1149 {
	public static void main(String[] args) {
		  Scanner sc = new Scanner(System.in);

		  int n = sc.nextInt();
		  int[][] list = new int[n][3];
		  int[][] result = new int[n][3];
		  int min = 0;

		  for (int i=0; i<n; i++) {
			  for (int j=0; j<3; j++)
				  list[i][j] = sc.nextInt();
		  }

		  if(n == 1) {
			  min = findMin(list[0][0], list[0][1], list[0][2]);
		  }
		  else {
				  result[0][0] = Math.min(list[0][1], list[0][2]) + list[1][0];
				  result[0][1] = Math.min(list[0][0], list[0][2]) + list[1][1];
				  result[0][2] = Math.min(list[0][0], list[0][1]) + list[1][2];

			  if (n>2) {
				  for (int i=1; i<n-1; i++) {
					  result[i][0] = Math.min(result[i-1][1], result[i-1][2]) + list[i+1][0];
					  result[i][1] = Math.min(result[i-1][0], result[i-1][2]) + list[i+1][1];
					  result[i][2] = Math.min(result[i-1][0], result[i-1][1]) + list[i+1][2];
				  }
			  }
			  min = findMin(result[n-2][0],result[n-2][1],result[n-2][2]);
		  }
		  System.out.println(min);
	}
	static int findMin(int a, int b, int c) {
		int min = a;
		if( a > b) {
			if (b > c)
				min = c;
			else
				min = b;
		}
		else {
			if (a > c)
				min = c;
		}
		return min;
	}

}

다른 분의 코드

public class BOJ1149 {
  public static void main(String[] args) {
    Scanner scanner = new Scanner(System.in);
    int N = scanner.nextInt();
    int[][] cost = new int[3][N];
    int r, g, b;

    cost[0][0] = scanner.nextInt();
    cost[1][0] = scanner.nextInt();
    cost[2][0] = scanner.nextInt();

    for(int i = 1; i < N; i++) {
      r = scanner.nextInt();
      g = scanner.nextInt();
      b = scanner.nextInt();

      cost[0][i] = r + Math.min(cost[1][i-1], cost[2][i-1]);
      cost[1][i] = g + Math.min(cost[0][i-1], cost[2][i-1]);
      cost[2][i] = b + Math.min(cost[0][i-1], cost[1][i-1]);
    }
    System.out.println(Math.min(cost[0][N-1], Math.min(cost[1][N-1], cost[2][N-1])));
    scanner.close();
  }
}

---

Reference

문제바로가기 문제풀이