📙 Algorithm Solving/Java
📙[Algo] 24.07.09 알고리즘
혜덕hyeduck
2024. 7. 9. 20:33
알고리즘 문제) BOJ 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
- 중간값이면서 가장 질 좋은 애를 찾아야 함
- 질 좋은 애들이 더 많은 영역이 존재한다는 의미이므로 e = mid - 1
- 0보다 작다면
- 아직 mid보다 질 나쁜 애들이 더 많은 영역만 존재한다는 의미이므로 s = mid + 1
- mid값을 키워서 최대한 중간값에 가깝게 만들어줘야 함
- 아직 mid보다 질 나쁜 애들이 더 많은 영역만 존재한다는 의미이므로 s = mid + 1
- upCnt가 0보다 크다면
코드
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. 흩날리는 시험지 속에서 내 평점이 느껴진거야
문제 요약
- N개의 시험지가 주어진다.
- 이때, 주어진 시험지 순서대로 K개의 그룹으로 나눈 뒤, 각 그룹의 문제 점수의 합을 구하여, 그 중 최솟값이 최대가되는 경우 찾기
시간 제한
- 1초
입력
- 시험지 개수 N, 시험지를 나눌 그룹 수 K
- 1 ≤ K ≤ N ≤ 10만
- 각 시험지마다 맞은 문제 개수 x
- 0 ≤ x ≤ 20
출력
- 받을 수 있는 최대 점수를 출력
접근법
- 받을 수 있는 최대 점수를 이분탐색으로 찾아가며, 조건을 충족하는 경우 중 가장 최대가 되는 경우를 찾으려 했다.
- 이때 최대 점수를 mid 변수에 담고,
- for문을 돌며, 점수의 합계가 mid보다 크거나 같을 경우 하나의 그룹으로 판단하여 카운트 + 1 해줬다.
- 그룹 점수의 최솟값이 곧 mid가 되어야하므로 무조건 크거나 같은 경우일 것
- for문을 돌며, 점수의 합계가 mid보다 크거나 같을 경우 하나의 그룹으로 판단하여 카운트 + 1 해줬다.
- 만약 카운트 한 값이 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);
}
}