[BOJ] 2251. 물통 - (Java)

Problem

제출일 : 2020-03-22

문제 풀이 시간 : 30M

난이도 : ★★

---

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

각각 부피가 A, B, C(1≤A, B, C≤200) 리터인 세 개의 물통이 있다. 처음에는 앞의 두 물통은 비어 있고, 세 번째 물통은 가득(C 리터) 차 있다. 이제 어떤 물통에 들어있는 물을 다른 물통으로 쏟아 부을 수 있는데, 이때에는 한 물통이 비거나, 다른 한 물통이 가득 찰 때까지 물을 부을 수 있다. 이 과정에서 손실되는 물은 없다고 가정한다.

이와 같은 과정을 거치다보면 세 번째 물통(용량이 C인)에 담겨있는 물의 양이 변할 수도 있다. 첫 번째 물통(용량이 A인)이 비어 있을 때, 세 번째 물통(용량이 C인)에 담겨있을 수 있는 물의 양을 모두 구해내는 프로그램을 작성하시오.

Input

첫째 줄에 세 정수 A, B, C가 주어진다.

Output

첫째 줄에 공백으로 구분하여 답을 출력한다. 각 용량은 오름차순으로 정렬한다.

Example

input

8 9 10

output

1 2 8 9 10

Solution & Inpression

물통의 물을 옮기는 방법

from A to B

from A to C

from B to A

from B to C

from C to A

from C to B

모든 경우를 BFS 탐색 Set을 이용하여 중복을 제거한 뒤 List로 옮겨 정렬 후 출력

Code

언어 : JAVA

메모리 : 23520 kb

실행 시간 : 112 ms

import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;

public class Main {
    static int[] input;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        input = new int[3];
        input[0] = sc.nextInt();
        input[1] = sc.nextInt();
        input[2] = sc.nextInt();

        Queue<int[]> q = new LinkedList<>();
        Set<Integer> set = new HashSet<>();
        boolean[][][] visit = new boolean[input[0] + 1][input[1] + 1][input[2] + 1];
        visit[0][0][input[2]] = true;
        set.add(input[2]);
        q.offer(new int[] { 0, 0, input[2] });

        while (!q.isEmpty()) {
            int[] now = q.poll();
            if (now[0] == 0) {
                set.add(now[2]);
            }

            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    if (i == j)
                        continue;
                    int[] next = solve(now, i, j);
                    if (!visit[next[0]][next[1]][next[2]]) {
                        visit[next[0]][next[1]][next[2]] = true;
                        q.offer(next);
                    }
                }
            }
        }

        ArrayList<Integer> ans = new ArrayList<>(set);
        Collections.sort(ans);
        StringBuilder sb = new StringBuilder();
        for (Integer i : ans) {
            sb.append(i).append(" ");
        }
        System.out.println(sb);
    }

    private static int[] solve(int[] now, int i, int j) {
        if (now[i] == 0 || now[j] == input[j]) {
            return now;
        }

        // from i to j;
        int[] next = now.clone();
        int tmp = input[j] - next[j];
        if (next[i] > tmp) {
            next[j] += tmp;
            next[i] -= tmp;
        } else {
            next[j] += next[i];
            next[i] = 0;
        }

        return next;
    }
}

[BOJ] 1525. 퍼즐- (Java)

Problem

제출일 : 2020-03-22

문제 풀이 시간 : 1H 30M

난이도 : ★★★

---

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

3×3 표에 다음과 같이 수가 채워져 있다. 오른쪽 아래 가장 끝 칸은 비어 있는 칸이다.

어떤 수와 인접해 있는 네 개의 칸 중에 하나가 비어 있으면, 수를 그 칸으로 이동시킬 수가 있다. 물론 표 바깥으로 나가는 경우는 불가능하다. 우리의 목표는 초기 상태가 주어졌을 때, 최소의 이동으로 위와 같은 정리된 상태를 만드는 것이다. 다음의 예를 보자.

