더 이상 물러설 곳이 없다

www.acmicpc.net/problem/1992

문제

흑백 영상을 압축하여 표현하는 데이터 구조로 쿼드 트리(Quad Tree)라는 방법이 있다. 흰 점을 나타내는 0과 검은 점을 나타내는 1로만 이루어진 영상(2차원 배열)에서 같은 숫자의 점들이 한 곳에 많이 몰려있으면, 쿼드 트리에서는 이를 압축하여 간단히 표현할 수 있다.

주어진 영상이 모두 0으로만 되어 있으면 압축 결과는 "0"이 되고, 모두 1로만 되어 있으면 압축 결과는 "1"이 된다. 만약 0과 1이 섞여 있으면 전체를 한 번에 나타내지를 못하고, 왼쪽 위, 오른쪽 위, 왼쪽 아래, 오른쪽 아래, 이렇게 4개의 영상으로 나누어 압축하게 되며, 이 4개의 영역을 압축한 결과를 차례대로 괄호 안에 묶어서 표현한다

위 그림에서 왼쪽의 영상은 오른쪽의 배열과 같이 숫자로 주어지며, 이 영상을 쿼드 트리 구조를 이용하여 압축하면 "(0(0011)(0(0111)01)1)"로 표현된다.  N ×N 크기의 영상이 주어질 때, 이 영상을 압축한 결과를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 영상의 크기를 나타내는 숫자 N 이 주어진다. N 은 언제나 2의 제곱수로 주어지며, 1 ≤ N ≤ 64의 범위를 가진다. 두 번째 줄부터는 길이 N의 문자열이 N개 들어온다. 각 문자열은 0 또는 1의 숫자로 이루어져 있으며, 영상의 각 점들을 나타낸다.

출력

영상을 압축한 결과를 출력한다.

예제 입력 1

8

11110000

11110000

00011100

00011100

11110000

11110000

11110011

11110011

예제 출력 1

((110(0101))(0010)1(0001))

풀이 .

import java.io.*;

public class Main {
    static BufferedReader br = null;
    static BufferedWriter bw = null;
    static StringBuilder sb = null;
    static char[] str = null;

    static int[][] map = null;
    static int n;

    public static boolean isPossible(int row, int col, int len) {
        int target = map[row][col];
        for(int i = row; i < row + len; i++) {
            for(int j = col; j < col + len; j++) {
                if(map[i][j] != target) {
                    return false;
                }
            }
        }
        return true;
    }

    public static void divideAndConquer(int row, int col, int len) {
        if(isPossible(row, col, len)) {
            char target = (char)(map[row][col] + '0');  // String.valueOf() 쓰기 싫어서 char로 받음
            sb.append(target);
        }else {
            sb.append("(");
            int nextLen = len / 2;
            for(int i = 0; i < 2; i++) {
                for(int j = 0; j < 2; j++) {
                    divideAndConquer(row + i*nextLen, col + j*nextLen, nextLen);
                }
            }
            sb.append(")");
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        sb = new StringBuilder();
        n = Integer.parseInt(br.readLine());

        map = new int[n+1][n+1];
        for(int i = 1; i <= n; i++) {
            str = (" " + br.readLine()).toCharArray();
            for(int j = 1; j <= n; j++) {
                map[i][j] = str[j] - '0';
            }
        }

        divideAndConquer(1, 1, n);
        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}

codeung.tistory.com/194 와 거의 유사한 문제

구간을 분할하면 분할된 그 구간은 괄호 안에서 출력이 되어야 한다.

따라서 반복문의 시작과 끝에 "(", ")"를 더해준다.

www.acmicpc.net/problem/1780

문제

N×N크기의 행렬로 표현되는 종이가 있다. 종이의 각 칸에는 -1, 0, 1의 세 값 중 하나가 저장되어 있다. 우리는 이 행렬을 적절한 크기로 자르려고 하는데, 이때 다음의 규칙에 따라 자르려고 한다.

1. 만약 종이가 모두 같은 수로 되어 있다면 이 종이를 그대로 사용한다.
2. (1)이 아닌 경우에는 종이를 같은 크기의 9개의 종이로 자르고, 각각의 잘린 종이에 대해서 (1)의 과정을 반복한다.

이와 같이 종이를 잘랐을 때, -1로만 채워진 종이의 개수, 0으로만 채워진 종이의 개수, 1로만 채워진 종이의 개수를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 37, N은 3k 꼴)이 주어진다. 다음 N개의 줄에는 N개의 정수로 행렬이 주어진다.

출력

첫째 줄에 -1로만 채워진 종이의 개수를, 둘째 줄에 0으로만 채워진 종이의 개수를, 셋째 줄에 1로만 채워진 종이의 개수를 출력한다.

예제 입력 1

9

0 0 0 1 1 1 -1 -1 -1

0 0 0 1 1 1 -1 -1 -1

0 0 0 1 1 1 -1 -1 -1

1 1 1 0 0 0 0 0 0

1 1 1 0 0 0 0 0 0

1 1 1 0 0 0 0 0 0

0 1 -1 0 1 -1 0 1 -1

0 -1 1 0 1 -1 0 1 -1

0 1 -1 1 0 -1 0 1 -1

예제 출력 1

10

12

11

풀이 .

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    static BufferedReader br = null;
    static BufferedWriter bw = null;
    static StringBuilder sb = null;
    static StringTokenizer st = null;

