다른 분류에 비해 유독 DP를 어려워했는데... 집중적으로 풀면서 좀 느낀점들이 있어서 정리해봤음

아직 실골 풀고 있는 피린이임

  • 1. 기준을 정하고, 규칙을 찾기

    • 기준: 자리수, 끝자리 숫자 등
    • 규칙 찾기: 표 작성, 도식화 등
  • 2. 여러가지 유형을 익히기
    • 가능한 모든 경우들을 갱신하는 1차원 dp 유형
    • 직전 선택지에 영향을 받는 2차원 dp 유형
    • 진행방향을 역으로 생각하는 2차원 dp 유형
    • 경로의 개수를 계산하는 2차원 dp 유형
    • dp 배열의 정의가 특이한 유형
    • dp 값이 직접 정답이 아닌 유형
    • 등등
나는 특히 유형화 하는게 도움이 됐던거 같음
이미 풀어본 유형에서 약간 응용하는 경우는 거의 쉽게 풀리더라고

하지만 아직 안 풀어본 유형은 손도 못대는 경우가 많은데... 이건 많이 풀다보면 늘겠지? 


골드쪽 올라가면 구간 쪼개기 유형이라든가 (ex. 11066 파일 합치기)

배낭 문제에서 기존의 x, y축과 dp값의 의미를 반대로 잡고 풀기라던가 (ex. 7579 앱)

한번씩은 풀어봐야 깨닫게 되는 것들이 많은거 같음


DP 공포증에서 벗어나고 싶다 ㅋㅋ