학습용 공간

import java.util.*;

public class Main {
    static char[][] candy;
    static int ans = 1;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int cnt = sc.nextInt();
        candy = new char[cnt][cnt];
        for (int i=0;i<cnt;i++) {
            candy[i] = sc.next().toCharArray();
        }
        // 브루트 포스
        // n^2개의 데이터를 입력받는데 n^2, 인접한 두 칸 고르기 = 4(n^2) (인전 -> 상하좌우 4가지 경우)
        // 그러나 첫 원소부터 오른쪽 또는 아래의 원소와 바꾸다보면 다음 원소에서의 위 또는 왼쪽 원소와 바꾸는 연산은 중복되는 연산이므로 수행할 필요가 없다.
        // 그러므로 각 원소마다 오른쪽과 아래의 원소만 교환하는 경우만 생각하면 된다. -> 2(n^2)
        // 바꾼 칸의 경우마다 가장 긴 연속 부분을 고르기 (행과 열 모두 탐색) -> 각 경우마다 2(n^2)만큼 걸림
        // 결과적으로 O(n^4) 걸림
        for (int i=0;i<cnt;i++) {
            for (int j=0;j<cnt;j++) {
                // 오른쪽과 교환
                if (j+1 < cnt) {
                    char temp = candy[i][j];
                    candy[i][j] = candy[i][j+1];
                    candy[i][j+1] = temp;
                    int len = findLen();
                    if (ans < len) ans = len;
                    // 원상복귀
                    candy[i][j+1] = candy[i][j];
                    candy[i][j] = temp;
                }
                // 아래쪽과 교환
                if (i+1 < cnt) {
                    char temp = candy[i][j];
                    candy[i][j] = candy[i+1][j];
                    candy[i+1][j] = temp;
                    int len = findLen();
                    if (ans < len) ans = len;
                    // 원상복귀
                    candy[i+1][j] = candy[i][j];
                    candy[i][j] = temp;
                }
            }
        }
        System.out.println(ans);
    }
    static int findLen() {
        int n = candy.length;
        int len = 1;
        for (int i=0;i<n;i++) {
            // 행검사
            int temp = 1;
            for (int j=1;j<n;j++) {
                if (candy[i][j] == candy[i][j-1]) {
                    temp += 1;
                } else temp = 1;
                if (len < temp) len = temp;
            }
            // 열검사
            temp = 1;
            for (int j=1;j<n;j++) {
                if (candy[j][i] == candy[j-1][i]) {
                    temp+=1;
                } else temp = 1;
                if (len < temp) len = temp;
            }
        }
        return len;
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] dwarf = new int[9];
        int sum = 0;
        for (int i=0;i<9;i++) {
            dwarf[i] = sc.nextInt();
            sum += dwarf[i];
        }
        Arrays.sort(dwarf);
        // 브루트 포스
        // 모든 경우의 수 : 9명 중에서 7명 뽑는 경우의 수 = 9C7 = 9C2 = 9*8/2 = 36
        // 36가지의 경우의 수 고려하면 됨.
        for (int i=0;i<9;i++) {
            for (int j=i+1;j<9;j++) {
                if (sum - dwarf[i] - dwarf[j] == 100) {
                    for (int k=0;k<9;k++) {
                        if (k == i || k == j) continue;
                        System.out.println(dwarf[k]);
                    }
                    System.exit(0); // 결과를 찾으면 추가 연산 시간을 줄이기 위해 강제 종료
                }
            }
        }
    }
}

문제 출처 : https://www.acmicpc.net/problem/2309

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int mod = 10007;
        int[][] A = new int[n][10]; // A[i][j] = 길이가 i이고 마지막 숫자가 j인 오르막수의 개수
        // Bottom-Up 방식
        // 점화식 : A[i][j] = A[i-1][0] + A[i-1][1] + ... A[i-1][j]
        for (int i=0;i<10;i++) A[0][i] = 1;
        for (int i=1;i<n;i++) {
            for (int j=0;j<10;j++) {
                for (int l=0;l<=j;l++) {
                    A[i][j] += A[i-1][j-l];
                    A[i][j] %= mod;
                }
            }
        }
        int temp = A[n-1][0];
        for (int i=1;i<10;i++) {
            temp += A[n-1][i];
            temp %= mod;
        }
        System.out.println(temp);
    }
}

