BackTracking 2

1) DP 메모이제이션
- 정의
- 노드 탐색시, Dp 값을 미리 구해놓은 값이 있으면 탐색하지 않고 해당 값을 이용하여 탐색의 수를 줄인다.
○ 가지치기 차이
§ ans 갱신을 하지 않고도, 노드 리턴할 수 있음.

1-1) 상향식 백트랙킹 메모이제이션
- 루트 노드에서 현재 노드까지 누적된 파라메터의 정답 값을 메모이제이션 하는 경우.
§ 가지치기 식으로 사용
○ 정답갱신을 리프노드에서 하기 때문에 자식 노드들의 값을 비교할 수 없음.
- 구현 방식
○

- 최적화 종류
○ 가지치기
§ 최소값 가지치기
§ 정답에 가까운 답을 빨리 찾을수록 가지치기 효율 좋음.
○ 상향식 DP 메모이제이션
§ 현재 함수까지 누적된 파라메터 값만 사용하여 앞으로 탐색을 할지 말지를 결정 (중간값)
□ Dp[i][j] = 구하려는 값
§ 리프노드에서 정답을 갱신하기 때문에, 자식노드들의 결과값을 비교하는 것이 불가능
§ DP 종류? 예제
□ DP 점화식
® 함수의 파라메터를 사용하여 dp 파라메터를 결정.
◊ DP의 파라메터가 너무 많으면 효율성이 떨어진다.
◊ DP의 파라메터가 너무 적으면 유망한 노드를 리턴하는 경우 발생
- (정답갱신 못하는 경우 발생) 
® 가지치기로 사용됨
◊ Dp 값이 0이 아니면 리턴
◊ 현재 파라메터의 값과 dp값과 비교해서 작거나 큰 경우 리턴.
□ 코드
dp[i][j] = 물건의 index 까지 고려했을때, j 값을 만들수 있으면 0 또는 1
® Dp[i][j] = 구하려는 값.
void DFS(int index, int weight) {
if (index == N) {
…..
return;
}
if (dp[index][weight] == 1) return; // 부모 노드 진입시 리턴,
dp[index][weight] = 1; // dp 값 세팅

DFS(index + 1, weight + S[index]);
DFS(index + 1, weight);
}
□ 그래프
® 내려갈수록 

§ DP 점화식을 최적화 하자
□ 유망한 노드를 리턴하지 않고, 효율성을 최대로 하자
□ Dp 파라메터의 후보는 함수의 파라메터
□ 효율성 높히기
® Dp 파라메터를 사이즈가 작은걸로 교체하자.
® Dp 차원 줄이자.
◊ 2차원 DP를 1차원 DP로 만들어보자.
◊ Dp[i][j] = i번 물건까지 고려했을때, j 무게를 만들수 있으면 1, 0
◊ DP 테이블 크기를 1차원으로 줄이면 효율성이 더 좋지만, 유망한 노드를 리턴하게 된다.
} Dp[i]= i 무게를 만들수 있으면 1, 0
} 예를들어 인덱스가 다르고 동일한 무게를 만들수 있다고 가정시, 하위노드의 결과값이 동일해야 한다.
} 위 그래프의 2번과 4번을 보면
– 2번은 2번 물건까지 고려하고 3무게를 만들수 있고
– 4번은 3번 물건까지 고려하고 3무게를 만들수 있다.
– 1차원 dp 사용하게 되면 위 둘중 하나는 중복처리가 되어
– 2번은 다음 스텝인 3번 물건을 고려하는 경우 6의 무게를 만들수 있지만, 4번은 6의 무게를 만들수 없다.
– 그렇기 때문에 유망한 노드를 리턴하게 되어, 1차원 dp가 불가능하다.


§ 예제
□ 정류장 문제 가지치기 -> 상향식 메모이제이션 으로 변환하자.

dp[i][j] = i 번째 충전지까지 고려, 남은 잔량 j일때 충전지 교환횟수
- 코드

int dp[1001][100];
void dfs(int index, int cnt, int sm) {
  if (index == N) {
    ans = min(ans, cnt);
    return;
  }
  if (dp[index][cnt] != INF && dp[index][sm] <= cnt) return;
  dp[index][sm] = cnt;

  dfs(index+1, cnt + 1, arr[index] - 1); // 교체하는 경우
  if (sm > 0) dfs(index+1, cnt, sm - 1); // 교체하지 않는 경우
}