가장 윗 상태에서 세 번의 이동을 통해 정리된 상태를 만들 수 있다. 이와 같이 최소 이동 횟수를 구하는 프로그램을 작성하시오.

Input

세 줄에 걸쳐서 표에 채워져 있는 아홉 개의 수가 주어진다. 한 줄에 세 개의 수가 주어지며, 빈 칸은 0으로 나타낸다.

Output

첫째 줄에 최소의 이동 횟수를 출력한다. 이동이 불가능한 경우 -1을 출력한다.

Example

input

1 0 3
4 2 5
7 8 6

output

3

Solution & Inpression

맵의 상태를 정수형으로 변환 Set자료구조를 이용한 방문 확인

Code

언어 : JAVA

메모리 : 63944 kb

실행 시간 : 688 ms

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Set;
import java.util.TreeSet;

public class Gold3_1525_퍼즐 {
    static int[] dr = { -1, 1, 0, 0 };
    static int[] dc = { 0, 0, -1, 1 };

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int map = 0;
        int[] start = new int[2];
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                int tmp = sc.nextInt();
                map *= 10;
                map += tmp;
                if (tmp == 0) {
                    map += 9;
                    start[0] = i;
                    start[1] = j;
                }
            }
        }
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] { map, start[0], start[1], 0 });
        Set<Integer> set = new TreeSet<>();
        set.add(map);
        while (!q.isEmpty()) {
            if (q.peek()[0] == 123456789) {
                System.out.println(q.peek()[3]);
                System.exit(0);
            }

            char[] now = ("" + q.peek()[0]).toCharArray();
            int r = q.peek()[1];
            int c = q.peek()[2];
            int cnt = q.peek()[3];
            q.poll();

            for (int k = 0; k < dr.length; k++) {
                int nr = r + dr[k];
                int nc = c + dc[k];
                if (isRange(nr, nc)) {
                    int next = getNext(now, r * 3 + c, nr * 3 + nc);
                    if (!set.contains(next)) {
                        set.add(next);
                        q.offer(new int[] { next, nr, nc, cnt + 1 });
                    }
                }
            }
        }
        System.out.println(-1);
    }

    private static int getNext(char[] now, int i, int j) {
        char tmp = now[i];
        now[i] = now[j];
        now[j] = tmp;
        int ret = 0;
        for (char c : now) {
            ret *= 10;
            ret += c - '0';
        }
        tmp = now[i];
        now[i] = now[j];
        now[j] = tmp;
        return ret;
    }

    private static boolean isRange(int nr, int nc) {
        if (0 <= nr && nr < 3 && 0 <= nc && nc < 3)
            return true;
        return false;
    }

}

[BOJ] 1175. 배달 - (Java)

Problem

제출일 : 2020-03-21

문제 풀이 시간 : 3H

난이도 : ★★★

---

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

어제 선물을 모두 포장한 민식이는 이제 선물을 배달하려고 한다. 민식이가 선물을 배달할 곳은 이 문제를 읽는 사람들이 앉아 있는 교실이다. 교실은 직사각형모양이고, 모두 같은 크기의 정사각형 블록으로 나누어져 있다.

입력으로 교실의 지도가 주어진다. 각각의 정사각형 블록은 다음과 같이 4가지 종류가 있다.

• S : 지금 민식이가 있는 곳이다. 이곳이 민식이가 배달을 시작하는 곳이다.
• C : 민식이가 반드시 선물을 배달해야 하는 곳이다. 이러한 블록은 정확하게 2개 있다.
• # : 민식이가 갈 수 없는 곳이다.
• . : 민식이가 자유롭게 지나갈 수 있는 곳이다.

민식이가 한 블록 동서남북으로 이동하는데는 1분이 걸린다. 민식이는 네가지 방향 중 하나로 이동할 수 있으며, 교실을 벗어날 수 없다. 민식이가 선물을 배달해야 하는 곳에 들어갈 때, 민식이는 그 곳에 있는 사람 모두에게 선물을 전달해야 한다. 이 상황은 동시에 일어나며, 추가적인 시간이 소요되지 않는다.

