oiehso0

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

풀이

                        1자리  2자리  3자리

뒷자리가 0일때 경우의 수   0개    1개    1개                 0뒤에 1

뒷자리가 1일때 경우의 수    1개    1개    3개                 1뒤에 0 이나 2

뒷자리가 2일때 경우의 수    1개    2개    3개                2뒤에 1 이나 3

뒷자리가 3일때 경우의 수    1개    2개    4개                3뒤에 2 나 4

뒷자리가 4일때 경우의 수    1개    2개    4개                4뒤에 3 이나 5

뒷자리가 5일때 경우의 수    1개    2개    4개                5뒤에 4 나 6

뒷자리가 6일때 경우의 수    1개    2개    4개                6뒤에 5 나 7

뒷자리가 7일때 경우의 수    1개    2개    4개                7뒤에 6 이나 8

뒷자리가 8일때 경우의 수    1개    2개    3개                8뒤에 7 이나 9

뒷자리가 9일때 경우의 수    1개    1개    2개                9뒤에 8

총 계단수            9        17     32    .  . .  .   .

위의 규칙에 따라 식을 만들게 되면 

dp[i][j] = dp[i - 1][j - 1] + dp[i  - 1][j + 1];    과 같은 식이 나오게 된다.

단 뒷자리가 0일 경우와 9일 경우는

dp[i][j] = dp[i - 1][j - 1] + dp[i  - 1][j + 1]; 의 식에서 파란 부분과 빨간 부분의 배열은 존재하지 않기 때문에 예외의 조건식을 작성해주면 된다.

그리고 1000000000으로 나눈 나머지를 출력하면되기 때문에  % 연산을 for문에 넣어준다.

자료형의 범위보다 훨씬 큰 값이 저장되지 않게 나머지를 출력하는 조건을 주어준 것이다.

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

풀이

연속된 수열이 있을때 이 중 연속된 몇개의 숫자를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하는 문제이다.

dp배열(기록해두는 배열)를 이용해서 수열 arr[1]부터 마지막 배열인 arr[n]까지 연산할 것이다.

먼저 arr[1]의 값을 dp[1]에 넣고 

if(dp[n-1] + arr[n] > arr[n]) 의 조건을 준다.

이전 dp(즉, arr[1]부터 arr[n-1] 까지의 합)가 0보다 큰 수라면 다음 배열 arr[n]도 더해서 다음 dp[n]에 저장하도록 한다.

하지만 만약 dp[n-1]이 0이거나 음수라면 과감하게 버려주고 dp[n]에 arr[n]만 넣어준다.

----->>

if(dp[n-1] + arr[n] > arr[n]) dp[n] = dp[n-1] + arr[n];

else dp[n] = arr[n];

위와 같은 식으로 알고리즘을 짜면 그때그때 수열의 합값을 dp에 기록하고 이전 dp가 0으로 접어들게 되면 이전 앞에서 부터 더해줬던 값들은 더할 의미가 사라지기 때문에 꼬리를 자르는 것처럼 버려준다. 그 대신 arr[n]값을 dp[n]에 넣어준다.(이 값이 dp[n]이 가질 수 있는 최대값) 이런식으로 배열 마지막까지 수행하게 되면 dp배열이 만들어 지게 되고

그리고 int Max; 를 만들어서 

Max = dp[1]

for(int i=1; i<N; i++){

if(Max < dp[i]) Max = dp[i];

}

를 해주면 된다.

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

풀이

N잔의 포도주가 일렬로 놓여있다. 포도주 시식을 하는데 2가지 규칙이 존재한다.

1. 포도주 잔을 선택하면 모두 마셔야하고, 마신후에는 제자리에 다시 놓아야 한다.

2. 연속으로 놓여 있는 3잔을 모두 마실 수는 없다.  ex) x o x o o o x 와 같은 경우는 불가하다.

위의 조건을 만족하면서 용량이 큰 포도주만 잘 골라마셔서 누적 최대 합을 만드는 알고리즘을 짜야한다. 

동적 계획법 알고리즘을 짤때 가장 핵심은 주어진 문제를 부분 문제로 나누어 생각해야하고 나눈 부분으로 전체 문제에서 나타날 수 있는 전체 경우의 수를 표현 할 수 있어야한다.

노트를 펴서 규칙을 나누고 생각해보면 3가지 부분으로 전체 문제를 쪼갤 수 있다. 

1. n번째 배열 arr[n]에서 arr[n-1]을 선택하여 마실경우

arr[n-5]    arr[n-4]    arr[n-3]    arr[n-2]    arr[n-1]    arr[n] 이라고 치면 arr[n-2]는 무조건 X(안마심)여야 한다.

arr[n-2]가 X라고 하면 arr[n-3]은 O or X 즉, 마실수도 안 마실 수 도 있지만 최대합을 구하는 문제에서 X(안마심)을 고를 필요는 없기 때문에 

arr[n-3]을 마시게 되고 최종적으로

arr[n-5]    arr[n-4]    arr[n-3]    arr[n-2]    arr[n-1]    arr[n] 

O or X    /  O or X    /     O     /       X       /       O     /      O    /

dp[n] = dp[n-3] + arr[n-1] + arr[n]; 라는 식이 나오게 된다.

2. n번째 배열 arr[n]에서 arr[n-1]을 선택하지 않은 경우 

1번 경우와 마찬가지로 arr[n-1]을 선택하지 않으면 arr[n-2]는 무조건 마시는게 좋기 때문에

arr[n-5]    arr[n-4]    arr[n-3]    arr[n-2]    arr[n-1]    arr[n] 

O  or  X  /  O or X  /  O or X   /       O      /     X        /     O    /

dp[n] = dp[n-2] + arr[n]; 과 같은 식이 나오게 된다.

3. n번째 배열을 arr[n]을 선택하지 않을 경우

arr[n]을 마시지 않으면 arr[n-1]은 선택하지 않아서 마시지 않을 이유가 없다.  그래서

arr[n-5]    arr[n-4]    arr[n-3]    arr[n-2]    arr[n-1]    arr[n] 

 O or X  /   O  or  X /  O or X   /  O or X   /     O     /       X    /

dp[n] = dp[n-1]; 과 같은 식이 나오게 된다.

위의 세 경우를 종합하여 프로그래밍 하면 정답을 출력 할 수 있다.