[BOJ] 14391. 종이 조각 (Java)

Problem

제출일 : 2020-03-14

문제 풀이 시간 : 1H 45M

난이도 : ★★★

---

link : https://www.acmicpc.net/problem/14391

영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. 행은 위에서부터 아래까지 번호가 매겨져 있고, 열은 왼쪽부터 오른쪽까지 번호가 매겨져 있다.

영선이는 직사각형을 겹치지 않는 조각으로 자르려고 한다. 각 조각은 크기가 세로나 가로 크기가 1인 직사각형 모양이다. 길이가 N인 조각은 N자리 수로 나타낼 수 있다. 가로 조각은 왼쪽부터 오른쪽까지 수를 이어 붙인 것이고, 세로 조각은 위에서부터 아래까지 수를 이어붙인 것이다.

아래 그림은 4×4 크기의 종이를 자른 한 가지 방법이다.

각 조각의 합은 493 + 7160 + 23 + 58 + 9 + 45 + 91 = 7879 이다.

종이를 적절히 잘라서 조각의 합을 최대로 하는 프로그램을 작성하시오.

Input

첫째 줄에 종이 조각의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 4)

둘째 줄부터 종이 조각이 주어진다. 각 칸에 쓰여 있는 숫자는 0부터 9까지 중 하나이다.

Output

영선이가 얻을 수 있는 점수의 최댓값을 출력한다.

Example

input

2 3
123
312

output

435

Solution & Inpression

조금 어려웠던 문제...

모든 경우의 수를 탐색해 최대값을 찾는 과정으로 문제를 푸려 생각을 했지만 모든 경우의 수를 어떻게 만들어야 할지 생각하기가 조금은 힘들었다.

N과 M이 최대 4로 각각의 칸이 종이의 가로 이거나 세로인 2가지 종류가 있기에 모든 경우의 수는 $2^{16}$이기 때문에 완전탐색이 가능했다.

2차원 배열을 1차원 배열로 만들어 인덱스 조작을 편하게 작업했다. r행 i열은 r*M + i로 표현할수 있다.

Code

언어 : JAVA

메모리 : 17152 kb

실행 시간 : 160 ms

import java.util.Scanner;

public class Main {
    static int N, M, ans;
    static int[] map;
    static boolean[] visit;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        M = sc.nextInt();

        map = new int[N * M];
        for (int i = 0; i < N; i++) {
            String str = sc.next();
            for (int j = 0; j < M; j++) {
                map[i * M + j] = str.charAt(j) - '0';
            }
        }

        visit = new boolean[N * M];
        ans = 0;
        solve(0);
        System.out.println(ans);
    }

    private static void solve(int idx) {
        if (idx == N * M) {
            check();
            return;
        }

        // 해당 좌표 선택(가로 선택)
        visit[idx] = true;
        solve(idx + 1);

        // 해당 좌표미선택(세로 선택)
        visit[idx] = false;
        solve(idx + 1);

    }

    private static void check() {
        int sum = 0, tmp = 0;

        // 가로
        for (int i = 0; i < N; i++) {
            tmp = 0;
            for (int j = 0; j < M; j++) {
                if (visit[i * M + j]) {
                    tmp *= 10;
                    tmp += map[i * M + j];
                } else {
                    sum += tmp;
                    tmp = 0;
                }
            }
            sum += tmp;
        }

        // 세로
        for (int j = 0; j < M; j++) {
            tmp = 0;
            for (int i = 0; i < N; i++) {
                if (!visit[i * M + j]) {
                    tmp *= 10;
                    tmp += map[i * M + j];
                } else {
                    sum += tmp;
                    tmp = 0;
                }
            }
            sum += tmp;
        }

        // 최대값 갱신
        ans = Math.max(ans, sum);
    }
}

[BOJ] 2580. 스도쿠 (Java)

Problem

제출일 : 2020-03-13

문제 풀이 시간 : 30M

난이도 : ★★

---

link : https://www.acmicpc.net/problem/2580

스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 몇 몇 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.

나머지 빈 칸을 채우는 방식은 다음과 같다.

1. 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
2. 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.

위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.

또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.