    static int[][] paper = null;
    static int[] answer = null;
    static int n;

    public static boolean isPossible(int row, int col, int len) {
        int target = paper[row][col];
        for(int i = row; i < row + len; i++) {
            for(int j = col; j < col + len; j++) {
                if(paper[i][j] != target) {
                    return false;
                }
            }
        }
        return true;
    }

    public static void divideAndConquer(int row, int col, int len) {  // row, col은 시작행, 시작열임
        if(isPossible(row, col, len)) {
            int target = paper[row][col];
            answer[target + 1] += 1;  // -1, 0, 1 을 [0], [1], [2]에 담는다.
        }else {
            int nextLen = len / 3;
            for(int i = 0; i < 3; i++) {
                for(int j = 0; j < 3; j++) {
                    divideAndConquer(row + i*nextLen, col + j*nextLen, nextLen);
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        sb = new StringBuilder();

        n = Integer.parseInt(br.readLine());
        paper = new int[n+1][n+1];  // 0행, 0열은 버린다.
        answer = new int[3];
        for(int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++) {
                paper[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        divideAndConquer(1, 1, n);
        for(int ans : answer) {
            System.out.println(ans);
        }
    }
}

1. 한 장의 종이로 가능한지 검사

2. 불가할 경우 9칸으로 나눠서 재귀

인덱스를 맞추는 데 애를 먹다가 파라미터 len으로 해결했다.

굳이 끝나는 인덱스까지 줄 것 없이 몇 칸을 이동할 것인지를 넘겨주면 된다.

www.acmicpc.net/problem/11728

문제

정렬되어있는 두 배열 A와 B가 주어진다. 두 배열을 합친 다음 정렬해서 출력하는 프로그램을 작성하시오.

입력

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

둘째 줄에는 배열 A의 내용이, 셋째 줄에는 배열 B의 내용이 주어진다. 배열에 들어있는 수는 절댓값이 109보다 작거나 같은 정수이다.

출력

첫째 줄에 두 배열을 합친 후 정렬한 결과를 출력한다.

예제 입력 1

2 2

3 5

2 9

예제 출력 1

2 3 5 9

예제 입력 2

2 1

4 7

1

예제 출력 2

1 4 7

예제 입력 3

4 3

2 3 5 9

1 4 7

예제 출력 3

1 2 3 4 5 7 9

풀이 1.

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] arr = new int[n + m];

        st = new StringTokenizer(br.readLine());
        int idx = 0;
        for(int i = 0; i < n; i++) {
            arr[idx++] = Integer.parseInt(st.nextToken());
        }
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < m; i++) {
            arr[idx++] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr);
        for(int num : arr) {
            sb.append(num + " ");
        }
        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}

처음부터 하나의 배열에 받아서 정렬한다.

풀이 2.

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        st = new StringTokenizer(br.readLine());
        int[] arr1 = new int[n];
        for(int i = 0; i < n; i++) {
            arr1[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr1);

        st = new StringTokenizer(br.readLine());
        int[] arr2 = new int[m];
        for(int i = 0; i < m; i++) {
            arr2[i] = Integer.parseInt(st.nextToken());
        }
        Arrays.sort(arr1);

        int idx1 = 0, idx2 = 0;
        for(int i = 0; i < n+m; i++) {
            if(idx1 == n) {
                sb.append(arr2[idx2++] + " ");
                continue;
            }
            if(idx2 == m) {
                sb.append(arr1[idx1++] + " ");
                continue;
            }

            if(arr1[idx1] <= arr2[idx2]) {
                sb.append(arr1[idx1++] + " ");
            }else {
                sb.append(arr2[idx2++] + " ");
            }
        }

        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}

두 배열을 받아서 머지소트처럼 합친다.

www.acmicpc.net/problem/10816

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 몇 개 가지고 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 몇 개 가지고 있는 숫자 카드인지 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다.

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 몇 개 가지고 있는지를 공백으로 구분해 출력한다.

예제 입력 1

10

6 3 2 10 10 10 -10 -10 7 3

8

10 9 -5 2 3 4 5 -10

예제 출력 1

3 0 0 1 2 0 0 2

풀이 1.

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = null;

        int n = Integer.parseInt(br.readLine());
        int[] cards = new int[20000001];  // input의 범의 -천만~천만, 음수까지 처리하기 위해 배열 크기 2천만으로
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            int input = Integer.parseInt(st.nextToken());
            cards[input + 10000000] += 1;
        }

        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < m; i++) {
            int target = Integer.parseInt(st.nextToken());
            sb.append(cards[target + 10000000] + " ");
        }

        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}

