1. 문제를 올바른 순서로 이해한다. 키보드에 손이 늦게 올라간다.

• 문제 읽기 : 시간,메모리 제한 파악 / 문제 전체를 꼼꼼히 !
• 이해하기 : 제공되는 정보(변수들) 정리 / 예제 데이터에 대해 이해한건지 손으로 테스트해본다.
• 파악하기 : 가능한 최대, 최소 정답에 맞는 데이터를 직접 생성 / 키워드가 되는 단어들을 체크

2. 시간과 공간 복잡도를 계산한다.
3. 코드를 효율적으로 함수화해서 구현한다.

• 코드가 길어질수록 실수할 수 있는 구멍이 많아진다.

4. 코딩 테스트에서 부분 점수를 챙긴다.

접근 순서

1. 완전 탐색 접근

완전 탐색 접근을 통해서 모든 경우를 직접 하나하나 찾아내 보기.
일반적으로 N이 커질수록 탐색해야 하는 경우가 엄청 많아진다.

2. 풀고 싶은 가짜 문제 정의

1) 진짜 문제를 먼저 써보자.
진짜 문제 : 주어진 N에 대해서 2 X N 경우의 수
가짜 문제 : N을 i 로 바꿔서 2 X i 경우의 수
Tip) 테이블을 하나 만들어서 , Dy(동적프로그래밍의 가짜문제 i 번째 값을 저장) 배열을 가득 채울 수만 있다면 문제를 풀수 있는지 확인한다.

2) 가짜 문제를 풀면 진짜 문제를 풀 수 있는가? 에 대해 확인하자.
Dy 배열을 가득 채울 수만 있다면? 진짜 문제에 대한 대답은 Dy[N] 이다.

3) 초기값은 어떻게 되는가?
초기값 : 쪼개지 않아도 풀 수 있는 "작은 문제" 들에 대한 정답
일반적으로 i 가 1 , 2 , 3 , 4

4) 점화식 구해내기

• Dy[i] 계산에 필요한 탐색 경우를 공통점끼리 묶어 내기. ( 마지막이 1, 마지막이 2, 마지막이 3 이런 경우처럼 공통화를 시키기 , BOJ 9095 문제)
  • i 를 하나 정해서, 손으로 다 그려보는 방법
  • 마지막에 뭐가 있는지를 먼저 보는게 쉬운 접근
• 묶어낸 부분의 정답을 Dy 배열을 이용해서 빠르게 계산해보기

3. 구현

static void pro() {
	Dy = new int[N + 1];
    // 초기값 구하기
    /* TODO */
    
    // 점화식을 토대로 Dy 배열 채우기
    /* TODO */
    
    System.out.println(Dy[N]);
}

연습문제 : 1003 , 10870 , 15988 , 15991 , 11052 , 2011