📙[Algo] 24.07.09 알고리즘

알고리즘 문제) BOJ 10227. 삶의 질

• 링크 : https://www.acmicpc.net/problem/10227

문제 요약

• R*C 격자의 도시가 존재
• 이때 각 칸에는 퀄리티 랭크가 표시되어있는데, 범위는 1~R*C내에서 표현된다.
• 퀄리티랭크가 작을수록 질이 높은 것이고, 클수록 질이 낮은 것이다.
• 이때, 도시 안에서 H*W(H홀수, W홀수)크기의 영역을 돌며 퀄리티랭크의 중간값 중 가장 질이 높은(수가 가장 작은)값을 찾으려 한다.
  • 영역안에서 중간값보다 작은 랭크 수와 큰 랭크수가 같을 경우 중간값이라 정의
• 이때 H*W영역 중 퀄리티랭크의 중간값중 가장 질이 높은 값을 찾아라

시간 제한

• 5초

입력

• 4개의 정수 R,C,H,W
  • R과 C는 도시 크기이며, 가능한 범위는 1~3000
  • H와 W는 영역의 크기이며 항상 홀수이고, 1 ≤ H ≤ R, 1 ≤ W ≤ C
• R개의 줄에 각각 C개의 퀄리티 랭크 수가 주어진다.

출력

• 퀄리티랭크의 중간값 중 가장 질이 높은 값 출력

접근법

• 누적합 + 이분탐색(매개변수 탐색)
• 이분탐색으로 중간값을 의미하는 mid변수를 지정해준다.
• 누적합이 필요한 이유는 매 케이스마다 영역을 돌며, 중간값이 있는지 판단하면 안되기 때문이다
  • 그래서 도시를 돌며
    • mid보다 큰 값은 누적합 배열 prefix에 -1,
    • 작은 값 은 prefix에 +1
    • 같은 값은 prefix에 0
  • 이후 prefix배열을 누적합 배열로 만든다.
• 누적합 배열 prefix을 사용해서 영역 H*W크기만큼 돌며 영역의 합이 0이상인 경우를 찾는다.
  • 영역의 합계가 0인 경우, same 카운트 + 1
  • 0보다 큰 경우는, mid보다 질 좋은 수들이 더 많이 분포한 영역으로 upCnt 카운트 + 1
• 만약 sum이 0보다 크다면
  • mid가 중간값을 의미하므로 answer변수에 담아주고,
  • 최대한 질 좋은 애를 찾아야하므로 e = mid - 1 (숫자가 작을수록 질 좋음)
• 그게 아닐 경우,
  • upCnt가 0보다 크다면
    • 질 좋은 애들이 더 많은 영역이 존재한다는 의미이므로 e = mid - 1
      • 중간값이면서 가장 질 좋은 애를 찾아야 함
  • 0보다 작다면
    • 아직 mid보다 질 나쁜 애들이 더 많은 영역만 존재한다는 의미이므로 s = mid + 1
      • mid값을 키워서 최대한 중간값에 가깝게 만들어줘야 함

코드

import java.io.*;
import java.util.*;
import java.util.function.Supplier;

public class Main {
    static int R, C, H, W;
    static int[][] arr;
    static int[][] prefix;

    static int binarySearch(int start, int end) {
        int s = start, e = end, mid, answer = -1;
        while (s <= e) {
            mid = (s + e) / 2; // quality rank의 중간값 가정

            // mid보다 쟉은 값은 1, 큰 값은 -1, 같은 값은 0
            // 퀄리티랭크가 작을수록 좋음
            // 3000*3000
            for (int i = 1; i < R + 1; i++) {
                for (int j = 1; j < C + 1; j++) {
                    if (arr[i][j] > mid) prefix[i][j] = -1; // mid보다 퀄리티랭크 높은애들(질낮)
                    else if (arr[i][j] < mid) prefix[i][j] = 1; // mid보다 퀄리티랭크 낮은애들(질높)
                    else prefix[i][j] = 0;
                }
            }

            // 2차원 누적합 배열 만들기  3000*3000
            for (int i = 1; i < R + 1; i++) {
                for (int j = 1; j < C + 1; j++) {
                    prefix[i][j] = prefix[i][j] + prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1];
                }
            }

            // H*W크기의 영역의 누적합이 0인것 찾기 -> 중간값을 의미함
            int sum, upCnt = 0, same = 0;
            for (int i = H; i < R + 1; i++) {
                for (int j = W; j < C + 1; j++) {
                    sum = prefix[i][j] - prefix[i - H][j] - prefix[i][j - W] + prefix[i - H][j - W];
                    if (sum > 0) upCnt++; // 퀄리티랭크 낮은 수(질높)가 많은 영역이 존재하면 카운트
                    else if (sum == 0) same++;
                }
            }

            if (same > 0) {
                // mid값이 중간값이니 answer 변수에 저장 
                answer = mid;
                // 최대한 퀄리티랭크가 낮은 애를 찾아야 하므로
                e = mid - 1;
            } else {
                if (upCnt > 0) {
                    // 퀄리티랭크가 더 낮은 수를 찾을 것
                    e = mid - 1;
                } else {
                    s = mid + 1;
                }
            }
        }