숫자 카드 1 문제와 거의 동일한 문제.

똑같이 이분탐색으로 풀려고 했으나 실패했다.

절반씩 나누어 검사를 하면서 필연적으로 소실되는 인덱스가 존재하기 때문에 각 숫자들의 개수를 온전히 셀 수 없었기 때문이다.

배열만을 사용한 코드로 문제를 해결했다.

입력되는 숫자의 범위가 -10,000,000 ~ 10,000,000 이기 때문에 음수까지 처리하기 위해서 2천만 크기의 배열을 사용했다.

풀이 2.

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static int lowerBound(int[] arr, int target) {
        int min = 0;
        int max = arr.length;

        while(min < max) {
            int mid = (min + max) / 2;
            if(arr[mid] >= target) {
                max = mid;
            }else {
                min = mid + 1;
            }
        }
        return max;
    }

    public static int upperBound(int[] arr, int target) {
        int min = 0;
        int max = arr.length;

        while(min < max) {
            int mid = (min + max) / 2;
            if(arr[mid] <= target) {
                min = mid + 1;
            }else {
                max = mid;
            }
        }
        return max;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = null;

        int n = Integer.parseInt(br.readLine());
        int[] cards = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            cards[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(cards);
        int m = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
        while(st.hasMoreTokens()) {
            int target = Integer.parseInt(st.nextToken());
            int lower = lowerBound(cards, target);
            int upper = upperBound(cards, target);

            int ans = upper - lower;
            sb.append(ans + " ");
        }

        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}

이분탐색을 사용해 lowerBound, upperBound를 직접 구현하여 풀 수도 있다.

2천만짜리 배열을 만들 필요가 없으니 메모리는 줄지만 시간은 좀 더 느리게 나온다.

lowerBound, upperBound 코드는 그냥 외워버리자.

인덱스가 너무 헷갈린다..

www.acmicpc.net/problem/10815

문제

숫자 카드는 정수 하나가 적혀져 있는 카드이다. 상근이는 숫자 카드 N개를 가지고 있다. 정수 M개가 주어졌을 때, 이 수가 적혀있는 숫자 카드를 상근이가 가지고 있는지 아닌지를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이가 가지고 있는 숫자 카드의 개수 N(1 ≤ N ≤ 500,000)이 주어진다. 둘째 줄에는 숫자 카드에 적혀있는 정수가 주어진다. 숫자 카드에 적혀있는 수는 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다. 두 숫자 카드에 같은 수가 적혀있는 경우는 없다.

셋째 줄에는 M(1 ≤ M ≤ 500,000)이 주어진다. 넷째 줄에는 상근이가 가지고 있는 숫자 카드인지 아닌지를 구해야 할 M개의 정수가 주어지며, 이 수는 공백으로 구분되어져 있다. 이 수도 -10,000,000보다 크거나 같고, 10,000,000보다 작거나 같다

출력

첫째 줄에 입력으로 주어진 M개의 수에 대해서, 각 수가 적힌 숫자 카드를 상근이가 가지고 있으면 1을, 아니면 0을 공백으로 구분해 출력한다.

예제 입력 1

5

6 3 2 10 -10

8

10 9 -5 2 3 4 5 -10

예제 출력 1

1 0 0 1 1 0 0 1

풀이 .

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = null;

        int n = Integer.parseInt(br.readLine());
        int[] cards = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            cards[i] = Integer.parseInt(st.nextToken());
        }

        int m = Integer.parseInt(br.readLine());
        int[] numbers = new int[m];
        int[] answer = new int[m];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < m; i++) {
            numbers[i] = Integer.parseInt(st.nextToken());
        }

        // numbers에 있는 m가지 숫자에 대해 이분탐색을 모두 수행
        Arrays.sort(cards);
        for(int i = 0; i < m; i++) {
            int target = numbers[i];
            int min = 0;
            int max = n-1;
            int mid = (min + max) / 2;

            while(min <= max) {
                if(cards[mid] >= target) {
                    if(cards[mid] == target) {
                        answer[i] = 1;
                        break;
                    }
                    max = mid - 1;
                }else {
                    min = mid + 1;
                }
                mid = (min + max) / 2;
            }
        }

        for(int ans : answer) {
            sb.append(ans + " ");
        }
        bw.write(sb.toString());
        br.close();
        bw.flush();
        bw.close();
    }
}