이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.

게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.

Input

아홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.

Output

모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.

스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.

Example

input

0 3 5 4 6 9 2 7 8
7 8 2 1 0 5 6 0 9
0 6 0 2 7 8 1 3 5
3 2 1 0 4 6 8 9 7
8 0 4 9 1 3 5 0 6
5 9 6 8 2 0 4 1 3
9 1 7 6 5 2 0 8 0
6 0 3 7 0 1 9 5 2
2 5 8 3 9 4 7 6 0

output

1 3 5 4 6 9 2 7 8
7 8 2 1 3 5 6 4 9
4 6 9 2 7 8 1 3 5
3 2 1 5 4 6 8 9 7
8 7 4 9 1 3 5 2 6
5 9 6 8 2 7 4 1 3
9 1 7 6 5 2 3 8 4
6 4 3 7 8 1 9 5 2
2 5 8 3 9 4 7 6 1

Solution & Inpression

N-Queen과 비슷한 백트래킹 유형의 문제

현재 위치에 값이 세로와 가로 3*3칸에 같은 값이 있다면 그 값은 넣을수 없음

Code

언어 : JAVA

메모리 : 21504 kb

실행 시간 : 524 ms

import java.util.LinkedList;
import java.util.Scanner;

public class Main {
    static int[][] map;
    static LinkedList<int[]> list;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        map = new int[9][9];
        list = new LinkedList<>();
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                map[i][j] = sc.nextInt();
                if (map[i][j] == 0) {
                    list.add(new int[] { i, j });
                }
            }
        }
        solve(0);
    }

    private static void solve(int depth) {
        if (depth == list.size()) {
            StringBuilder sb = new StringBuilder();

            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    sb.append(map[i][j]).append(" ");
                }
                sb.append("\n");
            }
            sb.append("\n");

            System.out.println(sb);
            System.exit(0);
        }

        int r = list.get(depth)[0];
        int c = list.get(depth)[1];

        for (int i = 1; i <= 9; i++) {
            if (check(r, c, i)) {
                map[r][c] = i;
                solve(depth + 1);
                map[r][c] = 0;
            }
        }

    }

    private static boolean check(int r, int c, int num) {
        if (map[r][c] != 0)
            return false;

        for (int i = 0; i < 9; i++) {
            if (map[i][c] == num || map[r][i] == num) // 가로 세로
                return false;
        }
        int sr = (r / 3) * 3, sc = (c / 3) * 3;
        for (int i = sr; i < sr + 3; i++) {
            for (int j = sc; j < sc + 3; j++) {
                if (map[i][j] == num)  // 3x3
                    return false;
            }
        }

        return true;
    }

}

[BOJ] 9663. N-Queen (Java)

Problem

제출일 : 2020-03-13

문제 풀이 시간 : 2H

난이도 : ★★★★

---

link : https://www.acmicpc.net/problem/9663

N-Queen 문제는 크기가 N × N인 체스판 위에 퀸 N개를 서로 공격할 수 없게 놓는 문제이다.

N이 주어졌을 때, 퀸을 놓는 방법의 수를 구하는 프로그램을 작성하시오.

Input

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

Output

첫째 줄에 퀸 N개를 서로 공격할 수 없게 놓는 경우의 수를 출력한다.

Example

input

8

output

92-2 5 -3 1

Solution & Inpression

기본 적인 백트래킹 문제.

아래 애니메이션을 보면 해를 탐색하는 과정을 알 수 있다.

기본적으로 백트래킹은 map을 돌며 해당 위치에 가로, 세로, 대각선으로 중복되지 않게 말을 놓을 수 있는지 확인하고 된다면 다음 말을 놓고 아니면 이전 말의 위치를 변경하는 방법으로 문제를 해결하면 된다.

처음 시도한 코드는 시간초과가 발생했다. 당연히 시간 초과가 발생할것이다. 시간 복잡도를 따져보면 말을 놓을 수 있는 경우의 수는 $_{N\times N}P_N$가 될 것이고 가지치기는 $O(N^2)$의 시간이 소요될것이다.

