DP

여러 개의 하위 문제를 먼저 푼 후 그 결과를 쌓아올려 주어진 문제를 해결하는 알고리즘.

DP 푸는 과정

1. 테이블 정의하기
2. 점화식 찾기
3. 초기값 정하기

백준

예제1

https://www.acmicpc.net/problem/1463

정수 x에 사용할 수 있는 연산은 다음과 같이 3가지 이다.

1. x가 3으로 나눠떨어지면, 3으로 나눈다.
2. x가 2로 나눠떨어지면, 2로 나눈다.
3. 1을 뺀다.

정수 n이 주어졌을때, 위와 같은 3가지 연산을 사용해 1을 만드려고 함.
연산을 사용하는 횟수의 최솟값?

풀이

1. 테이블 정의하기

D[i] = i를 1로 만들기 위해 필요한 연산 사용 횟수 최솟값

2. 점화식 찾기

D[12] = ?

• 3으로 나누거나: D[12] = D[4] +1
• 2로 나누거나: D[12] = D[6] +1
• 1을 빼거나: D[12] = D[11] +1

위 3가지 경우의 최솟값을 구해주면 된다.

D[12] = min(D[4]+1, D[6]+1, D[11]+1)

이를 일반화 해서 점화식을 구해보면,

D[k] = min(D[k/3]+1, D[k/2]+1, D[k-1]+1)

을 도출할 수 있다.

3. 초기값 설정

피보나치 수열에서 초항, 둘째항이 각각 1, 1인 것처럼 점화식에는 당연히 초기값이 있어야 함.
이 문제에선 D[1]=0 을 초기값으로 주면, 나머지는 점화식을 가지고 값을 구할 수 있음.
문제마다 점화식이 돌아갈 수 있게 하기 위한 초기값을 어디까지 설정해야하는지 잘 고민해야 함.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());

        // 1. 테이블 정의
        int[] dp = new int[n + 1];

        // 3. 초기값 설정
        dp[1] = 0;

        // 2. 점화식
        for (int i = 2; i <= n; i++) {
            // 기본적으로 1을 뺀 경우 고려
            dp[i] = dp[i - 1] + 1;
            // 2로 나눠지는 경우 최솟값 비교
            if (i % 2 == 0) {
                dp[i] = Math.min(dp[i / 2] + 1, dp[i]);
            }
            // 3으로 나눠지는 경우 최솟값 비교
            if (i % 3 == 0) {
                dp[i] = Math.min(dp[i / 3] + 1, dp[i]);
            }
        }
        System.out.println(dp[n]);
    }
}

예제 2

https://www.acmicpc.net/problem/9095

정수 n이 주어졌을때, n을 1,2,3의 합으로 나타내는 방법의 수?

예를 들어, 4의 경우

정수 4를 1,2,3의 합으로 나타내는 방법은 총 7가지.

• 1+1+1+1
• 1+1+2
• 1+2+1
• 2+1+1
• 2+2
• 1+3
• 3+1

풀이

1. 테이블 정의하기

D[i] = i를 1,2,3의 합으로 나타내는 방법의 수

2. 점화식 찾기

D[4] = ?
1+1+1+1/ 3+1 / 1+2+1/ 2+1+1
2+2/ 1+1+2
1+3

• 각 식에서 끝의 값이 +1, +2, +3 임.
• D[3] +1, D[2] +2, D[1] +3 임을 알 수 있음.
• D[4] = sum(D[3], D[2], D[1])

D[i] = D[i-1]+ D[i-2] + D[i-3]

3. 초기값 설정하기

D[1], D[2], D[3] 필요.
D[1] = 1, D[2]= 2, D[3] = 4
D[i] = D[i-1]+ D[i-2] + D[i-3] 이므로 초기값이 최소 3개는 주어져야 함!

정답코드

package com.hana.kis;

import java.io.*;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // test case
        int tc = Integer.parseInt(br.readLine());


        for(int i=0; i<tc; i++){
            int n = Integer.parseInt(br.readLine());

            // 1. 테이블 정의
            int[] dp = new int[11]; // n은 11보다 작음

            // 3. 초기값 설정
            dp[1]=1;
            dp[2]=2;
            dp[3]=4;

            // 2. 점화식 도출
            for(int k=4; k<=n; k++){
                dp[k]=dp[k-1]+dp[k-2]+dp[k-3];
            }

            System.out.println(dp[n]);
        }

    }
}