이전 문제들 때문에 고정관념에 사로잡혀 난이도는 낮지만 오히려 더 어렵게 느껴졌던 문제.

N, M 모두 상한이 50만이기 때문에 완전탐색을 하면 O(25 * 10^10) 으로 시간초과가 날 것이다.

이분탐색의 시간 복잡도는 O(logN)이다.  

M개의 숫자에 대해서 모두 이분탐색을 수행하면 O(M * logN)으로 수행이 가능하다.

이는 어림잡아 천만대 숫자 안으로 충분히 처리가 가능해진다.

www.acmicpc.net/problem/2110

문제

도현이의 집 N개가 수직선 위에 있다. 각각의 집의 좌표는 x1, ..., xN이고, 집 여러개가 같은 좌표를 가지는 일은 없다.

도현이는 언제 어디서나 와이파이를 즐기기 위해서 집에 공유기 C개를 설치하려고 한다. 최대한 많은 곳에서 와이파이를 사용하려고 하기 때문에, 한 집에는 공유기를 하나만 설치할 수 있고, 가장 인접한 두 공유기 사이의 거리를 가능한 크게 하여 설치하려고 한다.

C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대로 하는 프로그램을 작성하시오.

입력

첫째 줄에 집의 개수 N (2 ≤ N ≤ 200,000)과 공유기의 개수 C (2 ≤ C ≤ N)이 하나 이상의 빈 칸을 사이에 두고 주어진다. 둘째 줄부터 N개의 줄에는 집의 좌표를 나타내는 xi (0 ≤ xi ≤ 1,000,000,000)가 한 줄에 하나씩 주어진다.

출력

첫째 줄에 가장 인접한 두 공유기 사이의 최대 거리를 출력한다.

예제 입력 1

5 3

1

2

8

4

9

예제 출력 1