검사를 해야 하는 항목이 열을 사용하는지 같은 대각선 내에 있는지를 확인하면 되기에 boolean배열을 이용하여 문제를 해결하였다.

Code 1

언어 : JAVA

결과 : 시간 초과

import java.util.Scanner;

public class Main {
    static int N, ans;

    static boolean[][] map;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();

        map = new boolean[N][N];

        ans = 0;
        solve(0);
        System.out.println(ans);
    }

    public static void solve(int r) {
        if (r == N) {
            ans++;
            return;
        }
        for (int c = 0; c < N; c++) {
            if (check(r, c)) {
                map[r][c] = true;
                solve(r + 1);
                map[r][c] = false;
            }
        }
    }

    public static boolean check(int r, int c) {
        if (map[r][c])
            return false;

        for (int i = 0; i < N; i++) {
            if (map[i][c]) // 행 검사
                return false;
            for (int j = 0; j < N; j++) {
                if (i + j == r + c && map[i][j]) // 대각선 검사(/방향)
                    return false;
                if (i - j == r - c && map[i][j]) // 대각선 검사(\방향)
                    return false;
            }
        }
        return true;
    }
}

Code 2

언어 : JAVA

메모리 : 14912 kb

실행 시간 : 2764 ms

import java.util.Scanner;

public class Main {
    static int N, ans;

    static boolean[] col, slash, backslash;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        N = sc.nextInt();

        col = new boolean[N];
        slash = new boolean[2 * N - 1];
        backslash = new boolean[2 * N - 1];

        ans = 0;
        solve(0);
        System.out.println(ans);
    }

    public static void solve(int r) {
        if (r == N) {
            ans++;
            return;
        }
        for (int c = 0; c < N; c++) {
            if (check(r, c)) {
                col[c] = slash[r + c] = backslash[r - c + N - 1] = true;
                solve(r + 1);
                col[c] = slash[r + c] = backslash[r - c + N - 1] = false;
            }
        }
    }
    public static boolean check(int r, int c) {
        if (col[c] || slash[r + c] || backslash[r - c + N - 1])
            return false;
        return true;
    }
}

[BOJ] 1248. 맞춰봐 (Java)

Problem

제출일 : 2020-03-11

문제 풀이 시간 : 1H 45M

난이도 : ★★★★

---

link : https://www.acmicpc.net/problem/1248

규현이는 멍청하다. 왜냐하면, 1~10까지 수 밖에 모르기 때문이다. 어느 날 규현이 옆을 지나가던 태석이가 규현이를 보고 이렇게 외쳤다. "빵빵!!" 규현이는 "아하!" 하면서 세상에는 빵이란 수도 있구나 했다. 그날 이후로 규현이는 매일 친구들을 볼 때면 "빵빵!!" 거리면서 인사를 했다. 규현이의 친구 중에는 태방이가 있다. 자꾸 규현이가 "빵빵!!" 거릴때 마다 자신을 놀리는 것 처럼 생각했던 태방이는 규현이에게 그건 "빵이 아니고 영이야" 라고 가르쳐 줬다.

이제 규현이는 0~10까지 수를 알고 있다. 어느 날 자신이 알고 있는 숫자를 까먹지 않으려고 종이에 1~10까지 수를 썻다. (0은 잠시 까먹었다) 규현이의 친구 석원이는 밀덕이다. 계급을 엄청나게 좋아해서, 규현이가 써 놓은 숫자에 이등병 마크인 -를 모두 그렸다. 석원이는 규현이에게 이렇게 말했다. "너, 우리 위대하신 미하엘 칼라시니코프께서 뭐라고 했는지 알아? 단순함과 신뢰성, 그리고 저렴한 가격이 최고야!"

규현이는 그 말을 듣고서 아하 세상에는 음수도 있구나 했다.

이제 규현이가 아는 수는 -10부터 10까지 20개가 되었다. 아차, 0을 빼먹었구나, 21개가 되었다.

근처 사파리에 놀러간 규현이는 사파리 가이드 승환이와 함께 관광을 시작했다. "저기, 사자 1마리가 보이죠? 그 옆이 그 사자 부인이에요. 그러니깐, 1 더하기 1은 2죠" 규현이는 덧셈을 익혔다. "저 사자는 아까 그 사자의 자식 2마리 입니다. 그럼 총 사자는 몇 마리이지요?" 이제 규현이는 1+1을 제외한 다른 덧셈도 할 수 있다. 만세!

