개발 블로그

문제 링크 : https://acmicpc.net/problem/15989

3
4
7
10

4
8
14

풀이 방법

[1]

1

=> 1가지

(0가지 일 수도 있는지?...)

[2] 

1 + 1

=> 1가지

[3]

1 + 1 + 1

2 + 1

=> 2가지

[4]

1 + 1 + 1 + 1

2 + 1 + 1 , 2 + 2

3 + 1

=> 4가지

[5]

1 + 1 + 1 + 1 + 1

2 + 1 + 1 + 1 , 2 + 2 + 1

3 + 1 + 1, 3 + 2

=> 5가지

[6]

1 + 1 + 1 + 1 + 1 + 1

2 + 1 + 1 + 1 + 1 , 2 + 2 + 1 + 1, 2 + 2 + 2

3 + 1 + 1 + 1, 3 + 2 + 1

3 + 3

=> 7가지

[7]

1 + 1 + 1 + 1 + 1 + 1 + 1

2 + 1 + 1 + 1 + 1 + 1 , 2 + 2 + 1 + 1 + 1, 2 + 2 + 2 + 1

3 + 1 + 1 + 1 + 1, 3 + 2 + 1 + 1, 3 + 2 + 2, 

3 + 3 + 1

=> 8가지

[8]

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

(2 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 1 + 1 + 1 + 1), (2 + 2 + 2 + 1 + 1), (2 + 2 + 2+ 2)

(3 + 1 + 1 + 1 + 1 + 1), (3 + 2 + 1 + 1 + 1), (3 + 2 + 2 + 1)

(3 + 3 + 1 + 1), (3 + 3 + 2)

=> 10가지

 [9]

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

(2 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 2 + 1 + 1 + 1), (2 + 2 + 2+ 2 + 1)

(3 + 1 + 1 + 1 + 1 + 1 + 1), (3 + 2 + 1 + 1 + 1 + 1), (3 + 2 + 2 + 1 + 1), (3 + 2 + 2 + 2)

(3 + 3 + 1 + 1 + 1), (3 + 3 + 2 + 1)

(3 + 3 + 3)

=> 12가지

 [10]

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

(2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 2 + 1 + 1 + 1 + 1), (2 + 2 + 2+ 2 + 1 + 1), (2 + 2 + 2+ 2 + 2)

(3 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (3 + 2 + 1 + 1 + 1 + 1 + 1), (3 + 2 + 2 + 1 + 1 + 1), (3 + 2 + 2 + 2 + 1)

(3 + 3 + 1 + 1 + 1 + 1), (3 + 3 + 2 + 1 + 1), (3 + 3 + 2 + 2)

(3 + 3 + 3 + 1)

=> 14가지

 [11]

1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1

(2 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 2 + 1 + 1 + 1 + 1 + 1), (2 + 2 + 2+ 2 + 1 + 1 + 1), (2 + 2 + 2+ 2 + 2 + 1)

(3 + 1 + 1 + 1 + 1 + 1 + 1 + 1 + 1), (3 + 2 + 1 + 1 + 1 + 1 + 1 + 1), (3 + 2 + 2 + 1 + 1 + 1 + 1), (3 + 2 + 2 + 2 + 1 + 1), (3 + 2 + 2 + 2 + 2)

(3 + 3 + 1 + 1 + 1 + 1 + 1), (3 + 3 + 2 + 1 + 1 + 1), (3 + 3 + 2 + 2 + 1)

(3 + 3 + 3 + 1 + 1), (3 + 3 + 3 + 2)

=> 16가지

6부터 2씩 증가-> fail!!!

==========================

dp[n,k] : 1,,,k 를 활용해 n을 만드는 방법의 수로 가정하고 각 값을 구해보자. 

===========================================

• dp[n,1] = 1
• dp[n,2] = n/2(몫만) + 1
• dp[n-3] = dp[n-1, 1] +dp[n-2, 2] + dp[n-3, 3]   = 1 + {(n-2)/2} + 1 + dp[n-3,3]

import java.util.Scanner;

public class BOJ_15989_123더하기4 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        int[][] dp= new int[10001][4];

        for(int n = 0; n<=10000; n++){
            dp[n][0] = 0;
            dp[n][1] = 1;
            dp[n][2] = n/2 + 1;
        }
        dp[1][2] = 1; dp[1][3] = 1;
        dp[2][2] = 1; dp[2][3] = 2;
        dp[3][2] = 2; dp[3][3] = 3;
        dp[4][2] = 3; dp[4][3] = 4;
        
        for(int i = 5; i<=10000; i++){
            dp[i][3] = 2 + (i-2)/2 + dp[i-3][3];
        }


        int n;
        for(int i = 0; i<T; i++){
            n = sc.nextInt();
            System.out.println(dp[n][3]);

        }
    }
}

문제 링크 : https://www.acmicpc.net/problem/10164

접근 방법

처음에는 조합으로 풀었다가 32점이 나와서 dp로 문제를 해결했다.

처음 접근 방법은 K가 0이 아니면