민식이는 어느 누구도 자신을 보지 않았으면 하기 때문에, 멈추지 않고 매 시간마다 방향을 바꿔야 한다. 이 말은 같은 방향으로 두 번 연속으로 이동할 수 없다는 말이다. 민식이가 선물을 모두 배달하는데 걸리는 시간의 최솟값을 구하는 프로그램을 작성하시오.

Input

첫째 줄에 교실의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에 교실의 지도가 주어진다.

Output

첫째 줄에 민식이가 선물을 모두 배달하는데 걸리는 시간의 최솟값을 출력한다. 만약 불가능 할 때는 -1을 출력한다.

Example

input

2 3
SCC
...

output

4

Solution & Inpression

visit[r][c][status][dir] 방향과 상태를 포함하여 방문처리하여 문제 해결

Code

언어 : JAVA

메모리 : 20068 kb

실행 시간 : 168 ms

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

public class Main {
    static int N, M;
    static char[][] map;
    static int[][] point;

    static int[] dr = { -1, 1, 0, 0 };
    static int[] dc = { 0, 0, -1, 1 };

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

        map = new char[N][M];
        point = new int[3][2];
        int idx = 1;
        for (int i = 0; i < N; i++) {
            String str = sc.next();
            for (int j = 0; j < M; j++) {
                map[i][j] = str.charAt(j);
                if (map[i][j] == 'S') {
                    point[0][0] = i;
                    point[0][1] = j;
                    map[i][j] = '.';
                } else if (map[i][j] == 'C') {
                    point[idx][0] = i;
                    point[idx++][1] = j;
                    map[i][j] = '.';
                }
            }
        }

        Queue<int[]> q = new LinkedList<>();
        // visit[r][c][status][dir]
        boolean[][][][] visit = new boolean[N][M][3][4];

        for (int i = 0; i < 4; i++) {
            visit[point[0][0]][point[0][1]][0][i] = true;
        }

        q.offer(new int[] { point[0][0], point[0][1], -1, 0, 0 });
        while (!q.isEmpty()) {
            int r = q.peek()[0];
            int c = q.peek()[1];
            int dir = q.peek()[2];
            int cnt = q.peek()[3];
            int status = q.peek()[4];
            q.poll();

            if (r == point[1][0] && c == point[1][1]) { // 1번 도착
                status |= 1;
            } else if (r == point[2][0] && c == point[2][1]) { // 2번 도착
                status |= 2;
            }

            if (status == 3) {
                System.out.println(cnt);
                System.exit(0);
            }

            for (int k = 0; k < dr.length; k++) {
                if (k == dir)
                    continue;
                int nr = r + dr[k];
                int nc = c + dc[k];
                if (isRange(nr, nc) && !visit[nr][nc][status][k] && map[nr][nc] == '.') {
                    visit[nr][nc][status][k] = true;
                    q.offer(new int[] { nr, nc, k, cnt + 1, status });
                }
            }
        }
        System.out.println(-1);
    }

    private static boolean isRange(int nr, int nc) {
        if (0 <= nr && nr < N && 0 <= nc && nc < M)
            return true;
        return false;
    }
}

[BOJ] 1039. 교환 - (Java)

Problem

제출일 : 2020-03-21

문제 풀이 시간 : 2H

난이도 : ★★★

---

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

0으로 시작하지 않는 정수 N이 주어진다. 이때, M을 정수 N의 자릿수라고 했을 때, 다음과 같은 연산을 K번 수행한다.

1 ≤ i < j ≤ M인 i와 j를 고른다. 그 다음, i번 위치의 숫자와 j번 위치의 숫자를 바꾼다. 이때, 바꾼 수가 0으로 시작하면 안 된다.

위의 연산을 K번 했을 때, 나올 수 있는 수의 최댓값을 구하는 프로그램을 작성하시오.