인도네시아에 놀러간 규현이는 자바 섬에 방문했다. 자바 섬에는 자바 커피를 재배하는 홍태석 농부가 있었다. 홍태석은 "ㅋㅋㅋ 님 음수와 양수와 0의 차이도 모름?" 하면서 음수와 양수와 0을 설명해주었다.

지금까지 배운 것을 종합해서, 한국으로 돌아오는 비행기에서 규현이는 종이에 수를 N개 썼다. (규현이가 아는 가장 큰 수는 10이기 때문에, 수를 10개까지만 쓸 수 있다.) 그 다음에, 가능한 모든 N*(N+1)/2개의 구간의 합을 구했다. 이 것을 해인이는 행렬로 표현했다.

규현이가 쓴 수를 A라고 하면, A[i]는 규현이가 i번째 쓴 수이다. 그리고, S[i][j]는 A[i]부터 A[j]까지 합이 0보다 크면 +, 0이면 0, 0보다 작으면 -이다. 여기서 i는 항상 j보다 작거나 같다. 이렇게 배열을 채우면 배열에는 총 N*(N+1)/2개의 문자가 있다. (+, -, 0 중 하나) 이 S 배열이 주어졌을 때, 규현이가 쓴 N개의 수 A를 구해서 출력하면 된다. 규현이는 -10부터 10까지의 정수밖에 모르기 때문에, A도 -10부터 10까지의 정수로만 이루어져 있어야 한다.

Input

첫째 줄에 수열의 크기 N이 주어진다. N은 10보다 작거나 같은 자연수이다. 둘째 줄에는 N(N+1)/2 길이의 문자열이 주어진다. 처음 N개의 문자는 부호 배열의 첫 번째 줄에 해당하고, 다음 N-1개의 문자는 두 번째 줄에 해당한다. 마찬가지로 마지막 문자는 N번째 줄에 해당하는 문자다.

Output

첫째 줄에 수열의 원소 N개를 빈 칸을 사이에 두고 출력한다. 답이 여러 가지 일 경우에는 아무거나 출력하면 된다.

Example

input

4
-+0++++--+

output

-2 5 -3 1

Solution & Inpression

처음 문제를 잃었을 때 이게 도대체 무슨 말이지? 라는 생각을 했다.

문제에서 S[i][j]는 A[i]부터 A[j]까지 합이 0보다 크면 +, 0이면 0, 0보다 작으면 -이다. 라고 했지만 입력을 보면 1차원 배열로 문제가 주어져 어떻게 입력이 들어오는지 확인을 해야 했다.

테스트 케이스를 기준으로 보면 N = 4로 입력은

- + 0 +
  + + +
    - -
      +

의 순으로 입력을 받았다.

처음에는 숫자를 미리 구해 해당 값이 가능한지 판단을 하는 방식으로 문제를 해결하려 생각했다.

경우의 수가 최대 ${21}C{10} = 1,279,935,820,800$이기 때문에 중간에 판단을 먼저 하여 가지치기 하는 방식으로 문제를 해결하였다.

그리고 새롭게 알게 된 것은 System.exit(0)로 프로그램을 종료 시키는 함수이다.

따로 flag 변수를 사용하여 값을 한번만 출력하게 한 것이 아닌 프로그램을 종료 시키는 방식을 사용하였다.

Code

언어 : JAVA

메모리 : 15644 kb

실행 시간 : 464 ms

import java.util.Scanner;

public class Main {
    static int N;
    static char[][] matrix;
    static int[] data;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        matrix = new char[N][N];
        String str = sc.next();
        int idx = 0;
        for (int i = 0; i < N; i++) {
            for (int j = i; j < N; j++) {
                matrix[i][j] = str.charAt(idx++);
            }
        }