1트 때, 런타임에러(ArrayIndexOutOfBounds)가 발생했다.
그 이유는 dp 테이블에서 길이를 n+1로 했었는데, n이 초기값으로 설정한 3보다 작은 수일수도 있기 때문에 index error 가 나는 것이다.
따라서, 문제에서 n은 11보다 작은 수라고 명시했으므로, 크기가 11인 배열로 선언한다.

또한, for문에서 반복자의 범위도 체크해야 한다.
해당 문제에선 k는 4부터 n보다 작거나 같은 수까지 돌게끔 해야 올바르게 dp 테이블이 채워진다.

예제3

https://www.acmicpc.net/problem/2579

계단 마다 적힌 점수를 획득한 최댓값?

<계단 규칙>

• 한번에 한계단/ 두계단식
• 연속된 3개 계단 모두 밟으면 안됨(시작점은 계단에 포함 x)
• 도착 계단은 무조건 밟아야 함

1차 시도
1. 테이블 정의
D[i]= i번째 계단까지의 점수 합 최댓값?
2. 점화식 도출
D[6] = D[1] + D[2]+ D[4] + D[6]
-> 연속 3개 계단이 안되므로 D[i]라는 테이블 갖고 점화식 표현 어렵,,
=> 다른 dp 테이블을 찾아야 함!

1. 테이블 정의

D[i][j] = 현재까지 연속 j개 계단 & i번째 계단까지의 점수 합 최댓값? 단, i번째 계단은 반드시 밟아야 함.

2. 점화식 도출

D[k][1] = ?

• 현재까지 연속 1개 계단 & k번째 계단 까지의 점수 합의 최댓값. k번째 계단은 반드시 밟아야 함
• 현재까지 1개 연속 계단 밟았으므로 -> k-2번째 계단은 반드시 밟아야 함.

D[k][1] = max(D[k-2][1], D[k-2][2]) + S[k](=현재 계단 점수)

D[k][2] = ?

• 현재까지 연속 2개 계단 & k번째 계단까지의 점수 합의 최댓값. k번째 계단은 반드시 밟아야 함.
• 현재까지 2개 연속 계단 밟았으므로 -> k-1번째 계단은 반드시 밟아야 함.

D[k][2] = D[k-1][1] + S[k](=현재 계단 점수)

3. 초기값 설정

D[K][1]의 점화식에 따라 D[K-2]의 값이 필요함.
따라서 초기값은 D[2]까지 설정해주는 게 좋음.

D[1][1] = S[1], D[1][2]= 0
D[2][1] = S[2], D[2][2] = S[1]+S[2]

정답코드

import java.io.*;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 계단 개수
        int n = Integer.parseInt(br.readLine());

        // 계단 점수 저장
        int[] S = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int grade = Integer.parseInt(br.readLine());
            S[i] = grade;
        }

        // 1. dp 테이블 설정
        int[][] dp = new int[n + 1][3];

        // 3. 초기값 설정
        dp[1][1] = S[1];
        dp[1][0] = 0;
        // n이 2 이상 일때만!
        if(n>=2){
            dp[2][1] = S[2];
            dp[2][2] = S[1] + S[2];
        }

        // 2. 점화식 도출
        for (int k = 3; k <= n; k++) {
            dp[k][1] = Math.max(dp[k - 2][1], dp[k - 2][2]) + S[k];
            dp[k][2] = dp[k - 1][1] + S[k];
        }

        System.out.println(Math.max(dp[n][1], dp[n][2]));
    }
}

1차 제출때, 런타임 에러 (ArrayIndexOutOfBounds) 가 발생했는데, n이 2보다 작을 때 dp 테이블 초기화 과정에서 index error 가 날 수 있음을 주의하자!

따라서 n>=2일때만 dp[2][j]와 S[2]처리를 하도록 하였다. 혹은 n=1일때, S[1]을 출력하고 종료하는 조건도 괜찮은 거 같다.

다른 풀이

관점을 좀 달리 하면 1차원 배열로도 dp 테이블을 설정할 수 있다.

계단을 밟은 점수 합이 최댓값이 되려면, 계단을 밟지 않은 점수 합이 최솟값이 되면 된다!