Input

첫째 줄에 정수 N과 K가 주어진다. N은 1,000,000보다 작거나 같은 자연수이고, K는 10보다 작거나 같은 자연수이다.

Output

첫째 줄에 문제에 주어진 연산을 K번 했을 때, 만들 수 있는 가장 큰 수를 출력한다. 만약 연산을 K번 할 수 없으면 -1을 출력한다.

Example

input

16375 1

output

76315

Solution & Inpression

visit을 2차원 배열을 이용하여 처리

BFS를 이용한 완전탐색.

Code

언어 : JAVA

메모리 : 55052 kb

실행 시간 : 176 ms

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

public class Main {

    static boolean visit[][];
    static int N, K, len;

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

        visit = new boolean[1000001][K + 1];

        Queue<int[]> q = new LinkedList<>();
        q.add(new int[] { N, 0 });
        visit[N][0] = true;

        int result = -1;

        while (!q.isEmpty()) {
            int[] now = q.poll();

            if (now[1] == K) {
                if (result < now[0]) {
                    result = now[0];
                }
                continue;
            }

            for (int i = 0; i < len - 1; i++) {
                for (int j = i + 1; j < len; j++) {
                    int next = solve(now[0], i, j);
                    if (next != -1 && !visit[next][now[1] + 1]) {
                        visit[next][now[1] + 1] = true;
                        q.add(new int[] { next, now[1] + 1 });
                    }
                }
            }

        }

        System.out.println(result);

    }

    private static int solve(int x, int i, int j) {
        char[] input = ("" + x).toCharArray();

        if (i == 0 && input[j] == '0')
            return -1;

        char tmp = input[i];
        input[i] = input[j];
        input[j] = tmp;

        int ret = 0;
        for (int k = 0; k < input.length; k++) {
            ret *= 10;
            ret += input[k] - '0';
        }
        return ret;
    }
}

[BOJ] 9019. DSLR - (Java)

Problem

제출일 : 2020-03-21

문제 풀이 시간 : 2H

난이도 : ★★★

---

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

네 개의 명령어 D, S, L, R 을 이용하는 간단한 계산기가 있다. 이 계산기에는 레지스터가 하나 있는데, 이 레지스터에는 0 이상 10,000 미만의 십진수를 저장할 수 있다. 각 명령어는 이 레지스터에 저장된 n을 다음과 같이 변환한다. n의 네 자릿수를 d1, d2, d3, d4라고 하자(즉 n = ((d1 × 10 + d2) × 10 + d3) × 10 + d4라고 하자)

1. D: D 는 n을 두 배로 바꾼다. 결과 값이 9999 보다 큰 경우에는 10000 으로 나눈 나머지를 취한다. 그 결과 값(2n mod 10000)을 레지스터에 저장한다.
2. S: S 는 n에서 1 을 뺀 결과 n-1을 레지스터에 저장한다. n이 0 이라면 9999 가 대신 레지스터에 저장된다.
3. L: L 은 n의 각 자릿수를 왼편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d2, d3, d4, d1이 된다.
4. R: R 은 n의 각 자릿수를 오른편으로 회전시켜 그 결과를 레지스터에 저장한다. 이 연산이 끝나면 레지스터에 저장된 네 자릿수는 왼편부터 d4, d1, d2, d3이 된다.

위에서 언급한 것처럼, L 과 R 명령어는 십진 자릿수를 가정하고 연산을 수행한다. 예를 들어서 n = 1234 라면 여기에 L 을 적용하면 2341 이 되고 R 을 적용하면 4123 이 된다.

여러분이 작성할 프로그램은 주어진 서로 다른 두 정수 A와 B(A ≠ B)에 대하여 A를 B로 바꾸는 최소한의 명령어를 생성하는 프로그램이다. 예를 들어서 A = 1234, B = 3412 라면 다음과 같이 두 개의 명령어를 적용하면 A를 B로 변환할 수 있다.