1-2) 하양식 백트랙킹 메모이제이션
현재 노드에서 리프노드까지 리턴되는 값을 계산하여  메모이제이션 하는 경우.
○ Dp[i][j] = 구하려는 값.
- 구현 방식
○ 자식노드 탐색 후 Dp 세팅을 하고, 노드 진입시에 리턴한다.
§ 정답 갱신 범위는 부모의 자식노드들.
§ 2번 부모노드는(보라색) 4, 5노드들의 정답갱신
§ 3번 부모노드는(보라색) 6, 7노드들의 정답갱신
§ 1번 부모노드는(보라색) 2번 3번 노드들의 정답 갱신
○ 1번 노드를 제일먼저 호출하지만, 1번 노드 모든 자식노드를 탐색 후 제일 마지막 정답갱신 (하양식)

- 최적화 종류
a. 비트마스킹 메모이제이션
§ 사용 할때
□ 순열 복잡도이며, 조합문제로 가능한 문제인 경우.
§ 복잡도
□ N <= 25, 순열을 조합의 복잡도로 바꾸어 준다.
§ 점화식
□ dp 파라메터 중 하나를 비트마스킹(mem) 값으로 사용해야 한다.
□ 예제
◊ dp[i] = 조합의 비트마스킹 값이 i일때, 최소 또는 최대 또는 개수 
◊ dp[i][j] = i 인덱서의 물건까지 고려했을대, 비트마스킹 값이 j인 경우 , 최소 또는 최대 개수
§ 비트마스킹 의미
□ 0001 : 1번째 아이템만 선택
□ 0101 : 1, 3 번째 아이템 만 선택
§ 코드

 int dp[1 << 20];
int DFS(int index, int kal, int mem) {
    if (index == N) return 0;
    if (dp[mem] > 0) return dp[mem]; // 부모노드 진입부분에서 dp 리턴.

    int taste = 0;
    if (kal + K[index] <= L) 
   taste = DFS(index + 1, kal + K[index], mem + (1 << index)) + T[index];
    taste = max(taste, DFS(index + 1, kal, mem));

    dp[mem] = max(dp[mem], taste);  // 자식 노드 탐색 후 dp 세팅
    return dp[mem];
}

○ 점화식 dp 메모이제이션
§ 현재 노드에서 리프노드까지의 값을 전부 반영하여 dp로 저장하고 메모이제이션.
§ 복잡도
□ N <= ??? 1000 ??
◊ 효율성 점검을 통해 복잡도 다시 계산 필요..
§ 점화식
□ 함수의 파라메터를 사용하여 dp 파라메터를 결정.
◊ 함수의 파라메터가 너무 많으면 효율성이 떨어진다.
◊ 함수의 파라메터가 너무 적으면 유망한 노드를 자르는 경우 발생. (정답갱신 못하는 경우 발생) 
□ 이미 방문한 노드에서 구한 값을 재방문 없이 재사용!
□ 효율성 확인.
◊ 한번만 방문했을때 리턴 (dp > 0)하는 경우, 효율성 매우 높음 O(N)
◊ 상향식 보다 부모노드에서 리턴될 가능성 높음
◊ 여러 번 방문이 되는 경우, 중복이 얼만큼 되느냐에 따라 복잡도가 달라진다.
◊ 그래프
□ Ex) dp[i][j] = i, j 에서 N, M까지 갈수있는 경로의 모든 개수
§ 메모이제이션 방법
□ 부모노드 진입 부분에서 dp 리턴.
□ 자식 노드 탐색 후 dp 세팅
§ 종료조건
□ 조건에 따라 리턴 값을 다르게 하는 경우 있음.
§ 코드

int DFS(int y, int x) {
If (dp[y][x] > 0) return dp[y][x] // 부모노드 진입부분에서 dp 리턴.
If (종료조건) { return 0; }
for (int i = 0; i < 4; i++) {
…..
k += DFS(ny, nx);
}
dp[y][x] = k // 자식 노드 탐색 후 dp 갱신.
return dp[y][x]; 
}

§ 그래프
§

1-3) 상향식에서 하양식 변경하는 방법
- 구하려는 값을 파라메터에서 빼고 리턴받는 식으로 변경
- 재귀 함수 뒤에 선택한 물건의 값을 연산.
- Child 노드의 모든 값들을 비교 하여 최종연산을 하고 값을 리턴함.
- 종료 조건은 보통 0을 리턴. But 응용이 가능.