1. 테이블 설정

D[i]= i번째 계단까지 밟지 않은 계단 점수 합의 최솟값, i번째 계단은 반드시 밟지 않음.

2. 점화식 도출

dp문제에서 점화식을 도출하기 어렵다면, dp 테이블을 채워보자.

1	2	3	4	5
10	20	15	?	?

D[4] = ?

4번째 계단을 밟지 않으려면, k-1번째 계단은 무조건 밟아야 함.

따라서 min(D[k-2], D[k-3]) + S[4] 이다! (=10+25)

D[5] = ?

5번째 계단을 밟지 않으려면, k-1번째 계단은 무조건 밟아야 함.

따라서 min(D[3], D[2])+S[5] = 15+10 = 25!

점화식

D[k] = min(D[k-2], D[k-3) + S[k]

3. 초기값 설정

D[K-3]이 쓰이니까 D[3]까지 초기값을 설정해주자.

D[1] = S[1]
D[2] = S[2]
D[3] = S[3]

dp 점화식과 별개로, 정답은 어떻게 출력할까?를 고민해봐야 한다.

현재 D[n]은 n번째까지 밟지 않은 계단 점수의 최솟값이다. 이때 마지막 계단은 반드시 밟아야 하므로,

계단 점수 합 - min(D[n-1], D[n-2])

을 정답으로 반환해준다.

정답코드

import java.io.*;
import java.util.Arrays;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 계단 개수
        int n = Integer.parseInt(br.readLine());

        // 계단 점수 저장
        int[] S = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            int grade = Integer.parseInt(br.readLine());
            S[i] = grade;
        }

        // 1. dp 테이블 설정
        int[] dp = new int[n + 1];

        // 3. 초기값 설정

        // 점수 합
        int sum = 0;
        for (int i : S) {
            sum += i;
        }
        // 3 미만이라면 더한 값이 최댓값임.
        if(n<3){
            System.out.println(sum);
            return;
        }
        
        dp[1] = S[1];
        dp[2] = S[2];
        dp[3] = S[3];

        // 2. 점화식 도출
        for (int i = 4; i <= n; i++) {
            dp[i] = Math.min(dp[i - 2], dp[i - 3]) + S[i];
        }


        System.out.println(sum - Math.min(dp[n - 1], dp[n - 2]));
    }
}

예제 4

https://www.acmicpc.net/problem/1149

RGB 거리.

집 N개. 거리는 선분으로 나타냄.
집은 빨, 초, 파 중 하나의 색으로 칠해야 함.
각각의 집을 빨, 초, 파로 칠하는 비용이 주어질때, 아래 규칙을 만족하면서 모든 집을 칠하는 비용의 최솟값?

<규칙>

• 1번 집은 2번 집의 색과 같지 않아야 함.
• n번 집의 색은 n-1번 집의 색과 같지 않아야 함
• i(2<=i<=n-1)번 집의 색은 i-1, i+1 집의 색과 같지 않아야 함.

1차 시도
1. 테이블 정의
D[i] = i번째 집 색칠하는데 드는 비용 최솟값
-> 해당 dp 테이블로는 점화식 도출이 어려움,, 색 R,G,B에 따른 식이 필요하기 때문!
따라서 다른 dp 테이블이 필요함을 깨달음

1. 테이블 정의하기

D[i][0] = i번째 집까지 색칠하는데 드는 비용의 최솟값. 단 i번째 집은 빨강
D[i][1] = i번째 집까지 색칠하는데 드는 비용의 최솟값. 단 i번째 집은 초록
D[i][2] = i번째 집까지 색칠하는데 드는 비용의 최솟값. 단 i번째 집은 파랑

2. 점화식 도출

D[k][0] = ?
k번째 집까지 색칠하는 데 드는 비용의 최솟값. 단 k번째 집은 빨강임.
따라서 앞에 집은 초록 or 파랑이어야 함.

D[k][0] = min(D[k-1][1], D[k-1][2])+R[k](k번째 집을 빨강으로 색칠하는 데 드는 비용)

마찬가지로, G, B 역시

D[k][1] = min(D[k-1][0], D[k-1][2])+G[k](k번째 집을 초록으로 색칠하는 데 드는 비용)