문제 출처 : https://www.acmicpc.net/problem/11057

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int mod = 9901;
        int n = sc.nextInt();
        int [][] A = new int[3][n]; // A[0][n] = n번째 칸에 배치안하는 경우의 수, A[1][n] = n번째 칸의 왼쪽에 배치하는 경우의 수, A[0][n] = n번째 칸의 오른쪽에 배치하는 경우의 수
        // Bottom-Up
        // 점화식 : A[0][i] = A[0][i-1] + A[1][i-1] + A[2][i-1]
        //         A[1][i] = A[0][i-1] + A[2][i-1]
        //         A[2][i] = A[0][i-1] + A[1][i-1]
        A[0][0] = 1;
        A[1][0] = 1;
        A[2][0] = 1;
        for (int i=1;i<n;i++) {
            A[0][i] = A[0][i-1] + A[1][i-1] + A[2][i-1];
            A[1][i] = A[0][i-1] + A[2][i-1];
            A[2][i] = A[0][i-1] + A[1][i-1];
            A[0][i] %= mod;
            A[1][i] %= mod;
            A[2][i] %= mod;
        }
        int temp = (A[0][n-1] + A[1][n-1] + A[2][n-1])%mod;
        System.out.println(temp);
    }
}

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int cnt = sc.nextInt();
        int[][] costs = new int[cnt][3]; // i번째 집을 각 색으로 칠하는데 드는 비용 (0행은 Red, 1행은 Green, 2행은 Blue)
        int[][] A = new int[cnt][3]; // 1~n번째 집들을 각 색으로 칠하는데 드는 최소 비용 (0행은 Red, 1행은 Green, 2행은 Blue)
        for (int i=0;i<cnt;i++) {
            costs[i][0] = sc.nextInt();
            costs[i][1] = sc.nextInt();
            costs[i][2] = sc.nextInt();
        }
        // Bottom-Up 방식
        // 점화식 : A[i][0] = min(A[i-1][1], A[i-1][2]) + costs[i][0]
        //         A[i][1] = min(A[i-1][0], A[i-1][2]) + costs[i][1]
        //         A[i][2] = min(A[i-1][0], A[i-1][1]) + costs[i][2]
        A[0][0] = costs[0][0];
        A[0][1] = costs[0][1];
        A[0][2] = costs[0][2];
        for (int i=1;i<cnt;i++) {
            // Red로 칠할 경우
            if (A[i-1][1] < A[i-1][2]) A[i][0] = A[i-1][1] + costs[i][0];
            else A[i][0] = A[i-1][2] + costs[i][0];
            // Green으로 칠할 경우
            if (A[i-1][0] < A[i-1][2]) A[i][1] = A[i-1][0] + costs[i][1];
            else A[i][1] = A[i-1][2] + costs[i][1];
            // Blue로 칠할 경우
            if (A[i-1][0] < A[i-1][1]) A[i][2] = A[i-1][0] + costs[i][2];
            else A[i][2] = A[i-1][1] + costs[i][2];
        }
        int min = A[cnt-1][0];
        for (int i=1;i<3;i++) {
            if (min > A[cnt-1][i]) min = A[cnt-1][i];
        }
        System.out.println(min);
    }
}

문제 출처 : https://www.acmicpc.net/problem/1149

import java.util.*;

public class Main {
    public static  void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int k = sc.nextInt();
        long[][] cases = new long[n+1][k+1]; // 0~n까지의 정수 k개를 더해서 그 합을 n으로 만드는 경우의 수
        long mod = 1000000000;
        // Bottom-Up 방식
        // 점화식 : cases[n][k] = cases[0][k-1] + cases[1][k-1] + ... + cases[n][k-1]
        cases[0][0] = 1;
        for (int i=1;i<=k;i++) {
            for (int j=0;j<=n;j++) {
                for (int l=0;l<=j;l++) {
                    cases[j][i] += cases[j-l][i-1];
                    cases[j][i] %= mod;
                }
            }
        }
        System.out.println(cases[n][k]);
    }
}

문제 출처 : https://www.acmicpc.net/problem/2225

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        int[] A = new int[num+1]; // A[i] = i를 제곱수로 나타냈을때, 필요한 항의 최소 개수

        // Bottom-Up 방식
        // 점화식 : A[i] = min(A[i-j*j] + 1) (1 <= j*j <= i)
        for (int i=0;i<num+1;i++) {
            if (i == 0) A[0] = 0;
            A[i] = i; // n를 제곱수로 표현한 최대 항의 개수는 모든 항을 1*1로 구성한 n개이다.
            for (int j=1;j*j<=i;j++) {
                if (A[i-j*j]+1 < A[i]) {
                    A[i] = A[i-j*j] + 1;
                }
            }
        }
        System.out.println(A[num]);
    }
}

