oiehso0

https://www.acmicpc.net/problem/2579

풀이

계단을 차근차근 올라 마지막 계단(꼭 거쳐야하는 계단)까지 밟았던 계단의 합이 최대값이 나오게 하는 알고리즘을 짜야한다.

단 조건이 있는데

1. 계단은 한번에 1칸 or 2칸을 올라갈 수 있다.

2. 연속된 세 개의 계단을 모두 밟으면 안된다.

3. 마지막 도착 계단은 반드시 밟아야한다.

1, 2, 3의 조건을 모두 조합해서 최대합 dp를 구하는 식을 나타내보면

arr[1] arr [2]  /중략/  arr[n-5]    arr[n-4]    arr[n-3]    arr[n-2]    arr[n-1]    arr[n]     <<- n개의 계단을 만들었다고 치면 계단 마지막 쯤은 이런식으로 생겼을 것이다. 

n의 계단을 꼭 밟는다는 조건을 충족하기 위해서는 

1. arr[n-3]  ,  arr[n-1]  ,  arr[n] 을 차례로 밟는 경우

2. arr[n-2]    arr[n] 을 차례로 밟는 경우

위의 두가지 경우가 가장 최소한의 경우라고 할 수 있다. 위의 경우는 세가지 조건에 모두 위배되지 않고

두 식으로 충분히 모든 경우의 수를 계산할 수 있다는 것을 노트에 조금만 적어서 생각해보면 알 수 있다. 

그래서 down-top방식으로 dp배열에 누적합을 구해 비교 저장하는 식

1. arr[n-3]  ,  arr[n-1]  ,  arr[n] 을 차례로 밟는 경우를 누적하는 식으로 응용

dp[i] = dp[i - 3] + arr[i] + arr[i - 1];

2. arr[n-2]    arr[n] 을 차례로 밟는 경우

비교해서 저장한다.

-->>

dp[i] = max(dp[i - 2] + arr[i], dp[i - 3] + arr[i] + arr[i - 1]);

https://www.acmicpc.net/problem/1149

풀이

arr[1][1]    arr[1][2]    arr[1][3]

arr[2][1]    arr[2][1]    arr[2][3]

arr[3][1]    arr[3][2]    arr[3][3]    <<----    와 같은 구조를 가지므로 무조건 같은 단(행)에 있는 숫자중에 최소값만 골라서 내려간다고 결과값이 최소가 나오지 않는다는 것을 쉽게 알 수 있었다. 그래서 각 경우의 값들을 모두 비교해줘야한다. 그러기 때문에 1번째 단부터 2,3,... N번째 단까지 한 단씩 3개의 행렬 모두에 최소의 값을 누적하여 저장하면서 내려가는 알고리즘을 짜면된다. 한 단에 3개의 배열이 존재하는데 이웃끼리는 같은 색깔로 색을 칠할 수 없다. 

이 조건을 유의하면 3가지 경우로 나눌 수 있는데

1. K번째 단의 임의의 배열 / arr[i][j]    arr[i][j+1]    arr[i][j+2] / 에서  arr[i][j]에 윗 단의 최소값을 누적하는경우

if(j == 1) arr[i][j] += Min(arr[i-1][j+1], arr[i-1][j+2]);

2. K번째 단의 임의의 배열 / arr[i][j]    arr[i][j+1]    arr[i][j+2] / 에서 arr[i][j+1]에 윗 단의 최소값을 누적하는 경우

else if(j == 2) arr[i][j] += Min(arr[i-1][j-1], arr[i-1][j+1]);

3. K번째 단의 임의의 배열 / arr[i][j]    arr[i][j+1]    arr[i][j+2] / 에서 arr[i][j+2]에 윗 단의 최소값을 누적하는 경우

else arr[i][j] += Min(arr[i-1][j-2], arr[i-1][j-1]);

위의 세가지 경우로 나누어서 코드를 짜면 된다. 

그리고 가장 마지막 단에서 누적된 3개의 배열의 값을 비교해주고 가장 최소값을 출력해 주기만 하면 된다.

https://www.acmicpc.net/problem/1932

풀이

arr[1][1]

arr[2][1]    arr[2][2]

arr[3][1]    arr[3][2]    arr[3][3]

arr[4][1]    arr[4][2]    arr[4][3]    arr[4][4]  <<------와 같은 구조로 이루어져있고 무조건 같은 단(행)에 있는 숫자중에 최대값만 따라 간다고 해서 결과값이 최대가 나오지 않는다는 것을 알 수 있다. 결국 모든 각각 배열공간에 위 값을 누적해서 넣어준다.

먼저 모든 연산을 식으로 정리해 본다면  3가지 경우로 나눌 수있다.

1. arr[1][1] -> arr[2][1] -> arr[3][1] -> arr[4][1] 과 같이 맨 왼쪽 배열만 따라서 누적해주는 경우

if(j == 1) arr[i][j] += arr[i-1][j];

2. arr[1][1] -> arr[2][2] -> arr[3][3] -> arr[4][4] 과 같이 맨 오른쪽 배열만 따라서 누적해주는 경우

if else(i == j) arr[i][j] += arr[i-1][j-1];

3. 위의 두가지 경우가 아닌 중간에 위치한 배열에 상위 값을 누적해줄 경우 

왼쪽 대각선과 오른쪽 대각선 값 2가지가 존재하므로 max함수를 만들어서 비교후 누적해준다.

else arr[i][j] += max(arr[i-1][j-1], arr[i-1][j]);

위의 코드가 핵심이다. 이를 종합하면 아래와 같은 답안 코드를 작성할 수 있다. 

실행시간을 줄이기 위해서 어떻게 해야하는지 생각해봤는데 결국 마지막 단에서 모든 배열에 대해서 연산을 해주고 마지막 단에서 max값을 찾는 방법 밖에 없었다.