1-4) DP 효율성 검증.
- 그래프 또는 2차원 표 그려보기
- 코드로 점검
○ N을 최대 제한으로 늘리고, input 값 추가.
○ 코드에서 complex 값을 찍어보기 (메모이제이션 전/후)

int complex = 0;
void DFS(int index, int weight) {
if (index == N) {
complex++;
return;
}
if (dp[index][weight] == 1) return;
dp[index][weight] = 1;

DFS(index + 1, abs(weight - S[index]));
…..
cout << complex << endl;
}

- 실제로 풀어본 문제들 중에 해보자.


2) 문제 풀이 방법
a. 문제 정의
a. 문제 정의
1) 직원들의 키를 선택/선택X (조합)하여 만들수있는 M을 만들때, 최소 직원의 수
i. 조합/순열, 2진, 멀티플을 확인
ii. 1번 토대로 문제의 그래프를 그려 보기
b. 문제의 복잡도를 계산한다. 
i. 2의N승, 3의N승…. 
c. 메모이제이션 고려
i. 상향식 메모이제이션
1) 루트 노드에서 현재 노드까지 누적된 파라메터의 정답 값을 메모이제이션 하는 경우.
ii. 하양식 메모이제이션
1) 현재 노드에서 리프노드까지 리턴되는 값을 계산하여 여 메모이제이션 하는 경우.
1) Dp 메모이제이션
2) 비트마스킹 메모이제이션
iii. 점화식 설정
§ dp[i][j] = 구하려는 값
§ 함수의 파라메터를 사용하여 dp 파라메터를 결정.
□ 함수의 파라메터가 너무 많으면 효율성이 떨어진다.
□ 함수의 파라메터가 너무 적으면 유망한 노드 자르는 경우 발생.
iv. 효율성 검증
1) 그래프 그려보기
1) 하양식
® 이전 방문한 노드인 경우 리턴 (dp > 0) 효율성 높음 O(N)
2) 상향식
® 이전 방문한 노드인 경우 리턴.
® 현재 dp 값과 파라메터의 값과 비교해서 작거나 큰 경우 리턴.
d. 탐색 방법을 설계한다.
i. Tip
1) 상향식으로 먼저 구현 후 하양식으로 변경 후 메모이제이션 적용

DFS(int index, int cnt) {
   DFS(index + 1, cnt + 1);
   DFS(index + 1, cnt);
}

e. 코드로 효율성 검증.
i. Complex 출력


1. 저울 (N = 30)
https://www.acmicpc.net/problem/2629

a. 문제 정의
a. 문제 정의
1) 추를 왼쪽에 넣거나, 놓지 않거나, 오른쪽에 놓았을때, 주어진 추의 무게를 만들수 있는가 ?
i. 조합 - 3진 트리
ii. 그래프 (3진트리)
b. 문제의 복잡도를 계산한다. 
i. 3의 N승 인데, 3의 30 승

c. 최적화 기법을 선택을 고려한다.
i. 상향식 메모이제이션
1) 현재노드까지 누적된 파라메터(측정가능한 무게)와 dp 값만 비교하여 메모이제이션 하는 경우
ii. 점화식 설정.
1) Index 파라메터를 빼면 유망한 노드 잘림.
2) Dp[i][j] = i번째까지 추를 고려하고, j 무게를 측정할수 있으면 1, 아니면 0
d. 탐색 방법을 설계한다.

e. 코드로 효율성 검증하자.
i. Input (N = 30)
30
2 3 3 3 5 2 3 3 3 5 2 3 3 3 5 2 3 3 3 5 2 3 3 3 5 2 3 3 3 5
3
1 4 10
ii. Complex : 273

DFS(index + 1, weight + w[idx]);
DFS(index + 1, abs(weight - w[idx]));
DFS(index + 1, weight); 

