더 이상 물러설 곳이 없다

www.acmicpc.net/problem/2225

문제

0부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수를 구하는 프로그램을 작성하시오.

덧셈의 순서가 바뀐 경우는 다른 경우로 센다(1+2와 2+1은 서로 다른 경우). 또한 한 개의 수를 여러 번 쓸 수도 있다.

입력

첫째 줄에 두 정수 N(1 ≤ N ≤ 200), K(1 ≤ K ≤ 200)가 주어진다.

출력

첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다.

예제 입력 1

20 2

예제 출력 1

21

풀이 .

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

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        int[][] dp = new int[n + 1][k + 1];

        dp[0][0] = 1;
        for(int i = 0; i <= n; i++) {
            for (int j = 1; j <= k; j++) {
                for (int m = 0; m <= i; m++) {
                    dp[i][j] += dp[i - m][j - 1];
                    dp[i][j] %= 1000000000;
                }
            }
        }
        System.out.println(dp[n][k]);
    }
}

점화식을 도출하는 과정이 codeung.tistory.com/124 와 비슷한 느낌이다.

결국 이것도 못 풀고 정답코드를 확인했다..

dp[n][k] = 숫자 n을 숫자 k개의 조합으로 만들 수 있는 경우의 수 (k개의 숫자들을 더한 결과가 n이 되는 경우의 수)

n = ? + ? + ? + ... + m 에서 점화식을 유도할 수 있다.

dp[n][k] = dp[n - m][k - 1] (0 <= m <= n 의 모든 m에 대한 값을 더한 것이 dp[n][k]가 된다.)

n은 1~200인데 i 반복은 0부터 시작하는 이유?

[0][1]~[0][k] 를 먼저 구해놔야 다음 반복의 점화식에서 사용할 수 있다.

[0][1]~[0][k] 는 어차피 전부 1이니까 (0만 k개 더하는 경우) 좀 더 명확하게 알아보기 위해 초기화용 반복을 따로 돌리고 본 반복은 i = 1 부터 시작하는 것도 방법이다.

O(k*n^2) 의 시간으로 정답을 구할 수 있다.

너무.. 어렵다.....

www.acmicpc.net/problem/9461

문제

오른쪽 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.

파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.

N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)

출력

각 테스트 케이스마다 P(N)을 출력한다.

예제 입력 1

2

6

12

예제 출력 1

3

16

풀이 .

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 T = Integer.parseInt(br.readLine());
        while(T-- > 0) {
            int n = Integer.parseInt(br.readLine());
            long[] dp = new long[101];
            dp[1] = 1;
            dp[2] = 1;
            dp[3] = 1;
            dp[4] = 2;
            dp[5] = 2;
            for(int i = 6; i <= n; i++) {
                dp[i] = dp[i-1] + dp[i-5];
            }
            System.out.println(dp[n]);
        }
    }
}

그림을 따라가다보면 dp[n] = dp[n-1] + dp[n-5] 의 규칙을 찾을 수 있다.

다 풀어놓고 자료형이 안 맞아서 틀렸습니다를 받아 왜인지 한참을 고민했다.

DP문제를 풀 때는 long을 "항상" 고려하자

www.acmicpc.net/problem/2133

문제

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

입력

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

출력

첫째 줄에 경우의 수를 출력한다.

예제 입력 1 복사

2

예제 출력 1 복사

3

힌트

아래 그림은 3×12 벽을 타일로 채운 예시이다.

풀이 1. (틀린 코드)

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());
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 0;
        for(int i = 2; i <= n; i++) {
            if(i == 2) {
                dp[i] = 3;
                continue;
            }
            if(i % 2 == 1) {
                dp[i] = 0;
                continue;
            }
            dp[i] = dp[i-2] * 3 + dp[i-4] * 2;
        }
        System.out.println(dp[n]);
    }
}

일단 n이 홀수인 경우는 절대로 타일을 다 채울 수 없다.

i = 2, 3 일 때는 조건문으로 따로 처리하고 4부터 반복이 제대로 돌게 했다.

i 번째로 올 수 있는 경우가 i-2, i-4 두 가지 경우만 있을 거라고 생각했는데, 이게 잘못된 생각이었다.

거의 다 온 거였는데.. 아쉽다.

풀이 2. (정답 코드)

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());
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 0;
        for(int i = 2; i <= n; i++) {
            dp[i] = dp[i-2] * 3;
            for(int j = i - 4; j >= 0; j-=2) {
                dp[i] += dp[j] * 2;
            }
        }
        System.out.println(dp[n]);
    }
}

i 번째에 도달할 수 있는 경우

1. i-2번째에서 3가지 경우 존재

2. i-4 부터 -2씩 반복하며 0이 될 때까지 2가지씩 계속 존재

www.acmicpc.net/problem/1699

문제

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

입력

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

출력

주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.

예제 입력 1

7

예제 출력 1

4

풀이 1. (틀린 코드)

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());
        int cnt = 0;
        while(n > 0) {
            int temp = (int)Math.sqrt(n);
            n -= Math.pow(temp, 2);
            cnt += 1;
        }
        System.out.println(cnt);
    }
}