        data = new int[N];
        solve(0);
    }

    private static void solve(int depth) {
        if (depth == N) {
            for (int i : data) {
                System.out.print(i + " ");
            }
            System.out.println();
            System.exit(0); // 프로그램 종료
        }
        for (int i = -10; i <= 10; i++) {
            data[depth] = i;
            if (check(depth)) {
                solve(depth + 1);
            }
        }
    }

    private static boolean check(int idx) {
        for (int i = 0; i <= idx; i++) {
            int sum = 0;
            for (int j = i; j <= idx; j++) {
                sum += data[j];
                if (matrix[i][j] != (sum == 0 ? '0' : (sum > 0 ? '+' : '-'))) {
                    return false;
                }
            }
        }
        return true;
    }
}

[BOJ] 1339. 단어 수학 (Java)

Problem

제출일 : 2020-03-10

문제 풀이 시간 : 4H

난이도 : ★★☆

---

link : https://www.acmicpc.net/problem/1339

민식이는 수학학원에서 단어 수학 문제를 푸는 숙제를 받았다.

단어 수학 문제는 N개의 단어로 이루어져 있으며, 각 단어는 알파벳 대문자로만 이루어져 있다. 이때, 각 알파벳 대문자를 0부터 9까지의 숫자 중 하나로 바꿔서 N개의 수를 합하는 문제이다. 같은 알파벳은 같은 숫자로 바꿔야 하며, 두 개 이상의 알파벳이 같은 숫자로 바뀌어지면 안 된다.

예를 들어, GCF + ACDEB를 계산한다고 할 때, A = 9, B = 4, C = 8, D = 6, E = 5, F = 3, G = 7로 결정한다면, 두 수의 합은 99437이 되어서 최대가 될 것이다.

N개의 단어가 주어졌을 때, 그 수의 합을 최대로 만드는 프로그램을 작성하시오.

Input

첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대 10개이고, 수의 최대 길이는 8이다. 서로 다른 문자는 서로 다른 숫자를 나타낸다.

Output

첫째 줄에 주어진 단어의 합의 최댓값을 출력한다.

Example

input

2
GCF
ACDEB

output

99437

Solution & Inpression

HashMap을 이용하여 사용된 알파벳의 개수를 구한뒤

순열을 이용하여 완전탐색 후 값 계산

최대값 갱신의 순으로 문제를 해결하였다.

Code

언어 : JAVA

메모리 : 19080 kb

실행 시간 : 1408 ms

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

public class Main {
    static int N, max;
    static String[] words;

    static Map<Character, Integer> alphabet;
    static boolean[] visit;
    static int[] data;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();

        words = new String[N];

        alphabet = new HashMap<Character, Integer>();
        int count = 0;
        for (int i = 0; i < N; i++) {
            words[i] = sc.next();
            for (int j = 0; j < words[i].length(); j++) {
                if (!alphabet.containsKey(words[i].charAt(j))) {
                    alphabet.put(words[i].charAt(j), count++);
                }
            }
        }
        data = new int[alphabet.size()];
        visit = new boolean[10];
        max = Integer.MIN_VALUE;
        solve(0, 0);
        System.out.println(max);
    }

    private static void solve(int index, int depth) {
        if (depth == data.length) {
            check();
            return;
        }
        for (int i = 0; i < 10; i++) {
            if (!visit[i]) {
                visit[i] = true;
                data[depth] = i;
                solve(i, depth + 1);
                visit[i] = false;
            }
        }
    }

    private static void check() {
        int ret = 0;
        for (int i = 0; i < words.length; i++) {
            int tmp = 0;
            for (int j = 0; j < words[i].length(); j++) {
                tmp += data[alphabet.get(words[i].charAt(j))];
                tmp *= 10;
            }
            ret += tmp / 10;
        }
        if (max < ret)
            max = ret;
    }
}

자료구조

자료구조란?

• 자료를 효율적으로 사용하기 위해서 자료의 특성에 따라서 분류하여 구성하고 저장 및 처리하는 모든 작업

자료의 형태에 따른 분류

1. 단순 구조
   • 정수, 실수, 문자열 등의 기본 자료형
2. 선형 구조
   • 자료들 사이의 관계가 1:1의 선형 관계
   • 리스트, 연결 리스트, 스택, 큐, 덱 등