1234 →L 2341 →L 3412
1234 →R 4123 →R 3412

따라서 여러분의 프로그램은 이 경우에 LL 이나 RR 을 출력해야 한다.

n의 자릿수로 0 이 포함된 경우에 주의해야 한다. 예를 들어서 1000 에 L 을 적용하면 0001 이 되므로 결과는 1 이 된다. 그러나 R 을 적용하면 0100 이 되므로 결과는 100 이 된다.

Input

프로그램 입력은 T 개의 테스트 케이스로 구성된다. 테스트 케이스 개수 T 는 입력의 첫 줄에 주어진다. 각 테스트 케이스로는 두 개의 정수 A와 B(A ≠ B)가 공백으로 분리되어 차례로 주어지는데 A는 레지스터의 초기 값을 나타내고 B는 최종 값을 나타낸다. A 와 B는 모두 0 이상 10,000 미만이다.

Output

A에서 B로 변환하기 위해 필요한 최소한의 명령어 나열을 출력한다.

Example

input

3
1234 3412
1000 1
1 16

output

LL
L
DDDD

Solution & Inpression

문제를 잘 읽자!!

n이 0 이라면 9999 가 대신 레지스터에 저장 == now == 0 ? 9999 : now - 1;

A 와 B는 모두 0 이상 10,000 미만

Code

언어 : JAVA

메모리 : 373232 kb

실행 시간 : 3836 ms

import java.util.*;

public class Main {
    static class Number {
        int num;
        String command;

        public Number(int num, String command) {
            this.num = num;
            this.command = command;
        }
    }

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

        for (int tc = 0; tc < T; tc++) {
            int A = sc.nextInt();
            int B = sc.nextInt();

            boolean[] visit = new boolean[10000];
            Queue<Number> q = new LinkedList<>();
            q.offer(new Number(A, ""));
            visit[A] = true;

            while (!q.isEmpty()) {
                int now = q.peek().num;
                String command = q.peek().command;
                q.poll();

                if (now == B) {
                    System.out.println(command);
                    break;
                }

                int next = (now * 2) % 10000;
                if (!visit[next]) {
                    visit[next] = true;
                    q.offer(new Number(next, command + "D"));
                }
                next = now == 0 ? 9999 : now - 1;
                if (!visit[next]) {
                    visit[next] = true;
                    q.offer(new Number(next, command + "S"));
                }

                next = now / 1000 + (now % 1000) * 10;
                if (!visit[next]) {
                    visit[next] = true;
                    q.offer(new Number(next, command + "L"));
                }
                next = now % 10 * 1000 + now / 10;
                if (!visit[next]) {
                    visit[next] = true;
                    q.offer(new Number(next, command + "R"));
                }
            }
        } // end of TC
    }

}

[BOJ] 1072. 게임 - (Java)

Problem

제출일 : 2020-03-17

문제 풀이 시간 : 1H 45M

난이도 : ★★★

---

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

김형택은 지금 몰래 Spider Solitaire(스파이더 카드놀이)를 하고 있다. 형택이는 이 게임을 이길 때도 있었지만, 질 때도 있었다. 누군가의 시선이 느껴진 형택이는 게임을 중단하고 코딩을 하기 시작했다. 의심을 피했다고 생각한 형택이는 다시 게임을 켰다. 그 때 형택이는 잠시 코딩을 하는 사이에 자신의 게임 실력이 눈에 띄게 향상된 것을 알았다.

이제 형택이는 앞으로의 모든 게임에서 지지 않는다. 하지만, 형택이는 게임 기록을 삭제 할 수 없기 때문에, 자신의 못하던 예전 기록이 현재 자신의 엄청난 실력을 증명하지 못한다고 생각했다.

게임 기록은 다음과 같이 생겼다.

• 게임 횟수 : X
• 이긴 게임 : Y (Z %)
• Z는 형택이의 승률이다. 소수점은 버린다. 예를 들어, X=53, Y=47이라면, Z = 88이다.