3

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
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 c = Integer.parseInt(st.nextToken());
        int[] houses = new int[n];
        for(int i = 0; i < n; i++) {
            houses[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(houses);
        long min = 1;
        long max = houses[n-1] - houses[0];
        long mid = (min + max) / 2;

        long ans = 1;
        while(min <= max) {
            long cnt = 1;  // 맨 처음 집은 처음부터 포함
            int previous = houses[0];  // 최근에 공유기를 놓은 집
            for(int i = 1; i < n; i++) {
                int dist = houses[i] - previous;  // 최근에 공유기 놓은 집부터 다음 타겟 집까지의 거리
                if(dist >= mid) {  // 무작정 mid 간격으로 놓는 것이 아니다
                    previous = houses[i];
                    cnt += 1;
                }
            }

            if(cnt >= c) {
                ans = Math.max(ans, mid);
                min = mid + 1;
            }else {
                max = mid - 1;
            }
            mid = (min + max) / 2;
        }
        System.out.println(ans);
    }
}

다른 이분탐색 문제보다 더 어려웠다.

공유기를 두는 최소간격의 최대를 구해야 한다. (공유기 사이의 간격은 적어도 K만큼 떨어져있어야 한다. 이때 K의 최대)

처음에는.. 무작정 mid 간격마다 공유기를 놓아서 구간 안에 들어가는 공유기의 개수만 C에 맞춰주면 된다고 생각했다.

그런데 이런 방식으로 짜면.. 들어가는 공유기의 개수 자체는 맞출 수 있지만 공유기 사이의 최소간격의 최대를 구할 수는 없다.

왜냐하면 집이 없는 좌표에는 공유기를 놓지 않기 때문이다.

공유기는 반드시 집이 있는 좌표에만 들어갈 수밖에 없다.

가장 최근에 공유기를 놓은 좌표를 저장하고 다음 집까지의 거리를 구했다. 그 거리가 mid를 넘어가지 못한다면 공유기를 놓지 않고 그 다음 집을 타겟으로 삼았다.

최근에 공유기를 놓은 집과 타겟으로 삼은 집 사이의 거리가 mid 이상일 때만 타겟지점에 공유기를 놓을 수 있다.

(처음에 짠 코드는 그냥 무작정 mid 칸 이후에 공유기를 놓아서 집이 아닌 곳에도 공유기를 놓았다.)

www.acmicpc.net/problem/2805

문제

상근이는 나무 M미터가 필요하다. 근처에 나무를 구입할 곳이 모두 망해버렸기 때문에, 정부에 벌목 허가를 요청했다. 정부는 상근이네 집 근처의 나무 한 줄에 대한 벌목 허가를 내주었고, 상근이는 새로 구입한 목재절단기를 이용해서 나무를 구할것이다.

목재절단기는 다음과 같이 동작한다. 먼저, 상근이는 절단기에 높이 H를 지정해야 한다. 높이를 지정하면 톱날이 땅으로부터 H미터 위로 올라간다. 그 다음, 한 줄에 연속해있는 나무를 모두 절단해버린다. 따라서, 높이가 H보다 큰 나무는 H 위의 부분이 잘릴 것이고, 낮은 나무는 잘리지 않을 것이다. 예를 들어, 한 줄에 연속해있는 나무의 높이가 20, 15, 10, 17이라고 하자. 상근이가 높이를 15로 지정했다면, 나무를 자른 뒤의 높이는 15, 15, 10, 15가 될 것이고, 상근이는 길이가 5인 나무와 2인 나무를 들고 집에 갈 것이다. (총 7미터를 집에 들고 간다) 절단기에 설정할 수 있는 높이는 양의 정수 또는 0이다.

상근이는 환경에 매우 관심이 많기 때문에, 나무를 필요한 만큼만 집으로 가져가려고 한다. 이때, 적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 나무의 수 N과 상근이가 집으로 가져가려고 하는 나무의 길이 M이 주어진다. (1 ≤ N ≤ 1,000,000, 1 ≤ M ≤ 2,000,000,000)

둘째 줄에는 나무의 높이가 주어진다. 나무의 높이의 합은 항상 M보다 크거나 같기 때문에, 상근이는 집에 필요한 나무를 항상 가져갈 수 있다. 높이는 1,000,000,000보다 작거나 같은 양의 정수 또는 0이다.