K의 좌표를 구한 다음 -> 그 좌표까지 가려면 우측 방향으로 몇번 가야하는지와 아래 방향으로 몇 번 가야하는지를 조합을 사용해서 계산햇다. 

예제를 예시로 들면 아래에서 K까지 가려면 처음 [0][0]에서 우측으로 두 번, 아래 방향으로 한 번 가면 되는 것이다.

총 세번 이동을 해야하는데 그 중에 아래 화살표들을 순서 상관 없이 나열하는 조합의 경우의 수를 구하면 된다. 

➡️➡️⬇️

➡️⬇️➡️

⬇️➡️➡️

import java.util.Scanner;

public class Main {

    static int combi(int n, int r){
        if(n==r || r==0) return 1;
        return combi(n-1, r-1) + combi(n-1,r);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();
        int K = sc.nextInt();
        int ans = 0;

        if(K!=0){
            int kRow = K/M;
            int kCol = K%M -1;

            int first = combi(kRow+kCol, kCol);
            int second = combi(M-kCol-1 + N-kRow-1, N-kRow-1);
            ans = first*second;
        }
        else{
            ans = combi(N+M-2, N-1);
        }
        System.out.println(ans);

    }
}

그러나 이 방법으로는 32점밖에 안 나와서 N,M이 커지면 서브테스크 3번부터 막히는 것 같아 dp로 다시 풀었다.

dp로 풀때 주의할 점은 K의 위치를 잘 구해야 한다는 것이다.

예제로 주어진 문제로만 푸는 것이 아니라

반레로 K가 M으로 딱 나눠서 떨어지는 경우 즉 입력 값이 (2, 2, 2) 인 케이스도 생각하면 서브 테스크 3,4번도 모두 맞출 수 있다

import java.util.Scanner;

public class BJOJ_10164_격자상의경로 {

    static int combi(int n, int r){
        if(n==r || r==0) return 1;
        return combi(n-1, r-1) + combi(n-1,r);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int N = sc.nextInt();
        int M = sc.nextInt();
        int K = sc.nextInt();
        int ans = 0;
        int[][] dp = new int[N][M];
        dp[0][0] = 0;

        if(K!=0){
            int kRow = K/M;
            int kCol = K%M;
            if(K%M == 0) {		//K가 오른쪽 끝에 붙어있는 경우 고려
                kRow -= 1;
                kCol = M-1;
            }else kCol-=1;


            for(int i = 1; i<=kRow; i++) {
                dp[i][0] = 1;
            }
            for(int i = 1; i<=kCol; i++){
                dp[0][i] = 1;
            }
            for(int i = 1; i<=kRow; i++){
                for(int j = 1; j<=kCol; j++){
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
            for(int i = kRow+1; i<N; i++) dp[i][kCol] = dp[kRow][kCol];
            for(int j = kCol+1; j<M; j++) dp[kRow][j] = dp[kRow][kCol];
            for(int i = kRow+1; i<N; i++){
                for(int j = kCol+1; j<M; j++){
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }

        }
        else{
            for(int i = 1; i<N; i++) {
                dp[i][0] = 1;
            }
            for(int i = 1; i<M; i++){
                dp[0][i] = 1;
            }
            for(int i = 1; i<N; i++){
                for(int j = 1; j<M; j++){
                    dp[i][j] = dp[i-1][j] + dp[i][j-1];
                }
            }
        }
        System.out.println(dp[N-1][M-1]);


    }
}

문제 링크 : https://www.acmicpc.net/problem/2240

7 2
2
1
1
2
2
1
1

6

접근 방법

처음에는 자두의 위치를 1) 그대로 있는 경우와 2) 옆 나무로 움직이는 경우 두 가지 케이스로 분류하려고 했으나, 자두의 위치 외에도 고려해야할 변수가 두개가 더 있었다. ( 현재 몇초인지(t)와 t초에 몇번째 자두나무에서 자두가 떨어지는지) 

즉 총 세개의 변수를 고려해야함을 알았는데

추가로 매 t초마다 하는 선택이 최선의 선택이 아니며, 그렇다고 모든 경우의 수를 다 조사해 볼 수는 없기 때문에 dp로 풀기로 했다. 

dp 배열 및 각 인덱스 의미는 다음과 같다. 

dp[t][w][1] : 현재 t초이며(t초 지남), t초까지 w만큼 이동했고, 그때의 자두의 현재 위치는 1일 때 -> 먹을 수 있는 자두의 최대 갯수

dp[t][w][2] : 현재 t초이며(t초 지남), t초까지 w만큼 이동했고, 그때의 자두의 현재 위치는 2일 때 -> 먹을 수 있는 자두의 최대 갯수

이제 및 [몇번째 자두나무에서 자두가 떨어지는지] 및 [자두의 이동 여부] 케이스를 분류해서 생각해보자.

각각 2가지 경우의 수가 있다. 

-> 1번째 자두나무에서 자두가 떨어지거나 or 2번째 자두나무에서 자두가 떨어지거나

-> 그대로 있거나 Or 옆 나무로 이동하거나

Case1. 1번째 자두나무에서 자두가 떨어질 때

경우 1) 현재 자두가 1번에 있을 때 : 자두 먹을 수 있음

