0.5초라는 짧은 시간을 통해 브루트포스를 통해 푸는 문제는 아니란 것을 알 수 있음.
현재 선택할 수 있는 색상이 세가지이며, 이전까지의 연산 내용을 저장한 후 활용할 수 있기 때문에 다이나믹 프로그래밍(DP)를 사용해 품.
다이나믹 프로그래밍을 적용하기 위해, 현재까지의 연산 내용을 저장한 후 활용해야겠다는 생각을 함.
현재 사용하는 색상이 세가지 뿐이니, n * 3의 이차원 배열에 현재까지의 연산값을 저장하는게 좋겠다는 생각이 들었지만, 저장할 수가 세가지 뿐이니 배열을 쓰는 대신 변수 3개를 이용하기로 함.
현재의 줄을 n번째라고 할 때, n-1번째까지의 빨강/초록/노랑을 선택했을 시의 최적해를 저장해둔 후, n번째에서 각 색상들의 최적해를 구하는 방향으로 진행. (ex. n번째에 빨강을 칠할 때 비용은, n-1번째 초록/ n-1번째 노랑 중 작은 값 + n번째에 빨강을 칠하는 값)
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));
}
}