백준 1149 - RGB 거리 (java)

JeongEun Kim·2023년 3월 28일
2

문제 링크


접근

0.5초라는 짧은 시간을 통해 브루트포스를 통해 푸는 문제는 아니란 것을 알 수 있음.
현재 선택할 수 있는 색상이 세가지이며, 이전까지의 연산 내용을 저장한 후 활용할 수 있기 때문에 다이나믹 프로그래밍(DP)를 사용해 품.

풀이

다이나믹 프로그래밍을 적용하기 위해, 현재까지의 연산 내용을 저장한 후 활용해야겠다는 생각을 함.
현재 사용하는 색상이 세가지 뿐이니, n * 3의 이차원 배열에 현재까지의 연산값을 저장하는게 좋겠다는 생각이 들었지만, 저장할 수가 세가지 뿐이니 배열을 쓰는 대신 변수 3개를 이용하기로 함.
현재의 줄을 n번째라고 할 때, n-1번째까지의 빨강/초록/노랑을 선택했을 시의 최적해를 저장해둔 후, n번째에서 각 색상들의 최적해를 구하는 방향으로 진행. (ex. n번째에 빨강을 칠할 때 비용은, n-1번째 초록/ n-1번째 노랑 중 작은 값 + n번째에 빨강을 칠하는 값)

정답 코드 (java/자바)

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class BOJ1149 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] str = br.readLine().split(" ");
		
		//a, b, c : n-1번째의 빨강, 노랑, 초록의 최적해
        //ina, inb, inc : n번째로 각 색상을 칠하는 비용
		int ina, inb, inc, a, b, c;
		int n = Integer.parseInt(str[0]);
		a = b = c = 0;
		
		for(int i = 0; i < n; i++) {
			str = br.readLine().split(" ");
			//현재 줄의 비용 입력받기
			ina = Integer.parseInt(str[0]);
			inb = Integer.parseInt(str[1]);
			inc = Integer.parseInt(str[2]);
			//현재의 최적해 찾기
            //a, b, c에 바로 값을 할당하지 않도록 주의
			ina = ina+Math.min(b, c);
			inb = inb+Math.min(a, c);
			inc = inc+Math.min(a, b);
			a = ina;
			b = inb;
			c = inc;
		}
		ina = Math.min(a, b);
		System.out.println(Math.min(ina, c));
	}

}

0개의 댓글