        return answer;
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        H = Integer.parseInt(st.nextToken());
        W = Integer.parseInt(st.nextToken());

        arr = new int[R + 1][C + 1];
        prefix = new int[R + 1][C + 1];
        int min = 1 << 30, max = 0 ;
        for (int i = 1; i < R + 1; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j < C + 1; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
                min = Math.min(min, arr[i][j]);
                max = Math.max(max, arr[i][j]);
            }
        }

        int ans = binarySearch(min, max);

        System.out.println(ans);
    }
}

 

알고리즘 문제) BOJ 17951. 흩날리는 시험지 속에서 내 평점이 느껴진거야

• 링크 : https://www.acmicpc.net/problem/17951

문제 요약

• N개의 시험지가 주어진다.
• 이때, 주어진 시험지 순서대로 K개의 그룹으로 나눈 뒤, 각 그룹의 문제 점수의 합을 구하여, 그 중 최솟값이 최대가되는 경우 찾기

시간 제한

• 1초

입력

• 시험지 개수 N, 시험지를 나눌 그룹 수 K
  • 1 ≤ K ≤ N ≤ 10만
• 각 시험지마다 맞은 문제 개수 x
  • 0 ≤ x ≤ 20

출력

• 받을 수 있는 최대 점수를 출력

접근법

• 받을 수 있는 최대 점수를 이분탐색으로 찾아가며, 조건을 충족하는 경우 중 가장 최대가 되는 경우를 찾으려 했다.
• 이때 최대 점수를 mid 변수에 담고,
  • for문을 돌며, 점수의 합계가 mid보다 크거나 같을 경우 하나의 그룹으로 판단하여 카운트 + 1 해줬다.
    • 그룹 점수의 최솟값이 곧 mid가 되어야하므로 무조건 크거나 같은 경우일 것
• 만약 카운트 한 값이 K보다 크다면 최대 점수를 너무 작게 설정한 것이므로 s= mid + 1,
• K보다 작다면 최대 점수를 너무 크게 설정한 것이므로 e = mid - 1해줬고,
• 만약 같을 경우 일단 정답 후보이므로 answer변수에 담은 후, 그 중 가장 최대인 값을 찾아야 하므로 s = mid + 1 했다.

코드

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

public class Main {
    static int N, K;
    static int[] arr;

    static int binarySearch(int start, int end) {
        int s = start, e = end, mid, sum, cnt = 0;
        int answer = -1;
        while (s <= e) {
            mid = (s + e) / 2; // 문제 합의 최솟값 (즉 받을 수 있는 최대 점수)

            sum = 0;
            cnt = 0;
            for (int i = 0; i < N; i++) {
                sum += arr[i];

                // 문제 합의 최솟값을 mid로 가정했으니 그룹의 합계는 mid보다 무조건 크거나 같아야함
                if (sum >= mid) {
                    // 크거나 같은 순간이 오면
                    cnt++; // 그룹수 카운트 + 1
                    sum = 0; // 그룹 합계는 0으로 초기화
                }
            }

            if (cnt < K) {
                // 그룹 개수가 K보다 작으면
                // 최소합을 줄여야 함
                e = mid - 1;
            } else if (cnt > K) {
                // 그룹 개수가 K보다 크면
                // 최소합을 늘려야함
                s = mid + 1;
            } else {
                // 그룹 개수와 K가 같다면 일단 정답 변수에 넣어주고
                answer = mid;
                // 최대한 점수를 크게 가져야 하므로 s를 늘린다.
                s = mid + 1;
            }
        }

        return answer;
    }

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());

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

        int ans = binarySearch(0, sum);

        System.out.println(ans);

    }
}