//자두가 t초째에 1번 자두나무 아래에 있을 때 (자두 먹은 케이스)
dp[t][w][1] = Math.max(dp[t-1][w][1], dp[t-1][w-1][2])+ 1;

=> 해석 : 1초 전에, 안 움직이고(w그대로), 1번에 있을 때 (안 움직여서 1번 그대로)

          vs 1초 전에, 움직이고 (w-1), 2번에 있을 때(2번에 있었으니까 1번으로 옮긴것)

중에 최대값을 구하고, 거기에 1을 더한다. 1을 더한 이유는

1번째 자두나무에서 자두가 떨어지는 Case1. 일 때

현재 자두의 위치가 1번 나무 아래에 있는 경우1) 이기 때문이다. 

경우 2) 현재 자두가 2번에 있을 때 : 자두 못 먹음 

//자두가 t초째에 2번 자두나무 아래에 있을 때
dp[t][w][2] = Math.max(dp[t-1][w-1][1], dp[t-1][w][2]);

=> 해석 : 1초 전에, 움직이고 (w-1), 1번에 있을 때 (1번에 있었으니까 2번으로 옮긴 것)) 

          vs 1초 전에, 안 움직이고(w그대로), 2번에 있을 때(안 움직여서 2번 그대로)

중에 최대값을 구하고, 이번엔 1을 안 더한다. 안 더한 이유는

1번째 자두나무에서 자두가 떨어지는 Case1. 일 때

현재 자두의 위치가 2번 나무 아래에 있는 경우2) 이기 때문이다. 

이런 방식으로 매 시간에 따라(t가 1부터 T일때까지)

w가 1일때부터 W일때까지 dp를 채워나간다. 

그리고 마지막에 모든 w에 대해서 dp[T][w][1], dp[T][w][2] 값 들 중에 최대값을 구한다. 

import java.util.*;

public class BOJ_2240_자두나무 {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        int W = sc.nextInt();
        int treeArr[] = new int[1001];
        int dp[][][] = new int[T+1][W+1][3];
        treeArr[0] = 1; //맨 처음 1번 나무에서 시작
        for(int i = 1; i<=T; i++){
            treeArr[i] = sc.nextInt();
        }

        //초기 값 셋팅
        if(treeArr[1] == 1){    //1초일 때, 첫번째 자두가 1번 나무에서 떨어질 경우(초기에 자두는 1번 나무 아래 있음)
            dp[1][0][1] = 1;    //1초일 때, 0번 움직여서, 현재 위치 그대로(1)   -> 자두 1개 먹음 (안움직이고 먹음)
            dp[1][1][2] = 0;    //1초일 때, 1번 움직여서, 현재 위치 바뀌고(2로) => 자두 0개 먹음 (움직이고 못먹음)
        }
        else{                   //1초일 때, 첫번째 자두가 2번 나무에서 떨어질 경우
            dp[1][0][1] = 0;    //1초일 때, 0번 움직이고, 현재 위치 그대로(1) -> 자두 0개 먹음 (안움직이고 못먹음)
            dp[1][1][2] = 1;    //1초일 때, 1번 움직이고, 현재 위치 바뀌고(2로) -> 자두 1개 먹음 (움직이고 먹음)

        }


        for(int t = 2; t<=T; t++){

            if(treeArr[t] == 1){    //1번 자두나무에서 자두가 떨어질 때
                //w = 0일 때 (안 움직였을 때) 현재 위치에 따른 초기 값 셋팅
                dp[t][0][1] = dp[t-1][0][1] + 1;    //현재 위치 1이면 = 0번 움직이고, 현재 위치 그대로 (안 움직이고 먹음)
                dp[t][0][2] = dp[t-1][0][2];        //현재 위치 2이면 = 0번 움직이고, 현재 위치 그대로 (안 움직이고 못 먹음)

                for(int w = 1; w<=W; w++){
                    //자두가 t초째에 1번 자두나무 아래에 있을 때 (자두 먹은 케이스)
                    dp[t][w][1] = Math.max(dp[t-1][w][1], dp[t-1][w-1][2])+ 1;
                    //자두가 t초째에 2번 자두나무 아래에 있을 때
                    dp[t][w][2] = Math.max(dp[t-1][w-1][1], dp[t-1][w][2]);
                }
            }

            else{                   //2번 자두나무에서 자두가 떨어질 때
                //w = 0일 때 (안 움직였을 때) 현재 위치에 따른 초기 값 셋팅
                dp[t][0][1] = dp[t-1][0][1];        //현재 위치 1이면 = 0번 움직이고, 현재 위치 그대로 (안 움직이고  못 먹음)
                dp[t][0][2] = dp[t-1][0][2] + 1;    //현재 위치 2이면 = 0번 움직이고, 현재 위치 그대로 (안 움직이고 먹음)



                for(int w = 1; w<=W; w++){
                    //자두가 t초째에 1번 자두나무 아래에 있을 때
                    dp[t][w][1] = Math.max(dp[t-1][w][1], dp[t-1][w-1][2]);
                    //자두가 t초째에 2번 자두나무 아래에 있을 때 (자두 먹은 케이스)
                    dp[t][w][2] = Math.max(dp[t-1][w-1][1], dp[t-1][w][2]) + 1;
                }
            }


        }