출력

적어도 M미터의 나무를 집에 가져가기 위해서 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

예제 입력 1

4 7

20 15 10 17

예제 출력 1

15

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
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 m = Integer.parseInt(st.nextToken());
        int[] trees = new int[n];
        st = new StringTokenizer(br.readLine());
        for(int i = 0; i < n; i++) {
            trees[i] = Integer.parseInt(st.nextToken());
        }

        long min = 1;
        long max = Arrays.stream(trees).max().getAsInt();
        long mid = (min + max) / 2;

        long ans = 0;
        while(min <= max) {
            long sum = 0;
            for(int i = 0; i < n; i++) {
                if(trees[i] > mid) {  // 조건 취하지 않으면 음수가 더해져 답을 해친다
                    sum += trees[i] - mid;
                }
            }
            if(sum >= m) {
                ans = Math.max(ans, mid);
                min = mid + 1;
            }else {
                max = mid - 1;
            }
            mid = (min + max) / 2;
        }
        System.out.println(ans);
    }
}

mid 미터에서 얻을 수 있는 나무의 길이를 셀 때 if(trees[i] > mid) 조건을 붙여줘야 한다.

그렇지 않으면 mid 미터보다 작은 나무의 경우에서는 음수가 더해져 정상적인 값을 출력할 수 없다.

www.acmicpc.net/problem/1654

문제

집에서 시간을 보내던 오영식은 박성원의 부름을 받고 급히 달려왔다. 박성원이 캠프 때 쓸 N개의 랜선을 만들어야 하는데 너무 바빠서 영식이에게 도움을 청했다.

이미 오영식은 자체적으로 K개의 랜선을 가지고 있다. 그러나 K개의 랜선은 길이가 제각각이다. 박성원은 랜선을 모두 N개의 같은 길이의 랜선으로 만들고 싶었기 때문에 K개의 랜선을 잘라서 만들어야 한다. 예를 들어 300cm 짜리 랜선에서 140cm 짜리 랜선을 두 개 잘라내면 20cm는 버려야 한다. (이미 자른 랜선은 붙일 수 없다.)

편의를 위해 랜선을 자르거나 만들 때 손실되는 길이는 없다고 가정하며, 기존의 K개의 랜선으로 N개의 랜선을 만들 수 없는 경우는 없다고 가정하자. 그리고 자를 때는 항상 센티미터 단위로 정수길이만큼 자른다고 가정하자. N개보다 많이 만드는 것도 N개를 만드는 것에 포함된다. 이때 만들 수 있는 최대 랜선의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 후 K줄에 걸쳐 이미 가지고 있는 각 랜선의 길이가 센티미터 단위의 정수로 입력된다. 랜선의 길이는 231-1보다 작거나 같은 자연수이다.

출력

첫째 줄에 N개를 만들 수 있는 랜선의 최대 길이를 센티미터 단위의 정수로 출력한다.

예제 입력 1

4 11

802

743

457

539

예제 출력 1

200

풀이 .

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
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 k = Integer.parseInt(st.nextToken());
        int n = Integer.parseInt(st.nextToken());
        int[] lan = new int[k];
        for(int i = 0; i < k; i++) {
            lan[i] = Integer.parseInt(br.readLine());
        }

        long min = 1;
        long max = Arrays.stream(lan).max().getAsInt();
        long mid = (min + max) / 2;

        long ans = 0;
        while(min <= max) {
            long sum = 0;
            for(int i = 0; i < k; i++) {
                sum += lan[i] / mid;
            }
            if(sum >= n) {
                ans = Math.max(ans, mid);
                min = mid + 1;
            }else {
                max = mid - 1;
            }
            mid = (min + max) / 2;
        }
        System.out.println(ans);
    }
}

이분탐색 문제.

자료형 문제를 생각하지 못해 애를 먹었다.

어차피 4바이트 밖에 차이 안 나니까 이분탐색에선 그냥 웬만하면 long을 사용하자.