X와 Y가 주어졌을 때, 형택이가 게임을 몇 판 더해야 Z가 변하는지 구하는 프로그램을 작성하시오.

Input

각 줄에 X와 Y가 주어진다. X는 1,000,000,000보다 작거나 같은 자연수이고, Y는 0보다 크거나 같고, X보다 작거나 같은 자연수이다.

Output

첫째 줄에 형택이가 게임을 몇 판 해야하는지 출력한다. 만약 Z가 절대 변하지 않는다면 -1을 출력한다.

Example

input

10 8

output

1

Solution & Inpression

이분탐색을 이용한 구현

자료형을 주의하여 문제를 해결해야 한다.

99% 와 100%는 확률이 변하지 않음.

Code

언어 : JAVA

메모리 : 14264 kb

실행 시간 : 104 ms

import java.util.Scanner;

public class Main {
    static long X, Y, Z;

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

        Z = Y * 100 / X;
        if (Z >= 99)
            System.out.println(-1);
        else
            binarySearch(1, X);
    }

    private static void binarySearch(long start, long end) {
        long mid = 0, ratio = 0;
        while (start <= end) {
            mid = (start + end) / 2;
            ratio = (Y + mid) * 100 / (X + mid);

            if (ratio > Z) {
                end = mid - 1;
            } else {
                start = mid + 1;
            }
        }
        System.out.println(start);
    }

}

[BOJ] 7453. 합이 0인 네 정수 - (Java)

Problem

제출일 : 2020-03-17

문제 풀이 시간 : 1H

난이도 : ★★★★

---

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

정수로 이루어진 크기가 같은 배열 A, B, C, D가 있다.

A[a], B[b], C[c], D[d]의 합이 0인 (a, b, c, d) 쌍의 개수를 구하는 프로그램을 작성하시오.

Input

첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 $2^{28}$이다.

Output

합이 0이 되는 쌍의 개수를 출력한다.

Example

input

6
-45 22 42 -16
-41 -27 56 30
-36 53 -37 77
-36 30 -75 -46
26 -38 -10 62
-32 -54 -6 45

output

5

Solution & Inpression

low_bound와 upper_bound를 활용하는 문제, 아이디어를 도출해 내는 것이 중요함.

시간초과를 벗어나기 위해 BufferedReader를 사용했으며 ArrayList대신 배열을 이용함.

Code

언어 : JAVA

메모리 : 140708 kb

실행 시간 : 2552 ms

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

public class Main {
    static int N;
    static int[][] data;
    static int[] AB, CD;
    static long ans;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        N = Integer.parseInt(br.readLine());

        data = new int[4][N];
        for (int j = 0; j < N; j++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int i = 0; i < 4; i++) {
                data[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        AB = new int[N * N];
        CD = new int[N * N];

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                AB[i * N + j] = data[0][i] + data[1][j];
                CD[i * N + j] = data[2][i] + data[3][j];
            }
        }

        Arrays.sort(CD);

        for (int i : AB) {
            int high = upper_bound(CD, -i);
            int low = lower_bound(CD, -i);
            ans += high - low;
        }