D[k][2] = min(D[k-1][1], D[k-1][1])+B[k](k번째 집을 파랑으로 색칠하는 데 드는 비용)

3. 초기값 설정

D[k-1]이 있으므로 D[1]의 초기값을 설정해주자.
D[1][0]= R[1]
D[1][1]= G[1]
D[1][2]= B[1]

정답 코드

package com.hana.kis;

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 집 개수
        int n = Integer.parseInt(br.readLine());

        // 색칠 비용 저장
        int[] R = new int[n + 1];
        int[] G = new int[n + 1];
        int[] B = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            // 한줄에 띄어쓰기 기준으로 R, G, B 쫘르륵
            // 1번째 요소: R, 2번째 요소: G, 3번째 요소: B 배열에 넣고자 함.
            StringTokenizer st = new StringTokenizer(br.readLine());

            R[i] = Integer.parseInt(st.nextToken());
            G[i] = Integer.parseInt(st.nextToken());
            B[i] = Integer.parseInt(st.nextToken());
        }

        // 1. dp 테이블 설정
        int[][] dp = new int[n + 1][3];

        // 3. 초기값 설정
        dp[1][0] = R[1];
        dp[1][1] = G[1];
        dp[1][2] = B[1];

        // 2. 점화식 도출
        for (int i = 2; i <= n; i++) {
            dp[i][0] = Math.min(dp[i - 1][1], dp[i - 1][2]) + R[i];
            dp[i][1] = Math.min(dp[i - 1][0], dp[i - 1][2]) + G[i];
            dp[i][2] = Math.min(dp[i - 1][1], dp[i - 1][0]) + B[i];
        }

        // 답 도출
        int tmp = Math.min(dp[n][0], dp[n][1]);
        System.out.println(Math.min(tmp, dp[n][2]));
    }
}

예제5

https://www.acmicpc.net/problem/11726

2xn크기 직사각형을 1x2, 2x1 크기의 타일로 채우는 경우의 수?

아래 그림은 2x5크기 직사각형을 채운 한가지 방법의 예시임.

1. 테이블 정의

D[i]=2xi크기 직사각형 채우는 경우의 수

2. 점화식 도출

1	2	3	4	5	6	7	8	9
1	2	3	5	8	13	21	34	55

dp 테이블을 그려가면서 점화식 발견!

D[k]= D[k-2] + D[k-1]

3. 초기값 설정

D[K-2]가 있으므로 2까지 초기값 설정해준다.

D[1]=1
D[2]=2

정답코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        // 2xn 크기
        int n = Integer.parseInt(br.readLine());

        // 1. dp 테이블 설정
        int[] dp = new int[n + 1];

        // 3. 초기값 설정
        // 1인 경우 예외처리 해준다!
        if (n == 1) {
            dp[1] = 1;
            System.out.println(dp[n]);
            return;
        }

        dp[1] = 1;
        dp[2] = 2;

        // 2. 점화식 도출
        // int overflow가 발생하지 않도록 결과 반환시에만 10007을 나눠주는 것이 아닌 계산마다 나눈 값을 저장해야 한다!
        for (int i = 3; i <= n; i++) {
            dp[i] = (dp[i - 2] + dp[i - 1]) % 10007;
        }

        // 답 도출
        System.out.println(dp[n]);
    }
}

예제 6

https://www.acmicpc.net/problem/11659

수 n개가 주어질때, i번째 수부터 j번째 수까지 합을 구하는 프로그램.

1. 테이블 정의

문제의 dp 테이블을 정의하면 다음과 같다.

D[i]=D[i-1]+A[i]

D[i]= 그전까지의 합 + 현재 요소

2. 점화식 도출

A[i]+A[i+1]+ ... + A[j]
=(A[1]+A[2]+...+A[j])-(A[1]+A[2]+...A[i-1])
=A[j]-A[i-1]

3. 초기값 설정

D[i-1]이 있으므로

D[1]=A[1]

로 설정한다.

