학습용 공간

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());
        for (int i=0;i<n;i++) {
            String[] temp = br.readLine().split(" ");
            int M = Integer.parseInt(temp[0]);
            int N = Integer.parseInt(temp[1]);
            int x = Integer.parseInt(temp[2]);
            int y = Integer.parseInt(temp[3]);
            int ans = caing(M, N, x, y);
            System.out.println(ans);
        }
    }
    // 브루트 포스
    // N과 M의 최대값은 각 4만이므로 최다 경우의 수는 N*M인 16억이다.
    // 1억개의 경우의 수가 1초가 걸린다는 것을 감안하면 모든 경우의 수를 고려하기에는 경우가 너무 많다.
    // 그러므로 고려할 필요가 없는 경우들은 건너뛰면서 경우들을 고려한다.
    // 예를 들어 x=2이고 M=10이라면 x=2인 경우는 10의 주기로 등장한다.
    // (2, y), (3, y), ... , (1, y), (2, y)
    // 그러므로 x 값의 M 값을 주기로 하여 확인하고, y값은 그렇게 확인한 경우들 중 입력 값과 일치하는 값을 찾으면 된다.
    // 위로 도출된 경우의 수들은 총 N개이다.
    // 이 방법을 통해 O(M*N)이였던 시간복잡도는 O(N)으로 줄일 수 있다.
    // (N이 더 작은 경우에는 y 값을 N주기로 경우의 수를 처리하도록하면 O(M)으로 만들 수도 있다.)
    static int caing(int m, int n, int x, int y) {
        if (m < n) {
            for (int k=x;k<(n*m); k+=m) {
                int temp = k%n;
                if (temp == 0) temp = n;
                if (temp == y) {
                    return k;
                }
            }
        } else { // m > n
            for (int k=y;k<(n*m); k+=n) {
                int temp = k%m;
                if (temp == 0) temp = m;
                if (temp == x) {
                    return k;
                }
            }
        }
        return -1;
    }
}

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

import java.util.*;

public class Main {
    static int[][] value;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt(); // 세로크기(행)
        int M = sc.nextInt(); // 가로크기(열)
        value = new int[N][M];
        // 각 칸의 값 받아서 2차월 배열에 저장
        for (int i=0;i<N;i++) {
            for (int j=0;j<M;j++) {
                value[i][j] = sc.nextInt();
            }
        }
        // 브루트 포스
        // 테트로미노가 붙는 모든 경우의 수를 고려하여 최대값 도출
        // 5가지 모형의 테트로미노는 모두 19가지의 경우로 붙을 수 있다. (회전, 대칭 포함)
        // 경우의 수 : 어떤 테트로미노를 놓을지(19가지) * 어디에 놓을지(N*M가지) = 19*N*M가지
        // N과 M의 최대값은 500이므로 가장 많은 경우의 수는 19*500*500 = 4750000
        // 1억 가지의 경우의 수를 고려하는 것이(1가지 고려에 O(1)이라면) 1초가 걸린다는 것을 생각하면
        // 그렇게 많은 경우가 아니므로 브루트 포스 이용 가능.
        int ans = 0;
        for (int i=0;i<N;i++) {
            for (int j=0;j<M;j++) { // 모든 칸에 대해 검사 수행
                if (j+3 < M) {
                    int temp = value[i][j] + value[i][j+1] + value[i][j+2] + value[i][j+3];
                    if (ans < temp) ans = temp;
                }
                if (i+3 < N) {
                    int temp = value[i][j] + value[i+1][j] + value[i+2][j] + value[i+3][j];
                    if (ans < temp) ans = temp;
                }
                if (i+1 < N && j+2 < M) {
                    int temp = value[i][j] + value[i+1][j] + value[i+1][j+1] + value[i+1][j+2];
                    if (ans < temp) ans = temp;
                }
                if (i+2 < N && j+1 < M) {
                    int temp = value[i][j] + value[i][j+1] + value[i+1][j] + value[i+2][j];
                    if (ans < temp) ans = temp;
                }
                if (i+1 < N && j+2 < M) {
                    int temp = value[i][j] + value[i][j+1] + value[i][j+2] + value[i+1][j+2];
                    if (ans < temp) ans = temp;
                }
                if (i+2 < N && j-1 >= 0) {
                    int temp = value[i][j] + value[i+1][j] + value[i+2][j] + value[i+2][j-1];
                    if (ans < temp) ans = temp;
                }
                if (i-1 >= 0 && j+2 < M) {
                    int temp = value[i][j] + value[i][j+1] + value[i][j+2] + value[i-1][j+2];
                    if (ans < temp) ans = temp;
                }
                if (i+2 < N && j+1 < M) {
                    int temp = value[i][j] + value[i+1][j] + value[i+2][j] + value[i+2][j+1];
                    if (ans < temp) ans = temp;
                }
                if (i+1 < N && j+2 < M) {
                    int temp = value[i][j] + value[i][j+1] + value[i][j+2] + value[i+1][j];
                    if (ans < temp) ans = temp;
                }
                if (i+2 < N && j+1 < M) {
                    int temp = value[i][j] + value[i][j+1] + value[i+1][j+1] + value[i+2][j+1];
                    if (ans < temp) ans = temp;
                }
                if (i+1 < N && j+1 < M) {
                    int temp = value[i][j] + value[i][j+1] + value[i+1][j] + value[i+1][j+1];
                    if (ans < temp) ans = temp;
                }
                if (i-1 >= 0 && j+2 < M) {
                    int temp = value[i][j] + value[i][j+1] + value[i-1][j+1] + value[i-1][j+2];
                    if (ans < temp) ans = temp;
                }
                if (i+2 < N && j+1 < M) {
                    int temp = value[i][j] + value[i+1][j] + value[i+1][j+1] + value[i+2][j+1];
                    if (ans < temp) ans = temp;
                }
                if (i+1 < N && j+2 < M) {
                    int temp = value[i][j] + value[i][j+1] + value[i+1][j+1] + value[i+1][j+2];
                    if (ans < temp) ans = temp;
                }
                if (i+2 < N && j-1 >= 0) {
                    int temp = value[i][j] + value[i+1][j] + value[i+1][j-1] + value[i+2][j-1];
                    if (ans < temp) ans = temp;
                }
                if (j+2 < M) {
                    int temp = value[i][j] + value[i][j+1] + value[i][j+2];
                    if (i-1 >= 0) {
                        int temp2 = temp + value[i-1][j+1];
                        if (ans < temp2) ans = temp2;
                    }
                    if (i+1 < N) {
                        int temp2 = temp + value[i+1][j+1];
                        if (ans < temp2) ans = temp2;
                    }
                }
                if (i+2 < N) {
                    int temp = value[i][j] + value[i+1][j] + value[i+2][j];
                    if (j+1 < M) {
                        int temp2 = temp + value[i+1][j+1];
                        if (ans < temp2) ans = temp2;
                    }
                    if (j-1 >= 0) {
                        int temp2 = temp + value[i+1][j-1];
                        if (ans < temp2) ans = temp2;
                    }
                }
            }
        }
        System.out.println(ans);
    }
}

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