        int ans = 0;    //최대 값을 구해야 함
        for(int w = 0; w<=W; w++){
            ans = Math.max(ans, Math.max(dp[T][w][1], dp[T][w][2]));
        }
        System.out.println(ans);
    }
}

문제 링크 : https://www.acmicpc.net/problem/9251

ACAYKP
CAPCAK

4

---

 

접근 방법

처음에는 완전 탐색으로 해결하려고 했다. 그러나 해당 문제의 제한 시간은 0.1초라 dp로 해결해야함을 알게 되었다.

최장 공통 수열을 찾기 위해서는 마지막의 문자에 주목해야한다. 

ABDE와 ABE의 공통 수열을 찾는다고 해보자. 주어진 문자열은 길이가 짧아서 바로 LCS = "ABE"라는 답이 나오지만, 

문자열이 길어지면 한 눈에 파악하기 어렵다. 그럴 때는 마지막부터 거꾸로 거슬러 올라갈 수 있다.

즉, 마지막 문자열인 E가 동일하니, ABD와 AB의 LCS에 +1을 더하면 그것이 답이 되는 것이다. (arr[i-1][j-1] + 1)

그러나 이 로직은 마지막 문자가 서로 같을 경우에만 적용되며, ABD와 AB처럼 서로 다른 경우에는 아래와 같이 경우를 나눠서 생각해야 한다.

1)  D를 포함시킬 때 : ABD - A 간의 LCS = 1(A)    (arr[i-1][j])

2) B를 포함시킬 때 : AB - AB 간의 LCS = 2(AB)  (arr[i][j-1])
서로 다른 끝 문자를 하나씩 포함시킬 때, 둘 중 LCS의 최대값이 ABD와 AB의 LCS가 된다. Max(arr[i-1][j], arr[i-1][j])

 

이를 코드로 작성하면 아래와 같다. 

 

import java.util.*;
public class Main {
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        String strA = sc.nextLine();
        String strB = sc.nextLine();

        int arr[][] = new int[1001][1001];

        for(int i = 1; i<=strB.length(); i++){
            for(int j = 1; j<=strA.length(); j++){
                if(strB.charAt(i-1) == strA.charAt(j-1)){	//끝 문자가 같을 때 
                    //arr[i][j] = arr[i-1][j] + 1;
                    arr[i][j] = arr[i-1][j-1] + 1;
                }
                else{										//끝 문자가 다를 때
                    //arr[i][j] = arr[i][j-1];
                    arr[i][j] = Math.max(arr[i][j-1], arr[i-1][j]);	
                }
            }

        }
        System.out.println(arr[strB.length()][strA.length()]);
    }
}

 

문제 링크 : https://www.acmicpc.net/problem/12865

문제

이 문제는 아주 평범한 배낭에 관한 문제이다.

한 달 후면 국가의 부름을 받게 되는 준서는 여행을 가려고 한다. 세상과의 단절을 슬퍼하며 최대한 즐기기 위한 여행이기 때문에, 가지고 다닐 배낭 또한 최대한 가치 있게 싸려고 한다.

준서가 여행에 필요하다고 생각하는 N개의 물건이 있다. 각 물건은 무게 W와 가치 V를 가지는데, 해당 물건을 배낭에 넣어서 가면 준서가 V만큼 즐길 수 있다. 아직 행군을 해본 적이 없는 준서는 최대 K만큼의 무게만을 넣을 수 있는 배낭만 들고 다닐 수 있다. 준서가 최대한 즐거운 여행을 하기 위해 배낭에 넣을 수 있는 물건들의 가치의 최댓값을 알려주자.

입력

첫 줄에 물품의 수 N(1 ≤ N ≤ 100)과 준서가 버틸 수 있는 무게 K(1 ≤ K ≤ 100,000)가 주어진다. 두 번째 줄부터 N개의 줄에 거쳐 각 물건의 무게 W(1 ≤ W ≤ 100,000)와 해당 물건의 가치 V(0 ≤ V ≤ 1,000)가 주어진다.

입력으로 주어지는 모든 수는 정수이다.

출력

한 줄에 배낭에 넣을 수 있는 물건들의 가치합의 최댓값을 출력한다.

접근 방법

이 문제는 유명한 '배낭 문제(https://ko.wikipedia.org/wiki/%EB%B0%B0%EB%82%AD_%EB%AC%B8%EC%A0%9C)' 이다.

DFS를 이용한 완전탐색으로 풀었더니 시간초과가 났다. DP로 빠르게 풀어보자.

i = 1 부터 N 까지

1) 해당 물건을 배낭에 담았을 때와

2) 배낭 리미트 K를 넘어가서 해당 물건을 담지 않았을 때를

고려하여 검사를 진행한다.

DP[i][k] : 1번째 물건부터 i번째 물건까지 고려했을 때, 담을 수 있는 가장 최대 가치라고 하자.

