oiehso0

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

풀이

기존의 2xn타일링 문제에서 2x2타일이 추가된 형태이다.

기존 문제에서 2xn 크기의 직사각형을 1x2타일과 2x1타일을 이용해 채웠을때

dp[n] = dp[n-1] + dp[n-2]; 과 같은 식이 성립했다.

그 이유는 dp[n-1]까지의 타일 끝에 2x1의 타일을 이어 붙이는 경우 / dp[n-2]까지의 타일 끝에 1x2타일 두장을 이어 붙이는 경우를 더해 dp[n]의 타일의 경우의 수가 도출

되었기 때문이다. 

 <<< --- 타일링 2 문제에서는 n-2까지의 타일에 이어 붙이는 2x2 사각형의 경우가 1x2타일 2 개와 2x2타일 1 개를 이어 붙이는 경우로 나누어 지기 때문에

타일링 2 문제의 경우에서는

dp[n] = dp[n-1] + dp[n-2] * 2 ; 라는 식이 성립하게 된다. 

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

풀이

수열 중 가장 긴 증가하는 부분 수열을 구하면 된다.

arr[1] ... arr[n-1], arr[n]까지 총 n개의 수열이 주어진다고 할 때

dp[n] 을 이용해서 n번째 수열까지의 부분수열의 최대값을 저장하려고 한다.

1번째로 세워야할 조건

arr[n] > arr[n-1] 인가? 아니라면 증가하는 부분 수열이라고 할 수 없기 때문이다.

arr[i]를 마지막 배열이라고 가정 했을 때 수열의 최대 길이를 dp[i]라고 한다. 그러면  최대 dp[i]를 구하기 위해서 

arr[1], arr[2], arr[3] ... arr[i-1]까지 arr[i]보다 작은수가 존재하지 않는다면 dp[n]은 1이 될 것이다.

만약 arr[3]까지의 증가하는 부분수열의 최대길이인 dp[3]이 2라고 하고

arr[4]가 arr[3]의 값보다 크지 않다면 dp[4]는 2가 될것이다.

위의 조건과 예시를 종합해 조건식을 만들자면 아래와 같은 식이 나온다.

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

for(int j = 1; j < i; j++}{

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

}

}

하지만 빠진 조건이 하나 존재한다. 우리는 부분수열의 최대길이를 구해야하지만  위의 식대로 프로그램을 돌리면 위의 조건문을 만족하는 i 와 가장 가까운 j 의 부분수열의 최대길이가 dp[i]에 대입되기 때문에 아래 예시와 같은 예외의 경우가 나타나게 된다.

ex) 

2    3    4    1    5

    dp[i]    1    2    3    1    ? <<-- dp[5]는 4가 되어야 하지만 dp[5] = dp[4] + 1; 로 인해 2가 되어 버릴 것이다. 그래서 아래와 같은 조건 하나를 추가한다.

if(dp[i] < dp[j] + 1) dp[i] = dp[j] +1;

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

풀이

붕어빵이 N개 있다고 가정하자. 1개 팔 때의 가격(arr[1]), 2개 팔 때의 가격(arr[2]), .... N개 팔 때의 가격(arr[n])이 있을 것이다. N개의 붕어빵을 모두 팔 때 얻을 수 있는 최대 수익을 구해야 한다.

먼저 dp[1]은 N개의 붕어빵 중에 1개를 팔때 얻을 수 있는 최대 이익을 담는다고 하자.

그러면 dp[0] = 0; ,

 dp[1] = arr[1]; 이라고 할 수 있다.

다음으로 N개 중 2개의 붕어빵을 팔때 얻을 수 있는 최대 이익은

dp[2] = dp[1] + arr[1] or dp[0] + arr[2] 이다.

3개의 붕어빵을 팔때 얻을 수 있는 최대 이익은

dp[3] = dp[2] + arr[1] or dp[0] + arr[3] or dp[1] + arr[2] 이다.

4개의 붕어빵을 팔때 얻을 수 있는 최대 이익은

dp[4] = dp[3] + arr[1] or dp[0] + arr[4] or dp[2] + arr[2] or dp[1] + arr[3] 이다. 

dp[i] = max(dp[i-j] + arr[j]); 로 나타낼 수 있다.