개발 블로그

문제 링크 : 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/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/2748

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 90보다 작거나 같은 자연수이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

접근 방법

처음에는 재귀 함수로 풀었는데 시간 초과가 났다.

그래서 DP로 풀었는데 dp[]의 자료형을 int 형으로 지정해서 오답으로 처리됐다. F(90) = 2,880,067,194,370,816,120 이므로 dp[]는  long long 형으로 선언해줘야한다. 

F(45) = 1836311903
F(46) = 2971215073
이므로 n = 46부터 int형 범위를 넘어간다. 

* long long(8byte) : –9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 
* long (4byte) : –2,147,483,648 ~ 2,147,483,647

의문) long형으로 선언해도 백준은 정답으로 처리돼서 테스트케이스에 n=90이 없나 싶었는데,

         VsCode에서도 F(90)이 정상적으로 출력된다. 이론상으로는 long long 이 맞는데 정답 처리 되는 이유를 잘 모르겠다.

#include <iostream>
using namespace std;

long long dp[91]={0,};

int main()
{
    int n; cin >> n;
    
    dp[0] = 0; dp[1] = 1;
    for(int i = 2; i<=n; i++){
        dp[i] = dp[i-1] + dp[i-2];
    }

    cout << dp[n];
    return 0;
}

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

문제

유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다.

오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다.

파이프는 회전시킬 수 있으며, 아래와 같이 3가지 방향이 가능하다.

파이프는 매우 무겁기 때문에, 유현이는 파이프를 밀어서 이동시키려고 한다. 벽에는 새로운 벽지를 발랐기 때문에, 파이프가 벽을 긁으면 안 된다. 즉, 파이프는 항상 빈 칸만 차지해야 한다.

파이프를 밀 수 있는 방향은 총 3가지가 있으며, →, ↘, ↓ 방향이다. 파이프는 밀면서 회전시킬 수 있다. 회전은 45도만 회전시킬 수 있으며, 미는 방향은 오른쪽, 아래, 또는 오른쪽 아래 대각선 방향이어야 한다.

파이프가 가로로 놓여진 경우에 가능한 이동 방법은 총 2가지, 세로로 놓여진 경우에는 2가지, 대각선 방향으로 놓여진 경우에는 3가지가 있다.

아래 그림은 파이프가 놓여진 방향에 따라서 이동할 수 있는 방법을 모두 나타낸 것이고, 꼭 빈 칸이어야 하는 곳은 색으로 표시되어져 있다.

가로

세로

대각선

가장 처음에 파이프는 (1, 1)와 (1, 2)를 차지하고 있고, 방향은 가로이다. 파이프의 한쪽 끝을 (N, N)로 이동시키는 방법의 개수를 구해보자.

입력

첫째 줄에 집의 크기 N(3 ≤ N ≤ 32)이 주어진다. 둘째 줄부터 N개의 줄에는 집의 상태가 주어진다. 빈 칸은 0, 벽은 1로 주어진다. (1, 1)과 (1, 2)는 항상 빈 칸이다.

출력

첫째 줄에 파이프의 한쪽 끝을 (N, N)으로 이동시키는 방법의 수를 출력한다. 이동시킬 수 없는 경우에는 0을 출력한다.

접근 방법

파이프 옮기기1번(https://nanyoungkim.tistory.com/183)

과 문제는 같지만, N 최대값이 16에서 32로 커졌기 때문에 같은 코드로는 시간초과가 났다.

- DP와 삼차원 배열을 이용해서 해결해보자. 

- dp[i][r][c] : 파이프 방향이 i이고, 현재 파이프 끝의 위치가 [r][c]일때의 (1,2)부터 (r,c) 로 가는 방법의 수

step 1) 처음 시작 위치 초기화

dp[0][1][2] : 처음 초기 상태로 1을 저장한다.

step 2) 첫 줄 초기화

dp[0][1][3]부터 dp[0][1][N]은 (1,2)에서 시작해서 가로로 쭉 이동하는 경우밖에 없다. 쭉 이동하면서 1로 초기화 하되, 벽이 나타나면 가로로 더 이상 이동할 수 없으므로 중단한다. (벽 오른쪽은 모두 0 인 상태로 남게 됨)

stpe 3) dp 채우기

첫번째 줄은 채웠으니, 두번째 줄과 두번째 열부터 dp를 채운다.

이때 경우는 아래의 3가지로 나눌 수 있다. 