그리고 예제에 주어진 입력으로 아래 이차원배열 DP를 채워보자.

먼저 limit가 1일 때는 아무것도 담을 수 없다. 물건들 무게가 모두 1이 넘기 때문이다. 그래서 limit=1인 열은 모두 0으로 채운다.

limit = 2일때도 마찬가지이다. 

그리고 W[3]은 무게가 3이기 때문에 담을 수 있다. V[3] = 6이므로, DP[3][2]을 6으로 채워준다. 

limit = 3일 때

: W[1]과 W[2]는 담을 수 없다. limit 3을 넘어가기 때문이다. 0으로 채워준다. 

그리고 W[3]은 무게가 3이기 때문에 담을 수 있다. V[3] = 6이므로, DP[3][2]을 6으로 채워준다. 

그러면 네번째 물건까지 고려했을 때, 담은 물건의 최대 가치는 어떻게 될까?

W[4]는 5이기 때문에 네번째 물건은 담을 수 없다. -> 그렇기 때문에 4번째 물건까지 고려하기 직전인 3번째 물건까지 고려했을 때 최대 가치인 DP[3][3]을 DP[4][3]에도 넣어주면 된다. 

limit = 4일 때

 : 첫번째 물건을 고려했을 때, W[1] = 6이기 때문에 담을 수 없다. DP[1][4]에는 0을 채워준다.

 : 두번째 물건까지 고려했을 때, W[2] = 4이기 때문에 담을 수 있다. DP[2][4]에는 두번째 물건의 가치 "V[2] = 8"을 채워준다.

 : 세번째 물건까지 고려했을 때, W[3] = 3이기 때문에 담을 수 있다. 그런데 V[3] = 6이고, 이것은 두번째 물건을 고려했을 때, 즉 두번째 물건만 담았을 때보다 가치가 더 적기 때문에 DP[3][4]에는 DP[2][4]의 값을 그대로 넣어준다. 

 : 네번째 물건까지 고려했을 때, W[4] = 5이기 때문에 담을 수 없다. 그래서 세번째 물건까지 고려했을 때의 값인 DP[3][4]를 DP[4][4]에도 넣어준다. 

limit = 5일 때

 : 첫번째 물건을 고려했을 때, W[1] = 6이기 때문에 담을 수 없다. DP[1][5]에는 0을 채워준다.

 : 두번째 물건까지 고려했을 때, W[2] = 4이기 때문에 담을 수 있다. DP[2][5]에는 두번째 물건의 가치 "V[2] = 8"을 채워준다.

 : 세번째 물건까지 고려했을 때, W[3] = 3이기 때문에 담을 수 있다. 그런데 V[3] = 6이고, 이것은 두번째 물건을 고려했을 때, 즉 두번째 물건만 담았을 때보다 가치가 더 적기 때문에 DP[3][5]에는 DP[2][5]의 값을 그대로 넣어준다. 

 : 네번째 물건까지 고려했을 때, W[4] = 5이기 때문에 담을 수 있다. V[4] = 12로, 이 값은 세번째 물건까지 고려했을 때 가치인 8보다 크기 때문에 DP[4][5]는 12로 채워준다. 

limit = 6일 때

 : 첫번째 물건을 고려했을 때, W[1] = 6이기 때문에 담을 수 있다. DP[1][6]에는 V[1] = 13을 채워준다.

 : 두번째 물건까지 고려했을 때, W[2] = 4이기 때문에 담을 수 있다. 그런데 V[2] =8이고, 이것은 첫번째 물건까지 고려했을 때, 즉 첫번째 물건만 담았을 때보다 가치가 더 적기 때문에 DP[2][6]에는 DP[1][6]의 값을 그대로 넣어준다.

 : 세번째 물건까지 고려했을 때, W[3] = 3이기 때문에 담을 수 있다. 그런데 V[3] = 6이고, 이것은 두번째 물건까지 고려했을 때 보다 가치가 더 적기 때문에 DP[3][6]에는 DP[2][6]의 값을 그대로 넣어준다. 

 : 네번째 물건까지 고려했을 때, W[4] = 5이기 때문에 담을 수 있다. V[4] = 12로, 이 값은 세번째 물건까지 고려했을 때 가치인 13보다 작기 때문에 DP[4][6]는 DP[3][6]의 값을 그대로 채워준다. 

limit = 7일 때

 : 첫번째 물건을 고려했을 때, W[1] = 6이기 때문에 담을 수 있다. DP[1][7]에는 V[1] = 13을 채워준다.

 : 두번째 물건까지 고려했을 때, W[2] = 4이기 때문에 담을 수 있다. 그런데 V[2] =8이고, 이것은 첫번째 물건까지 고려했을 때, 즉 첫번째 물건만 담았을 때보다 가치가 더 적기 때문에 DP[2][7]에는 DP[1][7]의 값을 그대로 넣어준다.

 : 세번째 물건까지 고려했을 때, W[3] = 3이기 때문에 담을 수 있다. 이때, 이전과는 다르게 한번 더 생각해야한다!!!