void DFS(int index, int weight) {
if (index == N) {
if (weight >= 0 && weight <= MAXV) {
visit[weight] = 1;
}
return;
}
if (dp[index][weight] == 1) return;
dp[index][weight] = 1;

DFS(index + 1, abs(weight - S[index]));
if (weight + S[index] <= MAXV) DFS(index + 1, weight + S[index]);
DFS(index + 1, weight);

그래프 그려보자
4
2 3 3 3
3
1 4 10

   | 1 0 0 0 0 0 0 0 0 0 0
2 | 1 0 1 0 0 0 0 0 0 0 0
3 | 1 1 1 1 0 1 0 0 0 0 0
3 | 1 1 1 1 1 1 1 0 1 0 0
3 | 1 1 1 1 1 1 1 1 1 1 0


상향식 -> 하양식 -> 메모이제이션 연습

1) 5215 햄버거 다이어트 (N = 20) ( 상향식, 하양식, 냅색 가능 )
햄버거 재료의 수, 제한 칼로리가 주어졌을때, 재료를 선택해서 가장 맛이 좋은 햄버거 점수를 출력
재료는 칼로리와 맛이 입력으로 주어진다.
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWT-lPB6dHUDFAVT

상향식 백트랙킹 (복잡도 : 2의 20승)
- 리프노드에서 정답 갱신

void DFS(int index, int score, int kal) {
    if (index == N) {
        ans = max(ans, score);
        return;
    }
    if (kal + K[index] <= L) DFS(index + 1, score + T[index], kal + K[index]);
    DFS(index + 1, score, kal);
}

하양식 백트랙킹
1) 구하려는 score 점수를 파라메터에서 빼고 리턴받는 식으로 변경한다.
2) score 점수를 DFS () + score 형태로 변경한다.
3) child의 모든 값들을 합산을 한 뒤, 최종 연산을 하고 해당 값을 리턴한다.
4) 종료조건에서 리턴하는 값은 보통 0

- 리프노드에서는 이전 노드에서 점수가 더해졌기 때문에 0을 리턴.

int DFS(int index, int kal) {
    if (index == N) return 0;    
    int taste = 0;
    if (kal + K[index] <= L) taste = DFS(index + 1, kal + K[index]) + T[index];
    taste = max(taste, DFS(index + 1, kal, mem));
    return taste;
}

하양식 백트랙킹 + 비트마스킹 메모이제이션 
1) N <= 25 인 경우 + 순열 조건에 해당되면 비트마스킹 메모이제이션을 적용할 수 있다. 
2) 효과 : 순열 (n!) --> 조합 (2의 n승)
3) 비트마스킹 인덱스의 의미는 현재 선택된 항목들, 배열값은 구하려는 값 (리턴 값)
- DP[비트마스킹 값] = 구하려는 값
- DP[비트마스킹 값] = 최대 맛.
- Ex) DP[5] = 10; // 이진수 0101, 첫번째와 세번째 항목을 선택할때, score = 10
4) dp 1차원 또는 2차원 ??
5) 위 문제에선 비트마스킹 메모이제이션 효과 없음 why? 

int dp[1 << 20];
int DFS(int index, int kal, int mem) {
    if (index == N) return 0;
    if (dp[mem] > 0) return dp[mem]; // dp 활용 (메모이제이션)
    int taste = 0;
    if (kal + K[index] <= L) 
   taste = DFS(index + 1, kal + K[index], mem + (1 << index)) + T[index]; // 메모이제이션 비트 갱신 (물건 추가)
    taste = max(taste, DFS(index + 1, kal, mem));
    dp[mem] = max(dp[mem], taste);  // 값을 저장
    return dp[mem];
}

하양식 백트랙킹 + 커스텀 메모이제이션

2) 1865 동철이의 일분배 (N = 16) 2의 16승 복잡도
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LuHfqDz8DFAXc
직원의 일을 조합한 모든 경우에 있어서, 주어진 일이 모두 성공한 확률 구하는 문제
복잡도
- 순열 문제 복잡도 16!
- N <= 25 인 경우 + 순열 조건에 해당되면 비트마스킹 dp 메모이제이션 적용할 수 있다. 
- 순열 메모제이션 적용하여 조합의 복잡도를 가지게 해줌.
점화식
- Index를 첫번째 파라메터에 추가 ?? X
○ 주어진 일이 모두 성공하는 것만 고려하고, 누가 그 일을 하는지는 상관없음.
- Dp[주어진 일의 조합 ( 비트마스크 값 )] = 성공할 확률

상향식 백트랙킹 (복잡도 : 16!)
- 상향식 백트랙킹 가지치기 복잡도 : 2843