(이전위치) -> (현재 위치 & 현재 상태 가로일 때) : 현재(r,c) 상태가 가로이므로 이전 위치는 (r, c-1)이며, 이전 상태는 가로/대각선.

(이전위치) -> (현재 위치 & 현재 상태 세로일 때) : 현재(r,c) 상태가 세로이므로 이전 위치는 (r-1, c)이며, 이전 상태는 세로/대각선.

(이전위치) -> (현재 위치 & 현재 상태 대각선일 때): 현재(r,c) 상태가 대각선이므로 이전 위치는 (r-1,c-1)이며, 이전 상태는 가로/세로/대각선

이 세 경우를 코드로 표현하면 아래와 같다. 세번째 경우는 대각선으로 이동한 경우이므로 (r,c)의 위와 왼쪽도 벽이 아닌지 검사해야한다.

for (int r = 2; r <= N; r++)
    {
        for (int c = 2; c <= N; c++)
        {
            if (map[r][c] == 1)
                continue;

            //가로 -> 가로  , 대각선 -> 가로  : (r,c-1) -> (r,c)
            dp[0][r][c] = dp[0][r][c - 1] + dp[2][r][c - 1];

            //세로 -> 세로   , 대각선 -> 세로  : (r-1, c) -> (r,c)
            dp[1][r][c] = dp[1][r - 1][c] + dp[2][r - 1][c];

            //가로 -> 대각선, 세로 -> 대각선  , 대각선 ->대각선  : (r-1, c-0) -> (r,c)
            if (map[r - 1][c] != 1 && map[r][c - 1] != 1)
                dp[2][r][c] = dp[0][r - 1][c - 1] + dp[1][r - 1][c - 1] + dp[2][r - 1][c - 1];
        }
    }

전체 코드 

//
//  BF_BOJ17070_파이프옮기기2.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/08/12.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

#include <iostream>
using namespace std;

int N;
int map[33][33];
long dp[3][33][33];

int main()
{

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

    for (int col = 2; col <= N; col++)
    { //(1,2) 에서 오른쪽으로 가로로 쭉 이동
        if (map[1][col] == 1)
            break;
        else
            dp[0][1][col] = 1;
    }

    for (int r = 2; r <= N; r++)
    {
        for (int c = 2; c <= N; c++)
        {
            if (map[r][c] == 1)
                continue;

            //가로 -> 가로  , 대각선 -> 가로  : (r,c-1) -> (r,c)
            dp[0][r][c] = dp[0][r][c - 1] + dp[2][r][c - 1];

            //세로 -> 세로   , 대각선 -> 세로  : (r-1, c) -> (r,c)
            dp[1][r][c] = dp[1][r - 1][c] + dp[2][r - 1][c];

            //가로 -> 대각선, 세로 -> 대각선  , 대각선 ->대각선  : (r-1, c-0) -> (r,c)
            if (map[r - 1][c] != 1 && map[r][c - 1] != 1)
                dp[2][r][c] = dp[0][r - 1][c - 1] + dp[1][r - 1][c - 1] + dp[2][r - 1][c - 1];
        }
    }
    cout << dp[0][N][N] + dp[1][N][N] + dp[2][N][N];

    return 0;
}