문제 출처 : https://www.acmicpc.net/problem/1699

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int cnt = sc.nextInt();
        int[] numbers = new int[cnt]; // 입력받은 수들을 기록
        int[] sums = new int[cnt]; // 연속된 수의 합을 기록
        for (int i=0;i<cnt;i++) {
            numbers[i] = sc.nextInt();
        }

        // Bottom-Up 방식
        // 점화식 : sums[i] = max(sums[i-1] + numbers[i], numbers[i])
        sums[0] = numbers[0];
        for (int i=1;i<cnt;i++) {
            if (sums[i-1]+numbers[i] > numbers[i]) {
                sums[i] = sums[i-1] + numbers[i];
            } else {
                sums[i] = numbers[i];
            }
        }
        int max = sums[0];
        for (int i=1;i<cnt;i++) {
            if (max < sums[i]) max = sums[i];
        }
        System.out.println(max);
    }
}

문제 출처 : https://www.acmicpc.net/problem/1912

import java.util.Scanner;

public class Main {
    static int[] numbers;
    static int[] len;
    static int[] prexIndex;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int cnt = sc.nextInt();
        numbers = new int[cnt]; // 수열 담기
        len = new int[cnt]; // 수열의 각 수에 대한 가장 긴 증가하는 부분 수열의 길이
        prexIndex = new int[cnt]; // 가장 긴 증가하는 부분 수열의 직전의 수
        for (int i=0;i<cnt;i++) {
            numbers[i] = sc.nextInt();
        }
        // Bottom-Up 방식
        // A[i] = 수열의 i번째 수까지 주어졌을 때, 가장 긴 증가하는 부분 수열
        // 점화식 : A[i] = A[j] + 1, j = 수열의 i번째 수까지 주어졌을 때, 가장 긴 증가하는 부분 수열의 마지막 직전의 수가 위치하는 인덱스
        for (int i=0;i<cnt;i++) {
            len[i] = 1;
            prexIndex[i] = -1;
            for (int j=0;j<i;j++) {
                if (numbers[j] < numbers[i] && len[i] < len[j]+1) {
                    len[i] = len[j] + 1;
                    prexIndex[i] = j;
                }
            }
        }
        int maxLen = len[0];
        int maxLenIndex = 0;
        for (int i=0;i<cnt;i++) {
            if (maxLen < len[i]) {
                maxLen = len[i];
                maxLenIndex = i;
            }
        }
        System.out.println(maxLen);
        go(maxLenIndex);
        System.out.println();
    }

    public static void go(int p) {
        if (p == -1) {
            return;
        }
        go(prexIndex[p]);
        System.out.print(numbers[p] + " ");
    }
}

Bottom-Up 형식으로 구현함

Bottom-Up방식으로 구현

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int cnt = sc.nextInt();
        int[] numbers = new int[cnt+1]; // 수열 담기
        int[] len = new int[cnt+1]; // 수열의 각 수에 대한 가장 긴 증가하는 부분 수열의 길이
        int maxLen = 0;
        for (int i=0;i<cnt;i++) {
            numbers[i+1] = sc.nextInt();
        }
        // Bottom-Up 방식
        // A[i] = 수열의 i번째 수까지 주어졌을 때, 가장 긴 증가하는 부분 수열
        // 점화식 : A[i] = A[j] + 1, j = 수열의 i-1번째 수까지 주어졌을 때, 가장 긴 증가하는 부분 수열의 마지막 수가 위치하는 인덱스
        for (int i=0;i<cnt+1;i++) {
            for (int j=0;j<i;j++) {
                if (numbers[j] < numbers[i] && len[i] < len[j]+1) {
                    len[i] = len[j] + 1;
                    if (maxLen < len[i]) {
                        maxLen = len[i];
                    }
                }
            }
        }
        System.out.println(maxLen);
    }
}

문제 출처 : https://www.acmicpc.net/problem/11053

1. Top-Down 방식

import java.util.*;

public class Main {
    static long A[][]; // n자리의 이친수의 개수를 저장하는 배열
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        A = new long[num+1][2];
        pinaryNum(num);
        System.out.println(A[num][0] + A[num][1]);
    }

    public static void pinaryNum(int n) {
        // Top-Down 방식
        // A[i][j] = 마지막 자리 숫자가 j인 i자리 이친수의 개수
        // 점화식 : A[n] = A[n][0] + A[n][1]
        //         A[n][0] = A[n-1][0] + A[n-1][1] (0은 0 또는 1 모두 앞에 올 수 있음)
        //         A[n][1] = A[n-1][0] (1은 0 앞에만 올 수 있음)
        // 이전 자리수가 0으로 끝나면 0또는 1 두가지 경우가 올 수 있지만
        // 전 자리수가 1로 끝나면 0밖에 올 수 없다. (한가지 경우만 존재) (끝에 10을 하나로 묶어서 생각할 수 있다 -> A[n-2]에 붙인다고 생각)
        if (n < 2) {
            A[1][1] = 1;
            return;
        }
        if (A[n-1][0] == 0 && A[n-1][1] == 0) {
            pinaryNum(n-1);
        }
        A[n][0] = A[n-1][0] + A[n-1][1];
        A[n][1] = A[n-1][0];
    }
}

