이것도 하나하나 탐색해가며 찾으면 될 것같다. 저번 타일링 문제 처럼 말이다.
일단 점화식부터 세워야 하는데 기본적으로 모든 값중 최솟값을 찾는 점화식부터 세워보자
N이 0일땐, 아무것도 채워넣을 수 없다. 그러므로 dp[0]은 0,
일단 예제에서 N 이 1일땐, 0번째는 26 1번째는 40 2번째는 83이다. 이중 최솟값은 26이니 dp[1]는 26,
N이 2일땐 0번째는 49 1번째는 60 2번째는 57이다. 이중 최솟값은 49이니 dp[2]는 dp[1]까지 합친 값인 75
그럼 점화식은 결국 dp[i] = dp[i-1] + arr[i]; 이다. (arr[i] 는 현재 N값중 가장 작은 값이다.)
이제 제약조건인 이웃이 이미 칠한 색깔은 칠 할 수 없다 를 풀어보자
일단 arr와 dp를 모두 2차원 배열로 설정해준다
N값은 최대 1000보다 작거나 같다라고 했으니 dp[1001][3] 이라고 하면 될 것같다.
N이 2라면, N이 1일때만 확인해 주면 된다. 왜냐면 N이 1일때부터 하나씩 칠하면서 올라 오는데, N이 2일땐 1일때 칠하지 않는 값중 최솟값만 찾으면 되니까.
N이 3일땐 2일때 칠하지 않는 값중 최솟값만 찾으면 된다.
만약 N이 2고 빨강(arr[0])을 칠했다면, N이 1일때는 arr[0]를 칠할 수 없다. dp[2][0] = min(dp[1][1],dp[1][2]) + arr[0];
만약 N이 2고 초록(arr[1])을 칠했다면, N이 1일때는 arr[1]를 칠할 수 없다. dp[2][1] = min(dp[1][0],dp[1][2]) + arr[1];
만약 N이 2고 파랑(arr[2])을 칠했다면, N이 1일때는 arr[2]를 칠할 수 없다. dp[2][2] = min(dp[1][0],dp[1][1]) + arr[2];
dp[2][0] = min(dp[1][1],dp[1][2]) + arr[2][0]; 내가 2번째 층에선 빨강(arr[2][0])을 칠할건데, 1번째 층에 초록, 파랑중 최솟값이 누구냐?
dp[2][1] = min(dp[1][0],dp[1][2]) + arr[2][1]; 내가 2번째 층에선 초록(arr[2][1])을 칠할건데, 1번째 층에 빨강, 파랑중 최솟값이 누구냐?
dp[2][2] = min(dp[1][0],dp[1][1]) + arr[2][2]; 내가 2번째 층에선 파랑(arr[2][2])을 칠할건데, 1번째 층에 빨강, 초록중 최솟값이 누구냐?
dp[3][0] = min(dp[2][1],dp[2][2]) + arr[3][0];
dp[3][1] = min(dp[2][0],dp[2][2]) + arr[3][1];
dp[3][2] = min(dp[2][0],dp[2][1]) + arr[3][2];
<해석....?>
솔직히 그림으로 그려서 하나씩 풀어나가려했는데도
조금 이상하게 설명한 것 같다..
DP가 없고 arr만 있다고 가정했을때
arr[2]가 만약 빨강을 칠했다? 그럼 arr[1]는 초록 또는 파랑만 칠할 수 있다. 이거를 2차원 배열로 나타내면
arr[2][0] 을 칠하면 arr[1][1] 또는 arr[1][2]만 칠할 수 있는 것이다.
arr은 결국 모든 층의 빨강([0]), 초록([1]), 파랑([2]) 의 값을 저장해놓은 녀석이므로
dp를 하나 만들어 N층이 빨강, 초록, 파랑으로 칠해질때 각 각의 최솟값들을 구해내는 방식으로 했다.
<풀이소스>
풀고나서 어안이 벙벙하네
어떻게 풀었너;;;;;
'알고리즘 > 동적계획법' 카테고리의 다른 글
| [백준] 1912번 연속합 (0) | 2019.01.26 |
|---|---|
| [백준] 1932번 정수 삼각형 (0) | 2019.01.26 |
| [백준] 11727번 2 x n 타일링 2 (0) | 2019.01.24 |
| [백준] 11726번 2 x n 타일링 (0) | 2019.01.24 |
| [백준] 2579번 계단 오르기 (0) | 2019.01.24 |