참고(https://hbj0209.tistory.com/118)

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

문제

명우는 홍준이와 함께 팰린드롬 놀이를 해보려고 한다.

먼저, 홍준이는 자연수 N개를 칠판에 적는다. 그 다음, 명우에게 질문을 총 M번 한다.

각 질문은 두 정수 S와 E(1 ≤ S ≤ E ≤ N)로 나타낼 수 있으며, S번째 수부터 E번째 까지 수가 팰린드롬을 이루는지를 물어보며, 명우는 각 질문에 대해 팰린드롬이다 또는 아니다를 말해야 한다.

예를 들어, 홍준이가 칠판에 적은 수가 1, 2, 1, 3, 1, 2, 1라고 하자.

• S = 1, E = 3인 경우 1, 2, 1은 팰린드롬이다.
• S = 2, E = 5인 경우 2, 1, 3, 1은 팰린드롬이 아니다.
• S = 3, E = 3인 경우 1은 팰린드롬이다.
• S = 5, E = 7인 경우 1, 2, 1은 팰린드롬이다.

자연수 N개와 질문 M개가 모두 주어졌을 때, 명우의 대답을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열의 크기 N (1 ≤ N ≤ 2,000)이 주어진다.

둘째 줄에는 홍준이가 칠판에 적은 수 N개가 순서대로 주어진다. 칠판에 적은 수는 100,000보다 작거나 같은 자연수이다.

셋째 줄에는 홍준이가 한 질문의 개수 M (1 ≤ M ≤ 1,000,000)이 주어진다.

넷째 줄부터 M개의 줄에는 홍준이가 명우에게 한 질문 S와 E가 한 줄에 하나씩 주어진다.

출력

총 M개의 줄에 걸쳐 홍준이의 질문에 대한 명우의 답을 입력으로 주어진 순서에 따라서 출력한다. 팰린드롬인 경우에는 1, 아닌 경우에는 0을 출력한다.

접근 방법

처음에는 S, E를 입력할 때마다 양쪽에서 가운데 방향으로 대칭을 이루는지 검사했다. 그런데 이 방법은 시간초과가 났다.

시간을 줄이기 위해 효율적인 DP 로 해결해보았다. 다음과 같이 생각해보자.

s = 1, e = 5가 팰린드롬인지 알려면 다음 두가지 조건이 만족하는지 검사해보면 된다.

조건 1) arr[1]과 arr[5]가 같은가?

조건 2) arr[2] 부터 arr[4]가 팰린드롬인가?

즉, dp[s][e] 에 arr[i] ~ arr[i]가 팰린드롬인지를 저장한다고 했을 때,

if((arr[s] == arr[e])  &&  (dp[s+1][e-1] == true)) => dp[s][e] = true 가 된다.

#include <iostream>
#include <string>
#include <vector>

using namespace std;
int arr[2001] = {
    0,
};
int dp[2001][2001]; //dp[i][j] : arr[i] ~ arr[j] 가 팰린드롬 문자열인지 여부

int main()
{
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

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

    //dp[x][x]와  + 길이가 2인 팰린드롬 dp[i][i+1] 을 셋팅.
    for (int i = 1; i <= N - 1; i++)
    {
        dp[i][i] = 1; //dp[x][x] 는 항상 true 임
        if (arr[i] == arr[i + 1])
            dp[i][i + 1] = 1;
        else
            dp[i][i + 1] = 0;
    }
    dp[N][N] = 1;

    for (int len = 3; len <= N; len++)
    {

        for (int st = 1; st <= N - len + 1; st++)
        {
            //s = st, e = st+len-1
            if ((arr[st] == arr[st + len - 1]) && (dp[st + 1][st + len - 2]))
            {
                dp[st][st + len - 1] = 1;
            }
            else
                dp[st][st + len - 1] = 0;
        }
    }
    int M;
    cin >> M;
    int S, E;

    for (int i = 0; i < M; i++)
    {
        cin >> S >> E;
        cout << dp[S][E] << "\n";
    }

    return 0;
}

문제 링크 : 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/2579

문제

계단 오르기 게임은 계단 아래 시작점부터 계단 꼭대기에 위치한 도착점까지 가는 게임이다. <그림 1>과 같이 각각의 계단에는 일정한 점수가 쓰여 있는데 계단을 밟으면 그 계단에 쓰여 있는 점수를 얻게 된다.

예를 들어 <그림 2>와 같이 시작점에서부터 첫 번째, 두 번째, 네 번째, 여섯 번째 계단을 밟아 도착점에 도달하면 총 점수는 10 + 20 + 25 + 20 = 75점이 된다.

계단 오르는 데는 다음과 같은 규칙이 있다.

1. 계단은 한 번에 한 계단씩 또는 두 계단씩 오를 수 있다. 즉, 한 계단을 밟으면서 이어서 다음 계단이나, 다음 다음 계단으로 오를 수 있다.
2. 연속된 세 개의 계단을 모두 밟아서는 안 된다. 단, 시작점은 계단에 포함되지 않는다.
3. 마지막 도착 계단은 반드시 밟아야 한다.

따라서 첫 번째 계단을 밟고 이어 두 번째 계단이나, 세 번째 계단으로 오를 수 있다. 하지만, 첫 번째 계단을 밟고 이어 네 번째 계단으로 올라가거나, 첫 번째, 두 번째, 세 번째 계단을 연속해서 모두 밟을 수는 없다.

각 계단에 쓰여 있는 점수가 주어질 때 이 게임에서 얻을 수 있는 총 점수의 최댓값을 구하는 프로그램을 작성하시오.