정답코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // n m
        String ln1 = br.readLine();
        StringTokenizer st = new StringTokenizer(ln1, " ");

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        // 1. dp 테이블 설정
        int[] dp = new int[n + 1];
        String ln2 = br.readLine();
        StringTokenizer st2 = new StringTokenizer(ln2, " ");

        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1] + Integer.parseInt(st2.nextToken());
        }

        // 3. 초기값 설정
        // 1인 경우 예외처리 해준다!
        if (n == 1) {
            System.out.println(dp[1]);
            return;
        }

        // 2. 점화식 도출: 구간 합 구하기
        for (int k = 0; k < m; k++) {
            String ln3 = br.readLine();
            StringTokenizer st3 = new StringTokenizer(ln3, " ");
            int i = Integer.parseInt(st3.nextToken());
            int j = Integer.parseInt(st3.nextToken());

            // 답 도출
            System.out.println(dp[j] - dp[i - 1]);
        }
    }
}

예제 7

https://www.acmicpc.net/problem/12852

정수 x에 사용할 수 있는 연산 3가지.

1. x가 3으로 나눠떨어질때, 3으로 나눔
2. x가 2로 나눠떨어질때, 2로 나눔
3. 1을 뺀다

위 3가지 연산을 적절히 사용해 1을 만드려고 함.
-> 연산 사용 최솟값?

출력

첫째 줄에 연산 최솟값
둘째 줄에 N을 1로 만드는 방법에 포함된 수를 공백으로 구분해 순서대로 출력. 정답이 여러가지 일경우 아무거나 출력

1. 테이블 정의

기존 dp 테이블 뿐만 아니라 1을 만드는데 거쳐간 수를 출력해야 하므로, 경로 복원용 테이블을 하나 더 두자.

값 테이블 D

1	2	3	4	5	6	7	8
0	1	1	2	3	2	3	3

경로복원용 pre

1	2	3	4	5	6	7	8
0	1	1	2	4	3	6	4

경로복원용 테이블에서 2가 1(2/2 or 2-1)인 이유는 2에서 1가는게 최적이기 때문이다. 3이 1인 이유도 역시, 3에서 1(3/3)로 가는 것이 최적이기 때문.
이와 같은 논리로 테이블을 채워주면 된다.

위와 같이 테이블을 채우고, 7을 확인해보자.
7에서 6으로 가고, 6에서 3으로 가고 3에서 1로 값을 따라가면 7을 1로 만드는 방법에 포함된 수인 (7,6,3,1)이 도출된다.

2. 점화식 도출

D[i] = min(D[i/3]+1, D[i/2]+1, D[i-1]+1)

pre[i] =
- i-1, if D[i]=D[i-1]+1
- i/2, if i%2==0 and D[i]=D[i/2]+1
- i/3, if i%3==0 and D[i]=D[i/3]+1

pre[i]는 D[i]값을 갱신할 때 선택한 이전 값을 저장하는 테이블임. 즉, pre[i]는 D[i]가 최솟값을 가지도록 만든 i 이전의 값임.

즉, D[i]가 최솟값을 가지게 만든 직전 i값을 pre[i]에 저장하면 됨.

3. 초기값 설정

D[1]=0
pre[1]=0

정답코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String args[]) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        // n
        int n = Integer.parseInt(br.readLine());

        // 1. dp 테이블 설정
        int[] dp = new int[n + 1];
        int[] pre = new int[n + 1]; // dp[i]가 최솟값을 만들게 한 직전 값 저장용

        // 3. 초기값 설정
        dp[1] = 0;
        pre[1] = 0;

        // 2. 점화식 도출

        // 만드는 데 걸린 경로 값 출력
        for (int i = 2; i <= n; i++) {
            // 1을 빼준다.
            dp[i] = dp[i - 1] + 1; // dp[4]=dp[3]+1 = 2
            pre[i] = i - 1; // pre[4]=3;

            // 2로 나눠지면 2로 나눈다 -> 최솟값이 저장되어야 하므로 2로 나눈 값이 더 작으면 갱신
            if (i % 2 == 0 && dp[i] > dp[i / 2] + 1) { // dp[4] > dp[2]+1
                dp[i] = dp[i / 2] + 1;
                pre[i] = i / 2;
            }

            // 3으로 나눠지면 3으로 나눈다
            if (i % 3 == 0 && dp[i] > dp[i / 3] + 1) {
                dp[i] = dp[i / 3] + 1;
                pre[i] = i / 3;
            }
        }
        // 연산 횟수 출력
        System.out.println(dp[n]);

        // 경로 값 출력
        int cur = n;
        StringBuilder sb = new StringBuilder();

        while (true) {
            sb.append(cur).append(" ");
            if (cur == 1) break;
            cur = pre[cur];
        }
        System.out.print(sb.toString().trim()); // 마지막 숫자에 붙인 공백 지움(trim: 문자열 양 끝의 불필요한 공백 지움)
    }
}