왜냐하면 만약 무게가 3인 세번째 물건을 담으면, 백팩은 무게 4가 남게 된다.

그 남은 무게에서 최대 가치는-> "limit=4이고 두번째 물건까지 고려했을 때"인 DP[2][4]가 된다. 

그리고 만약 무게가 3인 세번째 물건을 담지 않으면, 두번째 물건까지 고려했을 때의 최대 가치인 DP[2][7]의 값을 DP[3][7]에도 채워주면 된다. 

즉, 정리하면 아래 두 경우 중 더 큰 값을 DP[3][7]에 채워준다.

case 1) W[3]을 담을 경우 : DP[3][7] = DP[2][7 - W[3]] + V[3]

case 2) W[3]을 담지 않을 경우 : DP[3][7] = DP[2][7]

결론은, case 1)에서 DP[3][7]은 8+6 = 14로서,

case 2)에서 DP[2][7]인 13보다 크기 때문에 

DP[3][7]에는 14를 채워준다. 

: 네번째 물건까지 고려했을 때도 위 상황과 같이 아래의 두 경우를 고려해서 적어주면 된다. 

case 1) W[4]를 담을 경우 : DP[4][7] = DP[3][7 - W[4]] + V[4]

                                                            = DP[3][7 - 5]       + V[4]  

                                                            = DP[3][7 - 5]       + V[4]

                                                            = 0                          + 12

case 2) W[4]를 담지 않을 경우 : DP[4][7] = DP[3][7] = 14

즉, DP[4][7] = max(12, 14) = 14.

점화식으로 표현하면 다음과 같다.

DP[i][k] (최대 k무게까지 담을 수 있고, 1~i번째 물건까지 고려했을 때, 최대 가치 합) ?

1) DP[i-1][k]                                                                                         (W[i] > k) : i번째 물건 무거워서 못 담을 때

2) max( DP[i - 1][k - W[i]]   +   V[i]  ,  DP[i-1][k] )                  (W[i] <=k and i>0) : i번째 물건 담았을 때

3) 0                                                                                                    (i = 0 and k = 0)                                                                        

//
//  DFS_BOJ12865_평범한배낭.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/08/11.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include<iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

int N, K;
int W[101] = {0,};
int V[101] = {0,};
int DP[101][100001];

void dp(){
    
    for(int limit = 1; limit<=K; limit++){
        for(int row = 1; row<=N; row++){
            //1. 담을 수 없을 경우
            if(W[row] > limit){
                DP[row][limit] = DP[row-1][limit];
            }
            //2. 담을 수 있는 경우
            else{
                DP[row][limit] = max(DP[row-1][limit - W[row]] + V[row]  ,  DP[row-1][limit]);
            }
        }
    }
    
}

int main(){

    cin >> N >> K;
    for(int i = 1; i<=N; i++){
        cin >> W[i] >> V[i];
    }
    
	//초기화
    for(int r=0; r<=N; r++)
    {
        DP[r][0] = 0;
    }
    for(int c = 0; c<=K; c++){
        DP[0][c] = 0;
    }

    dp();

    cout << DP[N][K];
    
    return 0;
}

문제 링크 : www.acmicpc.net/problem/11057

문제

오르막 수는 수의 자리가 오름차순을 이루는 수를 말한다. 이때, 인접한 수가 같아도 오름차순으로 친다.

예를 들어, 2234와 3678, 11119는 오르막 수이지만, 2232, 3676, 91111은 오르막 수가 아니다.

수의 길이 N이 주어졌을 때, 오르막 수의 개수를 구하는 프로그램을 작성하시오. 수는 0으로 시작할 수 있다.

입력

첫째 줄에 N (1 ≤ N ≤ 1,000)이 주어진다.

출력

첫째 줄에 길이가 N인 오르막 수의 개수를 10,007로 나눈 나머지를 출력한다.

접근 방법

dp[N][j] : N자리 수 중 j로 끝나는 수의 개수

로 정의하고 경우의 수를 아래 그림과 같이 나열해보니 쉽게 규칙을 찾을 수 있었다.

문제에서 수는 0으로 시작할 수 있다고 했으므로 이를 주의하자.

dp[1][0], dp[1][1],,, dp[1][9]는 모두 한 자리 수에 해당하므로 1로 초기화하고 N=2부터 dp를 구해준다.

#include <iostream>

using namespace std; 


int main() {

	int dp[1001][10];
	for (int i = 0; i <= 1000; i++) {
		for (int j = 0; j <= 9; j++) {
			dp[i][j] = 0;
		}
	}

	for (int i = 0; i <= 9; i++) {
		dp[1][i] = 1;		//한자리수 초기화	
	}
	for (int i = 0; i <= 1000; i++) {
		dp[i][0] = 1;			//0으로 끝나는 오르막 수는 1개
	}

	for (int i = 2; i <= 1000; i++) {
		for (int j = 1; j <= 9; j++) {
			for (int k = 0; k <= j; k++) {
				dp[i][j] += dp[i - 1][k] % 10007;			//더할때마다 MOD 연산 수행
			}
		}
	}


	int N; 
	cin >> N;

	int ans = 0;
	for (int i = 0; i <= 9; i++) {
		ans += dp[N][i];
	}
	cout << ans % 10007;			//마지막 출력할 때도 MOD 연산 후 출력

	return 0;
}