DP 문제인 걸 알면서도 방법을 떠올리지 못해 수학으로 풀었다.

큰 제곱수부터 하나씩 빼가면 될 거라고 생각했는데 반례에 걸렸다.

ex ) 18 = 9^2 + 9^2 -> 2개, (코드에서는 16 + 1 + 1 으로 3개 나옴)

풀이 2. (정답 코드)

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());

        int[] dp = new int[n + 1];
        dp[0] = 0;
        for(int i = 1; i <= n; i++) {
            dp[i] = i;
            for(int j = 1; j*j <= i; j++) {
                if(dp[i] > dp[i - j*j] + 1) {
                    dp[i] = dp[i - j*j] + 1;
                }
            }
        }
        System.out.println(dp[n]);
    }
}

혼자 힘으로 풀지 못해 정답 코드를 확인했다.

이런식으로 수식을 조금씩 가지고 놀아야 하는 문제는 도저히 감을 못 잡겠다.

dp[n] = n을 표현하는 제곱수의 합의 최소 항의개수

?^2 + ?^2 + ?^2 + ... + j^2 = i

j^2 <= i

즉, dp[i] = min(dp[i - j^2]) + 1 (위의 수식에서 j^2를 제외한 좌항의 나머지 총합이 i-j^2 이므로 dp[i - j^2]. 거기다 j^2에 해당하는 1 더함)

j의 범위 1~루트i 안에서 dp[i - j^2] 가 최소가 되는 j를 찾는다.

www.acmicpc.net/problem/2579

문제

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

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

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

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

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

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

입력

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

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

출력

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

예제 입력 1

6

10

20

15

25

10

20

예제 출력 1

75

풀이 .

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());
        int[] arr = new int[n + 1];
        int[][] dp = new int[n + 1][3];
        for(int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(br.readLine());
        }

        dp[1][1] = arr[1];
        dp[1][2] = 0;
        for(int i = 2; i <= n; i++) {
            dp[i][1] = Math.max(dp[i-2][1], dp[i-2][2]) + arr[i];
            dp[i][2] = dp[i-1][1] + arr[i];
        }
        int ans = Math.max(dp[n][1], dp[n][2]);
        System.out.println(ans);
    }
}

1칸 뛰기, 2칸 뛰기 가능

연속된 3칸 오르기 불가능

n번째 계단은 반드시 밟아야 한다. 선택할 수 있는 경우는 두 개.

1. n번째 계단을 1번 연속 밟는 경우

2. n번째 계단을 2번 연속 밟는 경우

(n번째 계단을 반드시 밟아야 하기 때문에 0번 연속으로 밟는 경우는 고려하지 않음)

1번 연속일 때,

이전 계단은 밟지 않았다는 소리. 즉, n-2에서 n으로 온 것. 

n-2번째 계단은 1번 연속일 수도, 2번 연속일 수도 있다.

dp[n][1] = Math.max(dp[n-2][1], dp[n-2][2]) + arr[n];

2번 연속일 때,

이전 계단을 반드시 밟았어야 함. 즉, n-1에서 n으로 온 것.

n-1번째 계단을 반드시 1번 연속으로 밟았어야 한다.

dp[n][2] = dp[n-1][1] + arr[n];

www.acmicpc.net/problem/1912

문제

n개의 정수로 이루어진 임의의 수열이 주어진다. 우리는 이 중 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합을 구하려고 한다. 단, 수는 한 개 이상 선택해야 한다.

예를 들어서 10, -4, 3, 1, 5, 6, -35, 12, 21, -1 이라는 수열이 주어졌다고 하자. 여기서 정답은 12+21인 33이 정답이 된다.

입력

첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다.

출력

첫째 줄에 답을 출력한다.

예제 입력 1

10

10 -4 3 1 5 6 -35 12 21 -1

예제 출력 1

33

예제 입력 2

10

2 1 -4 3 4 -4 6 5 -5 1

예제 출력 2

14

예제 입력 3

5

-1 -2 -3 -4 -5

예제 출력 3

-1

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.OptionalInt;
import java.util.StringTokenizer;

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());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        int[] dp = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        dp[0] = arr[0];
        for(int i = 1; i < n; i++) {
            dp[i] = Math.max(dp[i-1] + arr[i], arr[i]);
        }

        OptionalInt ans = Arrays.stream(dp).max();
        System.out.println(ans.getAsInt());
    }
}

DP문제 풀기 전 반드시 생각해볼 것

1. dp에 어떤 값을 담을 것인가?

2. dp에 들어갈 수 있는 경우의 수는?

3. 각 경우의 수가 가능하기 위한 조건은?

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

1. dp에 어떤 값을 담을 것인가?

-> dp[n] = arr[n]으로 끝나는 최대 부분합 

2. dp에 들어갈 수 있는 경우의 수는?

-> 이전 부분합을 이어나가는 경우, 새로운 부분합을 시작하는 경우 (어쨌든 arr[n]은 포함되어야 한다)

3. 각 경우의 수가 가능하기 위한 조건은?

