1. 동적 프로그래밍

문제의 크기를 변화해가면서 작은 문제의 결과를 이용해 큰 문제를 빠르게 계산하는 알고리즘

• 먼저 완전 탐색(brute force)를 시도해 본 후 탐색되는 경우가 매우 많아 시간초과가 날 경우 DP를 시도해 볼 수 있음
• 규격화된 방법을 외워서 연습할 것
• 구현 코드 자체는 매우 간단하지만 작은 문제를 만들고 점화식을 만드는 것이 어려움

2. 동작 과정

1. 가짜 문제 정의
   • 유형
   1. Dy[i]
      • 1~i번 원소에 대해 조건을 만족하는 경우의 수
   2. Dy[i][j]
      • i~j번 원소에 대해 조건을 만족하는 경우의 수
   3. 문제 크기 N과 마지막 상태를 함께 기록하기
      • Dy[i][0]
      • Dy[i][1]
2. 가짜 문제를 풀면 진짜 문제를 풀 수 있는지 확인
   • Dy[i] → Dy[N]
3. 초기값 설정
   • 작은 문제로 나누지 않아도 손으로 풀 수 있는 값
4. 점화식 작성
   • 점화식을 작성하는게 가장 중요!
   • 공통점을 찾아서 묶어야 함 (Partitioning)
     • 보통 마지막에 무엇으로 끝나는지를 기준으로 묶을 수 있음
   • 묶어낸 작은 문제들의 합으로 큰 문제를 푸는 식으로 점화식 작성
5. 진짜 문제 풀기

❗ 위 5과정 중 하나라도 안 될 경우 1번으로 다시 돌아가서 가짜 문제 정의부터 다시 시작해야 함

3. 핵심 코드

static void process() {
        // 초기값 구하기

        // 점화식 작성

        System.out.println(Dy[N]);
    }