이때 주의할 점은 ans += dp[N][i] % 10007을 하고 마지막에는 그냥 ans 만 출력하면 틀린 답이라고 나온다는 것이다.

(이론상 mod 연산은 분배법칙이 성립해서 (a mod m + b mod m) = (a+b)mod m 를 만족하는데 왜 틀린지 모르겠다.)

문제 링크 : www.acmicpc.net/problem/15990

문제

정수 4를 1, 2, 3의 합으로 나타내는 방법은 총 3가지가 있다. 합을 나타낼 때는 수를 1개 이상 사용해야 한다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.

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

정수 n이 주어졌을 때, n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, 정수 n이 주어진다. n은 양수이며 100,000보다 작거나 같다.

출력

각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

접근 방법

문제의 조건에서 유의해야 할 점이 있다.

1) 1+3과 3+1 이 다름.

2) 같은 수를 두 번 이상 연속해서 사용할 수 없음.

일단 규칙을 찾기 위해 쭉 써보았다.

dp[1] = 1 (1)  (단일 숫자)

dp[2] = 1 (2) (단일 숫자)

dp[3] = dp[2]에 1을 더하는 경우 (2+1 -> 1가지)

          + dp[1]에 2를 더하는 경우 (1+2 -> 1가지)

          + dp[0]에 3을 더하는 경우 (0+3 -> 1가지)

          = 1 + 1 + 1 =3 

dp[4] = dp[3]에 1을 더하는 경우 (1+2+1 , 0+3+1 -> 연속 제외하고 2가지)

          + dp[2]에 2를 더하는 경우 (연속 제외하고 0가지)

          + dp[1]에 3을 더하는 경우 (1+3 -> 1가지)

          = 2 + 0 + 1 = 3

dp[5] = dp[4]에 1을 더하는 경우 (1+3+1 -> 연속 제외하고 1가지)

          + dp[3]에 2를 더하는 경우 (2+1+2, 0+3+2 -> 연속 제외하고 2가지)

          + dp[2]에 3을 더하는 경우 (2+3 -> 1가지)

          = 1 + 2 + 1 = 4

dp[6] = dp[5]에 1을 더하는 경우 (2+1+2+1, 0+3+2+1, 2+3+1 -> 연속 제외하고 3가지)

          + dp[4]에 2를 더하는 경우 (1+2+1+2, 0+3+1+2, 1+3+2 -> 3가지)

          + dp[3]에 3을 더하는 경우 (2+1+3, 1+2+3 -> 연속 제외하고 2가지)

          = 3 + 3 + 2 = 8

dp[7] = dp[6]에 1을 더하는 경우 (1+2+1+2+1, 0+3+1+2+1, 1+3+2+1  / 2+1+3+1, 1+2+3+1 -> 연속 제외하고 5가지)

          + dp[5]에 2를 더하는 경우 (1+3+1+2, 2+3+2 -> 연속 제외하고 2가지)

          + dp[4]에 3을 더하는 경우 (1+2+1+3, 0+3+1+3 -> 연속 제외하고 2가지)

          = 5 + 2 + 2 = 9

dp[n] = arr1[n] + arr2[n] + arr3[n] 으로 분할해서 더한다고 하자. (RHS의 각 배열은 +1, +2, +3 하는 경우이다.)

그러면

arr1[n] = arr2[n-1] + arr3[n-1]

arr2[n] = arr1[n-2] + arr3[n-2]

arr3[n] = arr1[n-3] + arr2[n-3] 

인 규칙을 찾을 수 있다. (위에 색칠해놓은 글씨를 보면 이해하기 쉽다.)

#include <iostream>

using namespace std;

long long dp[100001] = {0};
long long arr1[100001] = {0};
long long arr2[100001] = {0};
long long arr3[100001] = {0};


int main(){
    
        
    int TC; cin >> TC;

    arr1[3] = 1;    arr1[4] = 2;    arr1[5] = 1;
    arr2[3] = 1;    arr2[4] = 0;    arr2[5] = 2;
    arr3[3] = 1;    arr3[4] = 1;    arr3[5] = 1;
    
    dp[0] = 1; dp[1] = 1; dp[2] = 1;
    for(int i = 3; i<=5; i++) {dp[i] = (arr1[i] + arr2[i] + arr3[i]) % 1000000009;}
    
    for(int i = 6; i<=100000; i++){
        arr1[i] = (arr2[i-1] + arr3[i-1]) % 1000000009;
        arr2[i] = (arr1[i-2] + arr3[i-2]) % 1000000009;
        arr3[i] = (arr1[i-3] + arr2[i-3]) % 1000000009;
        dp[i] = (arr1[i] + arr2[i] + arr3[i]) % 1000000009;
    }
    
    
    for(int t = 0; t<TC; t++){
        
        int n;
        cin>>n;
        
        cout << dp[n] << "\n";
        
        
    }
    
    
    return 0;
}