3. 비선형 구조
   • 자료들 간의 관계가 1:N, 또는 N:N의 관계
   • 트리, 그래프 등
4. 파일 구조
   • 서로 관련 있는 필드로 구성된 레코드의 집합인 파일에 대한 구조
   • 순차 파일, 색인 파일, 직접 파일 등

자료구조의 관계

[BOJ] 6064. 카잉 달력(Java)

Problem

제출일 : 2020-03-10

문제 풀이 시간 : 4H

난이도 : ★★★★☆

---

link : https://www.acmicpc.net/problem/6064

최근에 ICPC 탐사대는 남아메리카의 잉카 제국이 놀라운 문명을 지닌 카잉 제국을 토대로 하여 세워졌다는 사실을 발견했다. 카잉 제국의 백성들은 특이한 달력을 사용한 것으로 알려져 있다. 그들은 M과 N보다 작거나 같은 두 개의 자연수 x, y를 가지고 각 년도를 <x:y>와 같은 형식으로 표현하였다. 그들은 이 세상의 시초에 해당하는 첫 번째 해를 <1:1>로 표현하고, 두 번째 해를 <2:2>로 표현하였다. <x:y>의 다음 해를 표현한 것을 <x':y'>이라고 하자. 만일 x < M 이면 x' = x + 1이고, 그렇지 않으면 x' = 1이다. 같은 방식으로 만일 y < N이면 y' = y + 1이고, 그렇지 않으면 y' = 1이다. <M:N>은 그들 달력의 마지막 해로서, 이 해에 세상의 종말이 도래한다는 예언이 전해 온다.

예를 들어, M = 10 이고 N = 12라고 하자. 첫 번째 해는 <1:1>로 표현되고, 11번째 해는 <1:11>로 표현된다. <3:1>은 13번째 해를 나타내고, <10:12>는 마지막인 60번째 해를 나타낸다.

네 개의 정수 M, N, x와 y가 주어질 때, <M:N>이 카잉 달력의 마지막 해라고 하면 <x:y>는 몇 번째 해를 나타내는지 구하는 프로그램을 작성하라.

Input

입력 데이터는 표준 입력을 사용한다. 입력은 T개의 테스트 데이터로 구성된다. 입력의 첫 번째 줄에는 입력 데이터의 수를 나타내는 정수 T가 주어진다. 각 테스트 데이터는 한 줄로 구성된다. 각 줄에는 네 개의 정수 M, N, x와 y가 주어진다. (1 ≤ M, N ≤ 40,000, 1 ≤ x ≤ M, 1 ≤ y ≤ N) 여기서 <M:N>은 카잉 달력의 마지막 해를 나타낸다.

Output

출력은 표준 출력을 사용한다. 각 테스트 데이터에 대해, 정수 k를 한 줄에 출력한다. 여기서 k는 <x:y>가 k번째 해를 나타내는 것을 의미한다. 만일 <x:y>에 의해 표현되는 해가 없다면, 즉, <x:y>가 유효하지 않은 표현이면, -1을 출력한다.

Example

input

3
10 12 3 9
10 12 7 2
13 11 5 6

output

33
-1
83

Solution & Inpression

나머지 연산의 특징을 이용하여 문제를 해결하였다.

x값에 M을 더하여 M으로 나누는 나머지 연산을 수행한 결과와 x를 M으로 나누는 나머지 연산을 수행한 결과가 같기 때문에 x값에 M만큼 증가시키며 해당 값이 N으로 나누었을때의 나머지가 y값과 같은지를 검사하였다.

코드상에서 (year % N) == 0 ? N : year % N 부분은 10%10의 결과가 10이 아닌 0이기에 위와같이 처리해주었다.

나머지 연산의 특징

a를 b로 나눈 나머지를 a mod b 할때 나머지는 다음과 같은 식들이 항상 성립합니다.

$1.\ (a+m)\mod m=a \mod m$

$ 2.\ ((a\mod m) + ( b\mod m) ) \mod m = ( a + b ) \mod m $

$3.\ ( ( a \mod m) \times ( b \mod m) ) \mod m = ( a \times b) \mod m $