입력

입력의 첫째 줄에 계단의 개수가 주어진다.

둘째 줄부터 한 줄에 하나씩 제일 아래에 놓인 계단부터 순서대로 각 계단에 쓰여 있는 점수가 주어진다. 계단의 개수는 300이하의 자연수이고, 계단에 쓰여 있는 점수는 10,000이하의 자연수이다.

출력

첫째 줄에 계단 오르기 게임에서 얻을 수 있는 총 점수의 최댓값을 출력한다.

접근 방법

1) 현재 계단을 밟지 않고 건너 뛰는 경우

2) 현재 계단을 밟는 경우

이렇게 두가지로 나눌 수 있다.

1)번의 경우에 계단의 합의 최대값은 직전의 최대값과 같다. 이 경우엔 현재 계단을 선택하지 않으므로 3개 연속 유무를 신경쓰지 않아도 된다.

2)번의 경우에 계단의 합의 최대값은, 현재 계단을 포함해서 3개 이상 연속되는 경우를 제외해야 한다. 그러므로 직전 계단에서 2개 이상 연속한 경우를 제외하고, 나머지 후보들을 비교해서 최대합을 찾으면 된다.

문제의 입력 예시를 보자.

6개의 계단 값은 10 20 15 25 10 20 이다.

벡터 배열안에 <합, 연속해서 밟은 계단 수> 를 저장했고, 저장할 때마다 합을 비교해서 마지막에 최대합을 dp[]에 저장했다.

벡터 배열 값을 보면 아래와 같다. 

10    vecArr[0] : <0,0>/  <10,1>  -> dp[0] = 10

20   vecArr[1] : <10,0> / <0+20, 1> <10+20, 2>  ->dp[1] = 30

15    vecArr[2] : <30,0> / <10+15, 1> <0+20+15,2>  ->dp[2] =  35

25   vecArr[3] : <35, 0> / <30+25, 1> <10+15+25, 2>  -> dp[3] = 55

10   vecArr[4] : <55,0> / <35+10, 1> <30+25+10, 2>  -> dp[4] = 65

20   vecArr[5] : <65,0> / <55+20, 1> <35+10+20, 2>  -> dp[5] = 75

//
//  DP_BOJ2579_계단오르기.cpp
//  Coding_Test_Practice
//
//  Created by 김난영 on 2021/04/11.
//  Copyright © 2021 KimNanyoung. All rights reserved.
//

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

using namespace std;

int stair[300] = {0};
int dp[300] = {0};
vector<pair<int,int>> vecArr[300];

int main(){
    
    int N; cin >> N;
    for(int i = 0; i<N; i++){
        cin >> stair[i];
    }
    
    //dp[0], dp[1] 초기화
    vecArr[0].push_back(make_pair(0,0));            //-1
    vecArr[0].push_back(make_pair(stair[0],1));     //0
    
    dp[0] = stair[0];
    
    vecArr[1].push_back(make_pair(dp[0], 0));               //0 x
    vecArr[1].push_back(make_pair(stair[1], 1));            //x 1
    vecArr[1].push_back(make_pair(stair[0] + stair[1], 2)); //0 1
    
    int maxi=0;
    for(int i = 0; i<3; i++){
        if(maxi<vecArr[1][i].first) maxi = vecArr[1][i].first;
    } dp[1] = maxi;
    
    
    
    for(int i = 2; i<=N-1; i++){
        
        //case 1 : 현재 계단 안 밟는 경우
        if(i!=N-1){     //문제의 조건에서 마지막 계단은 무조건 밟는다고 했음
            vecArr[i].push_back(make_pair(dp[i-1], 0));     //직전 계단까지 왔을 때 최대값
        }
        
        //case 2 : 현재 계단 밟는 경우
        int maxi = 0;
        for(int j = 0; j<vecArr[i-1].size(); j++){
            int conti = vecArr[i-1][j].second;
            if(conti==2) continue;                  //직전 계단까지 2개 연속해서 밟은 경우, 3개 연속 못 밟음
            
            int sum = stair[i] + vecArr[i-1][j].first;
            if(maxi < sum) maxi = sum;
            vecArr[i].push_back(make_pair(sum,conti+1));    //현재 계단 밟았으므로 연속해서 밟은 계단 수 1증가해서 저장
 
        }
        dp[i] = maxi;
        
    }
    cout << dp[N-1];
    
    return 0;
}