import java.util.*;

public class Main {
    static boolean[] brokenBtn = new boolean[10];
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int channel = sc.nextInt();
        int brokenNum = sc.nextInt();
        int ans = Math.abs(channel-100);
        for (int i=0;i<brokenNum;i++) {
            brokenBtn[sc.nextInt()] = true;
        }
        // 브루트 포스
        // <예외처리 목록>
        // 100번으로 이동은 숫자버튼 누를 필요 없다.
        // 101번으로 이동은 + 1번 누르는 것이 최소
        // 102번으로 이동은 + 2번 누르는 것이 최소
        // 99번으로 이동은 - 1번 누르는 것이 최소
        if (channel == 100) ans = 0;
        else if (channel == 101 || channel == 99) ans = 1;
        else if (channel == 102 || channel == 98) ans = 2;
        else if (channel == 103) ans = 3;
        else {
            // 고장나지 않은 숫자를 눌러서 접근할 수 있는 수 중 가장 가까운 수를 찾아야 함
            // 모든 채널에서 이동하려는 채널로 이동하는 모든 경우의 수를 찾기 (브루트 포스)
            for (int i=0;i<=1000000;i++) { // 최악의 경우 50만번 + 또는 -눌러야 하므로 100만까지 고려
                int temp = i;
                int pressNum = possible(temp); // 고장난 버튼을 포함하지 않는 채널이면 숫자버튼을 누르는 횟수 반환 그렇지 않으면 0 반환
                int plusMinus = Math.abs(channel-temp);
                if (pressNum>0) { // 해당 채널을 입력할 수 있다면
                    if (ans > plusMinus+pressNum) { // 더 적은 횟수로 이동 가능
                        ans = plusMinus+pressNum;
                    }
                }
            }
        }
        System.out.println(ans);
    }
    // 해당 채널이 고장난 버튼을 포함하는지 확인하는 함수
    // 고장난 버튼 포함하면 0 반환, 입력 가능하면 숫자 버튼 입력 횟수 출력
    static int possible(int num) {
        int n = num;
        if (num == 0) { // 0번 예외처리
            if (brokenBtn[0]) return 0;
            else return 1;
        }
        while (n>0) {
            if (brokenBtn[n%10]) return 0; // 고장난 버튼을 포함
            n/=10;
        }
        // 고장난 버튼 없이 입력이 가능한 경우
        return (int)(Math.log10(num)+1); // 자리수만큼 버튼 누르므로 자리수 출력
    }
}

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

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int E = sc.nextInt();
        int S = sc.nextInt();
        int M = sc.nextInt();

        int findE = 1;
        int findS = 1;
        int findM = 1;
        int year = 1;

        // 브루트 포스
        // 입력된 ESM 값이 나올 때까지 각 ESM 값을을 1에서부터 1씩 늘려가고
        // 그렇게 구한 year 값을 출력
        while (true) {
            if (findE == E && findS == S && findM == M) break;
            findE += 1;
            if (findE == 16) findE = 1;
            findS += 1;
            if (findS == 29) findS = 1;
            findM += 1;
            if (findM == 20) findM = 1;
            year+=1;
        }
        System.out.println(year);
    }
}

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

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