void DFS(int index, float sum) {
if (index == N) {
ans = max(ans, sum * 100);
return;
}
for (int i = 0; i < N; i++) {
if (visit[i] == 1) continue;
visit[i] = 1;
DFS(index + 1, sum * work[index][i] * 0.01f);
visit[i] = 0;
}
}

하양식 백트랙킹
- DO

하양식 백트랙킹 메모이제이션
- 복잡도 계산 : 900

double DFS(int index, int mem) {
    if (index == N) return 1;
    if (dp[mem] > 0) return dp[mem];
    for (int i = 0; i < N; i++) {
        if (P[index][i] == 0) continue;
        if ((mem & (1 << i)) != 0) continue;  // visit 배열로 가능.
        dp[mem] = max(dp[mem], DFS(index + 1, mem + (1 << i)) * P[index][i] * 0.01);
    }
    return dp[mem];
}

문제풀이

3)  1520 내리막길
https://www.acmicpc.net/problem/1520

f. 문제 정의
a. 문제 정의
1) 1, 1에서 시작해서 N, M까지 가는 경로의 개수를 구하여라
i. 멀티플을 확인
ii. 그래프로 그리기 어려움. (표에서 직접 경우의 수를 그려본다.)
g. 문제의 복잡도를 계산한다. 
i. 4의 N승 인데처럼 보이지만, 현재 위치에서 오르막 위치에 오를수 없음.
ii. 한번 탐색한 경로는 다시 탐색 안해도됨.
1) 500 * 500 <= 250,000
h. 최적화 기법을 선택을 고려한다.
i. Dp[y][x] = y,x 에서 N, M까지 가는 모든 경로의 개수
ii. 하양식 메모이제이션
1) 현재 노드에서 뻗어나가는 리프노드까지의 모든 경로의 개수를 구해야 한다.
i. 탐색 방법을 설계한다.

int DFS(int y, int x) {
if (dp[y][x] != -1) return dp[y][x]; // 리턴하는 부분
d[y][x] = 0;

for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (s[ny][nx] <= s[y][x]) continue;
dp[y][x] += DFS(ny, nx);
}
// dp값 세팅하는 부분
return d[y][x];
}

- 효율성 검증

하향식 dp 메모이제이션 동작방식

1) 1번 경로로 한번 탐색을 했음. (50 -> 35 -> 30 -> 27 -> 24 -> 22 -> 15 -> 10)
2) 2번 경로 탐색 하던 중 1번 경로에 이미 탐색한 노드 22를 만남 (30 -> 25 -> 22)
- 원래대로라면 30 -> 25 -> 22 -> 15 -> 10
3) 22번 노드에서는 갈수있는 경로는 1개로 이미 알고 있음.
4) 22번 노드에서 더 이상 탐색하지 않고 경로 1을 리턴한다.
- 1번 탐색시, 22번 노드에서 dp[4][3] = 1을 미리 저장해 놔야 한다.

Mission )
리턴되는 상황이 언제인지 말해봐라.
리턴 될때 가지치기 되는 부분을 말해봐라
(동 서 남 북 으로 갱신할때 dp 테이블을 작성해라)

리턴되는 상황은 3번째 탐색 (보라색) (4열 3칸) 22->15로 도착하면, 1을 리턴한다.
리턴되는 상황은 4번째 탐색 (노랑색) (2열 4칸) 25->20 로 도착하면, 1을 리턴한다.

dp[y][x] = y,x 위치에서 N,N까지 갈수있는 경로의 수
dp[y][x] 값이 0보다 크면, y, x에서 n,n까지 모든 경로의 수가 이미 계산이 되어 있기 때문에 dp값을 리턴한다.


4) 1861. 정사각형 방
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5LtJYKDzsDFAXc

j. 문제 정의
a. 문제 정의
1) 모든 경로에서 이동할수 있는 방의 개수를 구한다.( 현재 방에 적힌 수보다 1큰 방만 가능)
2) 최대 이동가능 한 방의 개수와 시작지점을 구해라.
i. 멀티플을 확인
ii. 그래프로 그리기 어려움. (표에서 직접 경우의 수를 그려본다.)
k. 문제의 복잡도를 계산한다. 
i. 4의 N승 처럼 보이지만, 현재방보다 1큰 방은 하나의 경로만 가능.
ii. 1000 * 1000  <= 백만 보다 작음.
l. 최적화 기법을 선택을 고려한다.
i. Dp[y][x] = y,x 에서 시작해서 이동할수 있는 방의 개수
1) DP 파라메터 생각 못하겠으면, 함수의 파라메터 중 넣어보자.
ii. 하양식 메모이제이션
1) 현재 노드에서 뻗어나가는 리프노드까지의 이동할수 있는 방의 개수를 구해야 한다.
m. 탐색 방법을 설계한다.