프로그래머스

N으로 표현

https://school.programmers.co.kr/learn/courses/30/lessons/42895?language=java

제한사항

• N은 1 이상 9 이하입니다.
• number는 1 이상 32,000 이하입니다.
• 수식에는 괄호와 사칙연산만 가능하며 나누기 연산에서 나머지는 무시합니다.
• 최솟값이 8보다 크면 -1을 return 합니다.

풀이

1. 테이블 정의

N을 최대 8번까지 사용해, number을 만들 수 있는 지 찾아야 함.

• 숫자를 반복해 붙여 쓸 수 있음-> 예: 5,55,555
• 사칙연산만 허용됨
• 최솟값을 찾아야 하므로, 각 사용횟수 별로 만들 수 있는 숫자 집합 관리

D[i]=N을 i번 사용해 만들 수 있는 숫자 집합

2. 점화식 도출

1. 숫자 반복

• D[i]에 반복된 숫자(n, nn, nnn, ...)을 추가

2. 이전 dp 조합을 활용한 사칙연산

• k: 1부터 i-1까지 값을 순회하는 변수 -> D[i]를 만들기 위해 더 작은 부분 문제들(D[k]와 D[i-k]를 조합)
  따라서,

D[i]: D[k]와 D[i-k]을 사칙연산한 값

• 예를 들어, D[2]는 D[1]와 D[1]의 사칙연산한 값이다.
• D[3]은 D[1]와 D[2]의 사칙연산한 값

3. 나누기 연산시 나머지는 무시함

• 즉 %가 아니라, /으로 정수 나누기 진행

D[i]= 위와 같이 탐색한 이전 D[j]들의 조합

3. 초기값 설정

D[1] = {N}

• n을 1번 사용했을때 만들 수 있는 숫자 집합은 N 하나 뿐임.

import java.util.*;

class Solution {
    public int solution(int N, int number) {
        int answer = 0;
        
        // 1. 테이블 정의: 배열의 각 요소에 집합을 저장한다
        Set<Integer>[] dp = new HashSet[9];
        
        // 3. 초기값 설정
        dp[1]= new HashSet<>();
        dp[1].add(N);
        
        // tc9: number==N일때 1 반환 후 종료해야함(for문 i=2부터 시작하므로 i=1의 조건 검사를 빠뜨림)
        if(number==N){
            return 1;
        }
        
        // 2. 점화식 도출
        for(int i = 2; i < 9; i++){
            // i개의 N을 사용해 만들 수 있는 숫자 저장
            dp[i]= new HashSet<>();
            
            // 1. 반복한 숫자 추가
            String repeat = String.valueOf(N).repeat(i);
            dp[i].add(Integer.parseInt(repeat));            
            
            // 2. 이전 숫자 조합을 활용한 사칙연산
            for(int k = 1; k <i; k++){
                for(int num1: dp[k]){
                    for(int num2: dp[i-k]){
                        dp[i].add(num1+num2);
                        dp[i].add(num1-num2);
                        dp[i].add(num1*num2);
                        if (num2 !=0) dp[i].add(num1/num2);
                    }
                }
            }
            // n이 dp[i]에 있다면 최소 사용 횟수 i를 반환
            if(dp[i].contains(number)) return i;
        }
        // 최솟값이 8보다 크면 -1 return
        return -1;
    }
}

정수 삼각형

https://school.programmers.co.kr/learn/courses/30/lessons/43105?language=java

삼각형 꼭대기에서 바닥까지 이어지는 경로 중, 거쳐간 숫자의 합이 큰 경우?

이동: 대각선 방향으로 한 칸 오른쪽 or 왼쪽 가능

1. 테이블 정의

D[i][j]=i번째 높이에서의 현재 요소인 j까지 경로들의 숫자합

• i: 삼각형의 행, j는 각 행의 인덱스
• D[i][j]는 (i,j)위치에 도달했을때 최대 합 저장

2. 점화식 도출

문제의 핵심은 각 요소에서 다음 행으로 내려가면서, 가능한 경로 중 합이 큰 값을 선택하는 것