        System.out.println(ans);
    }

    // lower bound는 찾고자 하는 값 이상이 처음 나타나는 위치
    private static int lower_bound(int[] arr, int val) {
        int start = 0;
        int end = arr.length;
        int mid;
        while (start < end) {
            mid = (start + end) >> 1;
            if (arr[mid] >= val) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }

    // upper bound는 찾고자 하는 값보다 큰 값이 처음으로 나타나는 위치
    private static int upper_bound(int[] arr, int val) {
        int start = 0;
        int end = arr.length;
        int mid;
        while (start < end) {
            mid = (start + end) >> 1;
            if (arr[mid] <= val) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return start;
    }
}

[BOJ] 2143. 두 배열의 합 - (Java)

Problem

제출일 : 2020-03-17

문제 풀이 시간 : 1H

난이도 : ★★★★

---

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

한 배열 A[1], A[2], …, A[n]에 대해서, 부 배열은 A[i], A[i+1], …, A[j-1], A[j] (단, 1 ≤ i ≤ j ≤ n)을 말한다. 이러한 부 배열의 합은 A[i]+…+A[j]를 의미한다. 각 원소가 정수인 두 배열 A[1], …, A[n]과 B[1], …, B[m]이 주어졌을 때, A의 부 배열의 합에 B의 부 배열의 합을 더해서 T가 되는 모든 부 배열 쌍의 개수를 구하는 프로그램을 작성하시오.

예를 들어 A = {1, 3, 1, 2}, B = {1, 3, 2}, T=5인 경우, 부 배열 쌍의 개수는 다음의 7가지 경우가 있다.

T(=5) = A[1] + B[1] + B[2]
      = A[1] + A[2] + B[1]
      = A[2] + B[3]
      = A[2] + A[3] + B[1]
      = A[3] + B[1] + B[2]
      = A[3] + A[4] + B[3]
      = A[4] + B[2] 

Input

첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다음 줄에 m개의 정수로 B[1], …, B[m]이 주어진다. 각각의 배열 원소는 절댓값이 1,000,000을 넘지 않는 정수이다.

Output

첫째 줄에 답을 출력한다. 가능한 경우가 한 가지도 없을 경우에는 0을 출력한다.

Example

input

5
4
1 3 1 2
3
1 3 2

output

7

Solution & Inpression

low_bound와 upper_bound를 활용하는 문제, 아이디어를 도출해 내는 것이 중요함.

Code

언어 : JAVA

메모리 : 48848 kb

실행 시간 : 948 ms

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Scanner;

public class Main {
    static int T, N, M;
    static long ans;
    static int[] A, B;

    static List<Integer> a, b;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        T = sc.nextInt(); // T(-1,000,000,000 ≤ T ≤ 1,000,000,000)

        N = sc.nextInt(); // n(1 ≤ n ≤ 1,000)
        A = new int[N];
        for (int i = 0; i < N; i++) {
            A[i] = sc.nextInt(); // 절댓값이 1,000,000을 넘지 않는 정수
        }

        M = sc.nextInt();// m(1≤m≤1,000)
        B = new int[M];
        for (int i = 0; i < M; i++) {
            B[i] = sc.nextInt(); // 절댓값이 1,000,000을 넘지 않는 정수
        }

        a = new ArrayList<>();
        get(A, a);
        b = new ArrayList<>();
        get(B, b);

        Collections.sort(b);

        ans = 0;
        for (Integer i : a) {
            int val = T - i;
            int high = upper_bound(b, val);
            int low = lower_bound(b, val);
            ans += high - low;
        }
        System.out.println(ans);
    }

    private static void get(int[] data, List<Integer> list) {
        for (int size = 1; size <= data.length; size++) {
            int sum = 0;
            for (int i = 0; i < size; i++) {
                sum += data[i];
            }
            for (int i = size; i < data.length; i++) {
                list.add(sum);
                sum += data[i];
                sum -= data[i - size];
            }
            list.add(sum);
        }
    }

    // lower bound는 찾고자 하는 값 이상이 처음 나타나는 위치
    private static int lower_bound(List<Integer> list, int val) {
        int start = 0;
        int end = list.size();
        int mid;
        while (start < end) {
            mid = (start + end) >> 1;
            if (list.get(mid) >= val) {
                end = mid;
            } else {
                start = mid + 1;
            }
        }
        return start;
    }

    // upper bound는 찾고자 하는 값보다 큰 값이 처음으로 나타나는 위치
    private static int upper_bound(List<Integer> list, int val) {
        int start = 0;
        int end = list.size();
        int mid;
        while (start < end) {
            mid = (start + end) >> 1;
            if (list.get(mid) <= val) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }
        return start;
    }
}