Code

언어 : JAVA

메모리 : 23080 kb

실행 시간 : 352 ms

package BOJ.Math;
import java.util.Scanner;

public class Silver1_6064_카잉달력 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        for (int tc = 1; tc <= T; tc++) {
            int M = sc.nextInt();
            int N = sc.nextInt();
            int x = sc.nextInt();
            int y = sc.nextInt();

            int year = x;
            int max = lcm(M, N);

            while (true) {
                if (year > max) {
                    System.out.println("-1");
                    break;
                } else if (((year % N) == 0 ? N : year % N) == y) {
                    System.out.println(year);
                    break;
                }
                year += M;
            }
        }
    }

    static int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }

    static int lcm(int a, int b) {
        return (a * b) / gcd(a, b);
    }
}

Reference

6064번 : 카잉 달력|작성자 DolphaGo

중국인의 나머지 정리

중국인의 나머지 정리(CRT: Chinese remainder theorem)를 이용하면 한 개의 변수와 서로소인 다른 모듈로를 갖는 합동 방정식의 해를 구할 수 있다. 이 방정식은 아래와 같이 표현된다.
$$
x \equiv a_1(mod\ m_1),\ x \equiv a_2(mod\ m_2),\ ...\ ,\ x \equiv a_3(mod\ m_3)
$$
중국인의 나머지 정리는 모듈로 값들이 서로소만 된다면 위의 연립 방정식이 유일한 해를 갖는다는 것을 보인 정리이다.

다음 연립 방정식의 해를 구하시오.
$$
x \equiv 2(mod\ 3),\ x \equiv 3(mod\ 5),\ x \equiv 2(mod\ 7)
$$
풀이

이 연립 방정식의 해는 다음 단계로 구할 수 있다.

1. 공통 모듈로로 사용할 $M = m_1 \times m_2 \times \ ... \ m_k$를 구한다.

2. $M_1 = M/m_1, \ M_2 = M/m_2, \ ...\ ,\ M_k = M/m_k$를 구한다.

3. 각각의 식에 대응하는 모듈로 값인 $(m_1,\ m_2,\ m_3)$를 이용하여 곱에 대한 역원인 $M_1,\ M_2,\ ...\ ,\ M_k$를 구한다. 각각의 역원을 $M_1\ ^{-1},\ M_2\ ^{-1},\ ...\ ,\ M_k\ ^{-1}$라고 나타낸다.

4. 이 연립 방정식의 해는 다음과 같다.
   $$
   x=(a_1\times M_1\times M_1\ ^{-1} + a_2\times M_2\times M_2\ ^{-1}+\ ...\ +a_k\times M_k\times M_k\ ^{-1})\ mod\ M
   $$

다음 4단계에 따라 해를 구해보자.

1. $M=3\times 5\times 7 = 105$이다.
2. $M_1=105/3=35,\ M_2=105/5=21,\ M_3=105/7=15$이다.
3. 곱에 대한 역원은 $M_1\ ^{-1}=2,\ M_2\ ^{-1}=1. M_3\ ^{-1}=1$이다.
4. $x=(2\times35\times2+3\times21\times1+15\times1)\ mod\ 105=23\ mod\ 105$

곱셈에 대한 역원

$Z_n$에서 두 수 $a,\ b$는 다음을 만족하면 서로 곱셈에 대한 역원이 된다.
$$
a\times b\equiv 1\ mod\ n
$$
예를 들어, 모듈로가 $10$이면 $3$의 곱셈에 대한 역원은 $7$이다. 즉, $(3 \times 7)\ mod\ 10=1$이다.

모듈로 연산에서 정수는 곱셈에 대한 역원이 있을수도 있고 없을수도 있다.
만약 곱셈에 대한 역원이 있다면, 
그 정수와 해당하는 곱셈에 대한 역원의 곱은 모듈로 n에서 1과 합동이다.

$a$가 $Z_n$에서 곱셈에 대한 역원을 갖기 위한 필요충분조건이 $gcd(n,a)=1$이라는 것을 증명 할 수 있다.

이 경우 $a$와 $n$은 서로소라고 한다.