예제에서,
높이 2: 8이 아니라 3을 선택한 이유를 보면 알 수 있다.

3일때, 다음 요소까지 더했을때의 합이 더 크기 때문.
7+3+8> 7+8+1 이기 때문에.

즉, 대각선 방향으로 이동할 수 있으므로, (i,j)에서 (i+1, j) or (i+1, j+1)로 이동 가능!

D[i][j] = triangle[i][j] + max(D[i+1][j], D[i+1][j+1])

3. 초기값 설정

D[1][1]=triangle[0][0]

알고리즘 설계할 때는 1-based로 했지만, 코드는 편의상 0-based로 구현했다.

import java.util.*;

class Solution {
    public int solution(int[][] triangle) {
        int answer = 0;
        
        // 삼각형 행
        int n = triangle.length;
        
        // 1. dp 테이블 정의 - 0-based
        int[][] dp = new int[n][n];
        
        // 3. 초기값 설정
        dp[0][0]=triangle[0][0];
        
        
        // 2. 점화식 도출
       for(int i=1; i<n; i++){
           for(int j=0; j<=i; j++){
               if(j==0){ // 왼쪽 끝: 바로 위의 값에서 내려와야 함
                    dp[i][j]=triangle[i][j] + dp[i-1][j];
               }
               else if(j==i){ // 오른쪽 끝: 왼쪽 위에서 내려와야 함
                    dp[i][j]=triangle[i][j] + dp[i-1][j-1];
               }
               else{
                   dp[i][j]=triangle[i][j] + Math.max(dp[i-1][j], dp[i-1][j-1]);
               }
           }
       }

        // 4. 정답 출력(최댓값 찾기)
        for(int i=0; i<n; i++){
            answer = Math.max(answer, dp[n-1][i]);
        }
        
        return answer;
    }
}

등굣길

https://school.programmers.co.kr/learn/courses/30/lessons/42898?language=java

mxn 크기의 맵.
puddles: 물 웅덩이.
이동: 오른쪽, 아래
집(1,1)에서 학교(m,n)까지 갈 수 있는 최단경로의 개수를 1000000007로 나눈 나머지 반환.

1. 테이블 정의

D[i][j]= (i,j) 위치까지의 거쳐온 경로 총 개수

2. 점화식 도출

(1,1)에서 출발해서 (m,n)까지 도달해야 함.
이때, 이동 방향은 오른쪽, 아래 뿐이므로
왼쪽, 위쪽 에서 온 경우를 생각해야 함.

즉, (i-1, j) + (i, j-1) 왼쪽, 위쪽에서온 경우를 더해준 값이 경로의 개수임.

또한, 물 웅덩이로는 이동 못하므로,
(i,j)가 물웅덩이인 경우
D[i][j]=0

if (i,j)==물웅덩이 라면,
D[i][j]=0

아니라면,
D[i][j] += D[i-1][j]+D[i][j-1]

3. 초기값 설정

1일때, D[i][j]를 더해주므로

D[1][1]=1;

정답코드

import java.util.*;

class Solution {
    public int solution(int m, int n, int[][] puddles) {
        int answer = 0;
        // overflow 방지
        int MOD= 1000000007;
        
        // 1. 테이블 정의: 1 based
        int[][] dp = new int[n+1][m+1];
        
        // 3. 초기값 설정
        dp[1][1]=1;

        // System.out.println(Arrays.deepToString(dp));
        
        // puddles를 조건식으로 처리하기 위해 boolean값으로 바꾼다.
        boolean[][] isPu = new boolean[n+1][m+1];
        
        for(int[] puddle: puddles){
            isPu[puddle[1]][puddle[0]]=true; // puddles는 x,y 형식이므로 순서주의
        }
            
        // 2. 점화식 도출
        for(int i=1; i<=n; i++){
            for(int j=1; j<=m; j++){
                if(isPu[i][j]){
                    dp[i][j]=0; // 물 웅덩이라면 경로 0
                }
                else{
                    // 오른쪽으로(=왼쪽에서 온 경우) +  아래로(=위쪽에서 온 경우)
                    dp[i][j]+=(dp[i-1][j]+dp[i][j-1])%MOD;
                }
            }
        }
        
        return dp[n][m];
    }
}