[ACMICPC.NET] 1149번 RGB 거리 RGB 거리문제를 풀때 한가지 기억해야할 전제 조건이 있다. N까지의 누적 최소합 = N-1까지의 누적최소합 + N번째의 최소값이라는 것이다. 둘중 어느 하나라도 최소값이 아닐 경우 N번째까지의 누적 값이 최소값이라고 보장할 수 없게된다. 왜 이런지 생각해보면 아래와 같다.만약 N-1까지의 누적값이 최소가 아니라면 최소값은 분명 존재할 것이고 이때 각각 N번째 최소값을 더한다면 N까지의 누적값이 최소값이 아니게 된다. 이를 이용하여 세울 수 있는 점화식은 2가지가 존재한다. 1. 2차원 배열을 이용하여 점화식 도출 int DP[1000][3]2. 1차원 배열을 이용하여 점화식 도출 int DP[3] 이제 점화식을 세울 차례이다.점화식을 세우기 앞서 문제를 요약해보면 아래와 같다. 1 ~ N 까지의 집이 .. 더보기 이전 1 ··· 3 4 5 6 7 8 9 ··· 69 다음