for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
if (dp[i][j] == 0) {
dp[i][j] = DFS(i, j);
l.push_back(make_pair(s[i][j], dp[i][j]));

int DFS(int y, int x) {
if (dp[y][x] > 0) return dp[y][x];
for (int i = 0; i < 4; i++) {
int ny = y + dy[i];
int nx = x + dx[i];
if (s[y][x] + 1 != s[ny][nx]) continue;
dp[y][x] =  DFS(ny, nx) + 1;
}
return dp[y][x];
}

- Mission)
- 예제 2번으로 해보자.
- Dp[y][x] = y,x 에서 시작해서 이동할수 있는 방의 개수
- DP 메모이제이션이 되는 좌표와, 어느 좌표 탐색으로 인하여 메모이제이션 되었는지 체크.
○ 3번방, 7번방 두개가 dp 테이블 set
-

5) 9092 마라톤 ( N = 500 )
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AW7Opy-KWPoDFAWY

 

n. 문제 정의
a. 문제 정의
1) 체크포인트를 방문하거나, 건너 뛰는 경우 (반드시 K번 건너뛰어야 함) N번 체크포인트에 도착했을때 최소 거리.
i. 조합 - 2진 트리
ii. 그래프로 그리기 어려움. (표에서 직접 경우의 수를 그려본다.)
o. 문제의 복잡도를 계산한다. 
i. K의 N승 처럼 보이지만 K가 계속 줄어듬.
ii.

iii. 가능한 이유
1) N 체크포인트에 도착하지 않는 경우는 없음.
2) 일자라서 경로 중복이 무지하게 많이 된다. 그만큼 dp 활용도 높음.

p. 최적화 기법을 선택을 고려한다.
i. Dp[i][[j] = i 번인덱스에서 건너뛴 개수가 j일때, 마지막 체크포인트까지 최소 거리
ii. 최소거리는 한번만 계산하면 다시 계산할 필요 없음.
iii. 하양식 메모이제이션
1) 현재 노드에서 리프노드까지 최소 거리를 알아야 함.
q. 탐색 방법을 설계한다.
• int DFS(int index, int cnt) {
    if (index == N - 1) return 0;
    if (dp[index][cnt] != MAX_DIST) return dp[index][cnt];
    int dist = 0;
    for (int i = 0; i <= cnt; i++) {
        int nextIndex = index + i + 1;
        if (nextIndex >= N) continue;
        int distance = GetDist(index, nextIndex);
        int nextDistance = DFS(nextIndex, cnt - i);
        dp[index][cnt] = min(dp[index][cnt], nextDistance + distance);
    }
    return dp[index][cnt];
}


이해를 돕기위한 
- dp[현재인덱스][점프cnt] = 현재 인덱스에서 목적지 까지의 최소거리
• 실제 거리구하는 공식은 아니고 이해를 돕기 위해 거리를 칸수로 지정.
• 실제 복잡도
○ N = 10, K = 10 이라고 가정
○ (N * (N - 1)) / 2 
○ 500 * 499 / 2 = 124,750 
○ 점프 cnt로 인하여 K를 곱해도 1억 이하긴 함.

1) 10번 인덱스는 도착지 dp[10][0] = 0
2) (검정) 9번 인덱스에서 10번 접근. dp[9][1] = 1
3) (파랑) 8번 인덱스에서 9번 접근. dp[8][1] = 1 + 1 ( 재사용 )
4) (파랑) 8번 인덱스에서 10번 접근 dp[8][2] = 2
5) (빨강 ) 7번 인덱스에서 8번 접근. Dp[7][1] = 1 + 2 (3번 재사용)
6) (빨강 ) 7번 인덱스에서 9번 접근 DP[7][2] = 2 + 1 ( 1번 재사용)
7) (빨강 ) 7번 인덱스에서 10번 접근 Dp[7][3] = 3 (재사용)