DP 풀이 팁!

1. 규칙성 찾기

규칙성은 우리가 일반적으로 생각하는 규칙성이 아니다. 상식적으로 구분해보지 않았던 규칙성이 나타날 수도 있다.

물론 점화식을 찾는 건 맞지만 수학적으로 생각하는 방법 + 프로그래밍적으로 생각하는 방법이 모두 필요하다.

 

2. dp 테이블 초기화

dp 테이블은 어떤 방식으로도 초기화 될 수 있다.

모두 0 으로 ,모두 1로,  입력받는 숫자 그대로도 그대로 가능하니, 이런 점들에 유의하자.

dp 테이블은 1차원, 혹은 2차원, 3차원으로도 모두 구현이 가능하다. 그러니 이런 부분들을 유의하면서 풀어보자 

 

3. 변화를 감지, 변화를 기록하는 방법

어느 지점에서 변화가 일어나는 지 파악한다. 그리고 단계마다 그 지점에서 최선의 비교가 되는 상태인 지 살펴봐야 한다.(냅색에서 특히 중요)

그리고 그 변화를 어떻게 표현해야 할 지 고민하는 과정이 필요하다.

 

4. 단계별 최적값 찾기

목표는 최종 결과일지라도 단계별로 최적의 값이 어떻게 발생하는 지 따져봐야 한다. 규칙성을 파악하기 용이하다.

적어도 값 세개까지는 규칙이 있을 것이라고 생각하자. 제한적인 연속값이 있는 경우, dp값 뿐만 아니라 일부러 주어진 값을 넣어서 값을 비교해야 하는 것도 팁!

 

5. 노가다

뭐든 직접 해보고 써야한다. 테스트 케이스가 주어지는 이유도 노가다를 통해 규칙성을 파악하라는 의미