푼 dp 유형 정리

1. 초급 DP

 

* 1 2 3 더하기

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

 

- 간단하게 첫번째 두번째 세번째 경우의 수만 구하면 규칙이 보이는 문제.

- 여기서 dp는 점화식을 세우기 전에 초기값을 먼저 할당하고 점화식을 세우는게 중요하다고 느낌

 

* 1로 만들기

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

 

* 계단 오르기

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

 

* 포도주 시식

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

 

- 둘다 3번연속 선택 못 한다는 조건이 존재

- 3개의 초기값을 설정 후에 점화식을 세워야함

- 계단 오르기는 마지막 계단은 꼭 밟아야 하기때문에 점화식을 세울때 현재 밟고 있는 계단은 꼭 값으로 포함시켜 줘야함

- 포도주 시식은 문제에 언급은 없지만 포함안시켜도 가능. 

- 포도주 시식의 점화식이 조금 더 길다.

 

2. 중급 DP

 

* LIS ( Longest Increament Sequence ) 최장 증가 수열

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

 

- 배열이 주어지고 그 중에 가장긴 증가 수열을 찾는 문제

- dp 배열을 1로 초기화 하고 증가 수열 발견 할때마다 값을 갱신시킴

 

* 연속 합

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

 

- 배열이 주어지고 그 중에 가장 큰 연속 합을 찾는 문제

- dp 배열로 초기값을 할당

- dp 배열의 i-1 값과 현재값을 비교하여 큰 값을 dp 배열에 할당

 

* 최대 부분 수열

https://songkc5671.tistory.com/62

최대 부분 수열

- 배열이 주어지고 2개의 K길이의 합중 최대값 반환.

- SlidingWindow로 값을 저장 후 중복되지 않는 범위에서 최댓값 반환.

 

* 카드 구매하기

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

 

- 첫번째부터 1개의 카드팩을 구매하는데 발생하는 비용, 2개의 카드팩을 구매하는데 발생하는 비용...

- 출력값을 N번째의 카드팩을 구매할때 지불해야하는 최대금액(최댓값) 출력하면 된다

- 배낭문제와 비슷하게 현재 카드팩 수량을 빼고 금액을 갱신해주면 된다

 

* 평범한 배낭문제

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

 

- 가방의 물품의 수와 버틸 수 있는 무게가 주어진다.

- 물품의 무게와 가치가 차례로 주어지는데 획득 할 수 있는 최대 가치를 출력하면 된다

- 위의 카드 구매하기 문제에서 '무게' 변수만 추가한 버전이라고 생각하면 된다

- 카드 문제에서는 카드팩 수량을 빼고 금액을 갱신했지만

배낭 문제에서는 무게를 빼고 가치를 갱신하면 된다.

 

정리

LIS : 증가하는 수열의 최대 길이를 찾는 문제

연속합 : 연속한 수열중에 최댓값을 반환하는 문제

최대 부분 수열 : dp 보다는 투 포인터를 사용해서 최댓값을 구하는 문제

카드 구매하기 : i 번째까지 고려했을때 획득 가능한 최댓값 반환하는 문제

평번한 배낭문제 : i 번째까지 고려했을때 획득 가능한 최댓값 반환하는 문제

+ 무게까지 고려해야해서 dp[][] 이차원 배열을 사용해야함