-> 두 경우 중 더 큰 값을 선택해야 한다.

www.acmicpc.net/problem/11054

문제

수열 S가 어떤 수 Sk를 기준으로 S1 < S2 < ... Sk-1 < Sk > Sk+1 > ... SN-1 > SN을 만족한다면, 그 수열을 바이토닉 수열이라고 한다.

예를 들어, {10, 20, 30, 25, 20}과 {10, 20, 30, 40}, {50, 40, 25, 10} 은 바이토닉 수열이지만,  {1, 2, 3, 2, 1, 2, 3, 2, 1}과 {10, 20, 30, 40, 20, 30} 은 바이토닉 수열이 아니다.

수열 A가 주어졌을 때, 그 수열의 부분 수열 중 바이토닉 수열이면서 가장 긴 수열의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 부분 수열 중에서 가장 긴 바이토닉 수열의 길이를 출력한다.

예제 입력 1

10

1 5 2 1 4 3 4 5 2 1

예제 출력 1

7

풀이 .

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

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());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        int[] dp1 = new int[n];  // 가장 긴 증가 부분수열
        int[] dp2 = new int[n];  // 가장 긴 감소 부분수열
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        dp1[0] = 1;
        for(int i = 1; i < n; i++) {
            dp1[i] = 1;
            for(int j = 0; j < i; j++) {
                if(arr[i] > arr[j] && dp1[j] + 1 > dp1[i]) {
                    dp1[i] = dp1[j] + 1;
                }
            }
        }

        dp2[n-1] = 1;
        for(int i = n-2; i >= 0; i--) {
            dp2[i] = 1;
            for(int j = i+1; j < n; j++) {
                if(arr[i] > arr[j] && dp2[j] + 1 > dp2[i]) {
                    dp2[i] = dp2[j] + 1;
                }
            }
        }

        int ans = 0;
        for(int i = 0; i < n; i++) {
            if(dp1[i] + dp2[i] > ans) {
                ans = dp1[i] + dp2[i];
            }
        }
        ans -= 1;
        System.out.println(ans);
    }
}

1. 가장 긴 증가하는 부분수열을 구한다.

2. 가장 긴 감소하는 부분수열을 구한다.

3. 가장 길게 이어붙일 수 있는 끝점을 찾는다.

기존에 "가장 긴 감소하는 부분수열" 문제를 풀었을때는 0번 인덱스부터 내림차순으로 구해서 풀었다.

그런데 이렇게 구하면 3번을 진행할 수가 없다.

[n-1]인덱스부터 거꾸로 가장 긴 증가하는 부분수열을 찾아서 가장 긴 감소하는 부분수열을 찾으면 3번을 진행할 수 있다.

www.acmicpc.net/problem/11722

문제

수열 A가 주어졌을 때, 가장 긴 감소하는 부분 수열을 구하는 프로그램을 작성하시오.

예를 들어, 수열 A = {10, 30, 10, 20, 20, 10} 인 경우에 가장 긴 감소하는 부분 수열은 A = {10, 30, 10, 20, 20, 10}  이고, 길이는 3이다.

입력

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

둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ Ai ≤ 1,000)

출력

첫째 줄에 수열 A의 가장 긴 감소하는 부분 수열의 길이를 출력한다.

예제 입력 1

6

10 30 10 20 20 10

예제 출력 1

3

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.OptionalInt;
import java.util.StringTokenizer;

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());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] arr = new int[n];
        int[] dp = new int[n];
        for(int i = 0; i < n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        dp[0] = 1;
        for(int i = 1; i < n; i++) {
            dp[i] = 1;
            for(int j = 0; j < i; j++) {
                if(arr[j] > arr[i] && dp[j] + 1 > dp[i]) {
                    dp[i] = dp[j] + 1;
                }
            }
        }

        OptionalInt ans = Arrays.stream(dp).max();
        System.out.println(ans.getAsInt());
    }
}

codeung.tistory.com/118?category=449370 와 비슷한 문제.

dp[n] = "n번째 수로 끝나는 부분수열 중 가장 긴 것의 길이"

n번째 수로 끝나는 부분수열에서는 n번째 수가 마지막 수이기 때문에 dp[n]을 구하기 위해선 dp[n-1] 까지만 살펴보면 된다.

감소하는 부분수열을 유지하려면 arr[n]로 끝나는 부분수열에서 arr[n] 앞에 올 수 있는 숫자는 반드시 arr[n]보다 커야 한다.

즉, [0]~[n-1] 중에서 arr[n] 보다 큰 숫자만 검사하면 된다.

arr[n]보다 큰 인덱스를 대상으로 dp[0]~dp[n-1]을 검사한다. arr[n]을 추가해서 arr[n]으로 끝나는 부분수열을 완성했을 때 최장길이가 되기 위해선 dp[n 이전의 인덱스] + 1 은 dp[n] 의 현재값보다 더 커야 한다. 

위 검사를 arr[0]~arr[n-1] 중 arr[n] 보다 큰 놈들에게만 수행하여 dp[n] 값을 갱신하면 된다.