2. Bottom-Up 방식

import java.util.*;

public class Main {
    static long A[][]; // n자리의 이친수의 개수를 저장하는 배열
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        A = new long[num+1][2];
        pinaryNum(num);
        System.out.println(A[num][0] + A[num][1]);
    }

    public static void pinaryNum(int n) {
        // Bottom-Up 방식
        // A[i][j] = 마지막 자리 숫자가 j인 i자리 이친수의 개수
        // 점화식 : A[n] = A[n][0] + A[n][1]
        //         A[n][0] = A[n-1][0] + A[n-1][1] (0은 0 또는 1 모두 앞에 올 수 있음)
        //         A[n][1] = A[n-1][0] (1은 0 앞에만 올 수 있음)
        A[1][1] = 1;
        for (int i=2;i<n+1;i++) {
            A[i][0] = A[i-1][0] + A[i-1][1];
            A[i][1] = A[i-1][0];
        }
    }
}

# memorization을 일차원 배열로 해결하기 - 이친수 문제는 고려할 경우의 수가 0 또는 1로 두가지 밖에 없으므로 1차원 배열로도 다이나믹 프로그래밍을 수행할 수 있다.

1. Top-Down

import java.util.*;

public class Main {
    static long A[]; // n자리의 이친수의 개수를 저장하는 배열 (일차원 배열로 해결하기
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        A = new long[num+1];
        pinaryNum(num);
        System.out.println(A[num]);
    }

    public static void pinaryNum(int n) {
        // Bottom-Up 방식
        // A[i][j] = 마지막 자리 숫자가 j인 i자리 이친수의 개수
        // 점화식 : A[n] = A[n-1] + A[n-2]
        //         A[n-1] : 전 이진수가 0으로 끝나는 경우 -> 마지막 자리에 0, 1 모두 올 수 있음
        //         A[n-2] : 전 이진수가 1로 끝나는 경우 -> 마지막 자리에 0 밖에 올 수 없음
        //                  01을 한 묶음으로 생각해서 A[n-2]에 01을 추가한 경우를 생각하면 됨
        if (n < 2) {
            A[1] = 1;
            return;
        }
        if (A[n-1] == 0) {
            pinaryNum(n-1);
        }
        A[n] = A[n-1] + A[n-2];
    }
}

2. Bottom-Up

import java.util.*;

public class Main {
    static long A[]; // n자리의 이친수의 개수를 저장하는 배열 (일차원 배열로 해결하기
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        A = new long[num+1];
        pinaryNum(num);
        System.out.println(A[num]);
    }

    public static void pinaryNum(int n) {
        // Bottom-Up 방식
        // A[i][j] = 마지막 자리 숫자가 j인 i자리 이친수의 개수
        // 점화식 : A[n] = A[n-1] + A[n-2]
        //         A[n-1] : 전 이진수가 0으로 끝나는 경우 -> 마지막 자리에 0, 1 모두 올 수 있음
        //         A[n-2] : 전 이진수가 1로 끝나는 경우 -> 마지막 자리에 0 밖에 올 수 없음
        //                  01을 한 묶음으로 생각해서 A[n-2]에 01을 추가한 경우를 생각하면 됨
        A[1] = 1;
        for (int i=2;i<n+1;i++) {
            A[i] = A[i-1] + A[i-2];
        }
    }
}

Bottom-Up 방식으로 해결

import java.util.*;

public class Main {
    static long mod = 1000000000;
    static long[][] A;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int num = sc.nextInt();
        A = new long[num+1][10];
        stairNum(num);
        long temp = 0;
        for (int i=0;i<10;i++) {
            temp += A[num][i];
        }
        temp %= mod;
        System.out.println(temp);
    }

    static void stairNum(int n) {
        // Bottom-Up 방식
        // A[i][j] = 길이가 i이고 마지막 숫자가 j인 계단 수의 개수
        // 점화식 : D[i][j] = D[i-1][j-1] + D[i-1][j+1];
        for (int i=1;i<10;i++) {
            A[1][i] = 1;
        }
        for (int i=2;i<n+1;i++) {
            for (int j=0;j<10;j++) {
                A[i][j] = 0;
                if (j-1 >= 0) { // +1로 연속이려면 직전 마지막 수가 0과 같거나 커야함 (음수 나올 수 없기 때문)
                    A[i][j] += A[i-1][j-1];
                }
                if (j+1 <= 9) { // -1로 연속이려면 직전 마지막 수가 9와 같거나 작아야 함
                    A[i][j] += A[i-1][j+1];
                }
                A[i][j] %= mod;
            }
        }
    }
}