주의할 점

int 형은 더할 때 범위가 넘어가므로 long long 자료형을 사용해야 한다.

그리고 for 문 안에서 arr1[], arr2[], arr3[] 을 구할 때도 Mod 연산을 적용해서 저장해야 한다. 

문제 링크 : www.acmicpc.net/problem/11052

문제

요즘 민규네 동네에서는 스타트링크에서 만든 PS카드를 모으는 것이 유행이다.

PS카드는 PS(Problem Solving)분야에서 유명한 사람들의 아이디와 얼굴이 적혀있는 카드이다. 각각의 카드에는 등급을 나타내는 색이 칠해져 있고, 다음과 같이 8가지가 있다.

• 전설카드
• 레드카드
• 오렌지카드
• 퍼플카드
• 블루카드
• 청록카드
• 그린카드
• 그레이카드

카드는 카드팩의 형태로만 구매할 수 있고, 카드팩의 종류는 카드 1개가 포함된 카드팩, 카드 2개가 포함된 카드팩, ... 카드 N개가 포함된 카드팩과 같이 총 N가지가 존재한다.

민규는 카드의 개수가 적은 팩이더라도 가격이 비싸면 높은 등급의 카드가 많이 들어있을 것이라는 미신을 믿고 있다. 따라서, 민규는 돈을 최대한 많이 지불해서 카드 N개 구매하려고 한다. 카드가 i개 포함된 카드팩의 가격은 Pi원이다.

예를 들어, 카드팩이 총 4가지 종류가 있고, P1 = 1, P2 = 5, P3 = 6, P4 = 7인 경우에 민규가 카드 4개를 갖기 위해 지불해야 하는 금액의 최댓값은 10원이다. 2개 들어있는 카드팩을 2번 사면 된다.

P1 = 5, P2 = 2, P3 = 8, P4 = 10인 경우에는 카드가 1개 들어있는 카드팩을 4번 사면 20원이고, 이 경우가 민규가 지불해야 하는 금액의 최댓값이다.

마지막으로, P1 = 3, P2 = 5, P3 = 15, P4 = 16인 경우에는 3개 들어있는 카드팩과 1개 들어있는 카드팩을 구매해 18원을 지불하는 것이 최댓값이다.

카드 팩의 가격이 주어졌을 때, N개의 카드를 구매하기 위해 민규가 지불해야 하는 금액의 최댓값을 구하는 프로그램을 작성하시오. N개보다 많은 개수의 카드를 산 다음, 나머지 카드를 버려서 N개를 만드는 것은 불가능하다. 즉, 구매한 카드팩에 포함되어 있는 카드 개수의 합은 N과 같아야 한다.

입력

첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000)

둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000)

출력

첫째 줄에 민규가 카드 N개를 갖기 위해 지불해야 하는 금액의 최댓값을 출력한다.

접근 방법 1) 

dfs로 풀었는데 역시 시간초과가 떴다 .

#include <iostream>
#include <vector>

using namespace std;

int N;
int P[1001] = {0};
vector<int> vec;
int maxSum = 0;

void dfs(int sum, int idx){
    
    if(sum>N) return;
    
    if(sum==N){
        int ans=0;
        for(int i=0; i<vec.size(); i++){
            ans += vec[i];
        }
        if(maxSum<ans){maxSum = ans;}
        
        
        return;
    }
    for(int i = 1; i<=N; i++){
        
        if(idx<=i){
            sum+=i;
            vec.push_back(P[i]);
            dfs(sum, i);
            sum-=i;
            vec.pop_back();
        }
    }
}

int main(){
    
    
   
    cin >> N;
    for(int i = 1; i<=N; i++){
        cin >> P[i];
    }
    dfs(0,0);
    cout << maxSum;
    
    
    
    return 0;
}

접근 방법 2)

 dp로 풀어야 시간 안에 문제를 풀 수 있을 것이다.

먼저 N = 3일 때, 어떤 카드팩 조합이 최대 금액이 될 것인가?

dp[n] 을 n개의 카드를 구매하는데에 필요한 최대 금액이라고 하자.

그러면 dp[3] 은 

dp[3-1] + P[1]

dp[3-2] + P[2] 

dp[3-3] + P[3]  (카드 팩 1개 통째로 사는 경우)

중 가장 큰 값이 될 것이다. 이는 아래와 같이 나타낼 수 있다. 

for(int j = 1; j<=i; j++){

      dp[i] = max(dp[i], dp[i-j] + P[j]);

}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N;
int P[1001] = {0};
int dp[1001] = {0};
vector<int> vec;
int maxSum = 0;



int main(){
    
    cin >> N;
    for(int i = 1; i<=N; i++){
        cin >> P[i];
    }

    dp[0] = 0;
    dp[1] = P[1];
    
    for(int i = 2; i<=N; i++){
        for(int j = 1; j<=i; j++){
            dp[i] = max(dp[i], dp[i-j] + P[j]);
        }
    }
    
    cout<<dp[N];
    
    return 0;
}