문제분석
N * N 개의 벌통이 정사각형 모양으로 배치
각 칸의 숫자는 벌통에 있는 꿀의 양을 나타냄, 이때 주어진 과정으로 벌꿀을 채취하여 최대한 많은 수익을 얻으려고 한다.
두명의 일꾼이 있다 . 이때 꿀을 채취할 수 있는 벌통의 수M이 주어지고 가로로 연속되도록M개의 벌통을 선택한다. 단, 벌통이 겹치면 안된다.
여기에서 가장 중요한건 두명의 일꾼과 가로로 연속적으로 M으로 이어진 칸을 골라야한다는 것이다.
즉, 두개의 연속적인 길이 m의 칸을 골라야 한다.
여기에서 전체의 부분집합을 구하되, 가로 방향으로 M개의 연속적인 칸을 구해야한다.
더불어 겹치지 않아야 한다.
- 꿀을 채취하여 용기에 담아야한다. 서로 다른 통에서 채집한 꿀을 넣을 수 없다. 그렇기 때문에
하나의 용기에는하나의 통에서 채집한 꿀만 넣을 수 있다. 이때, 두 일꾼이 채취할 수 있는 꿀의최대양은 C를 넘지 않아야 한다.
앞에서 구한 부분집합에서 조건을 하나 더 추가했다. 해당 부분집합에서 또 C를 넘지 않으면서 가장 큰 값을 구해야한다. 몇개를 선택하나 상관없고, C를 넘지 말아야 한다.
- 채집한 꿀들은 시장에서 팔리는데 용기에 있는 꿀의 양의 제곱이 꿀의 가치가 된다.이때, 가장 수익이 높은 경우의 수익을 구하자
이 부분은 그냥 수익을 구하면 된다. 구한 부분집합에다가 제곱을 해준 다음 더한 값이 가장 큰 값을 리턴하면 된다.
문제 풀이
-
두 일꾼이 채취하는 벌통을 구하자
이는, 부분집합을 구하는 것이다. 주어진 조건에 맞게 필터링 하여 부분집합을 구해보자.
2차원 배열에서의 부분집합이다.
여기에서 가장 큰 난관은 2차원 배열에서 부분집합을 어떻게 구할것인가이다. 2차원 배열을 1차원배열처럼 만들어서 해결할 것이다. 그렇다면 어떻게 할 것인가 ?
번호를 행의 개수만큼 나누면 행의 위치가 나오고 번호를 열의 개수의 나머지를 구하면 열이 나온다는 특징을 이용해서 행과 열을 구할 것이다. 그렇다면, 1차원 배열에서 부분집합을 구하듯이 가능하고, 여기에서 조건에 맞는지만 체크해주면 된다.
dfs통해서 2개의 벌통을 선택하고, 조건에 해당하지 않는 벌통 선택의 경우의 수를 줄여나간다.
조건은 다음과 같다.- 두 벌통이 겹치지 않게 위치해있는가
selected[0] >= selected[1] - (M - 1) - 한 일꾼이 선택한 벌통들이 하나의 열에 위치하고 있는지 확인한다.
(selected[0] + M - 1) / N != selected[0] / N || (selected[1] + M - 1) / N != selected[1] / N
- 두 벌통이 겹치지 않게 위치해있는가
static void dfs(int depth,int idx){
// 두개의 벌통만 선택하고 그 뒤에 연속으로 M-1 개를 자동으로 고르게 하자
if(depth == 2){
// 두개의 벌통을 모두 선택했다
if(selected[0] >= selected[1] - (M-1)) return;
// 벌통 선택은 어짜피 일꾼의 앞뒤가 없기 때문에 뒤 부분만 확인해도 된다
if((selected[0] + M - 1) / N != selected[0] / N || (selected[1] + M - 1) / N != selected[1] / N) return;
// 같은 열에 있는지 확인해야한다
// 채취하는 벌통에서 가장 최대로 나올 수 있는 값을 구해보자
int honey = getHoney(selected[0],selected[1]); // 최대 벌꿀양을 구한다
answer = Math.max(answer,honey);
return;
}
for(int i=idx;i<N*N; i++){
selected[depth] = i;
dfs(depth+1,i+1);
}
}- 조합을 구해주었다면, 해당 조합에서 구할 수 있는 최대 꿀의 양을 구해야한다.
getHoney()를 통하여 최대로 나올 수 있는 꿀의 양을 구해준다.
두 일꾼의 시작 지점을 정한 다음, 각각의 일꾼이 가질 수 있는 벌집의 조합을 모두 구한다. 조합을 구하는 과정에서 두 일꾼 각각의 최대 꿀의 양을 초기화 한다.
static int getHoney(int a,int b){
//최대 벌꿀양을 구하자
sumA = 0;
for(int r=1;r<=M;r++){
// i 만큼 뽑아보자
combination(a,a+M,r,0,0,0,1);
}
sumB = 0;
for(int r=1;r<=M;r++){
combination(b,b+M,r,0,0,0,2);
}
return sumA + sumB;
}static void combination(int start,int end,int r,int depth,int sum,int rev,int type){
if(depth == r){
if(sum > C) return;
if(type == 1) sumA = Math.max(sumA,rev);
else sumB = Math.max(sumB,rev);
return;
}
for(int i=start;i<end;i++){
// 연속으로 꿀을 채취해야하기 때문에 visited 배열이 필요 없다
int h = map[i/N][i%N];
combination(i+1,end,r,depth+1,sum + h,rev + (int) Math.pow(h,2),type);
}
// start 시작지점
// end 마지막 지점
// 뽑을 벌집의 개수
// depth 리턴을 위한 dfs 깊이
// sum 꿀의 합계
// rev 꿀 가치의 합계
// type 일꾼 타입
}코드
문제를 두번정도 다시 풀어보면서 코드의 버전이 조금 다르다.
가장 큰 차이점은 벌집을 고르는데 필터링 하는 로직이 조금 다르다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
* @author onyoo
* @performance
* @category
* @note
* 가로로 연속되도록 M개의 벌통을 선택 (겹치면 안됨)
* 두 일꾼이 채취할 수 있는 꿀의 최대 양은 C를 넘지 않아야 한다
* 꿀의 가치는 꿀의 양의 제곱만큼이다
* 여기에서 "수익의 합이 최대" 가 되는 경우를 찾아야 한다
* 이런 문제가 나오면 어떤걸 구해야하는지에 대해 집중해야한다.
* 다른거 다 필요없고 최대값을 구해야하기 때문에,가장 최대가 되는 값이 나오도록 값을 필터링 하면 된다
* 합계가 C보다 작으면서 제곱의 합이 최대가 되도록 한다. 즉, 최대 값을 갱신하면서 최대 값 보다 작다면 애초에 계산할 필요가 없다
* 이러한 경우 작은 경우의 이후 계산과정을 진행할 수 없도록 하는 것이 좋다 -> 불필요한 계산을 줄이기 위하여
* 여기서 또 중요한 아이디어는 2차원 배열을 1차원 배열처럼 펼쳐놓고 생각하는 것이다
* 2차원 배열에서 M개의 연속된 벌통을 선택하는 경우의 수를 구하기에는 복잡하기 때문에
* 2차원 배열을 1차원 배열처럼 생각한 뒤, 그걸 좌표계로 변경하는 아이디어를 생각해내야한다 이건,자주 사용되니까 알아두자
* @see
* https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu
* @since 2023-10-11
**/
public class Solution {
static int T; // 테스트 케이스의 개수
static int N,M,C; // 벌통의 크기 , 선택할 수 있는 벌통의 개수 , 채취할 수 있는 꿀의 최대 양
static int[][] map; // 벌통
static int[] selected; // 선택한 벌통 저장배열
static int sumA,sumB; // A
static int answer;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
T = Integer.parseInt(br.readLine());
for(int t=1;t<=T;t++){
st = new StringTokenizer(br.readLine()," ");
N = Integer.parseInt(st.nextToken()); // 벌통의 크기
M = Integer.parseInt(st.nextToken()); // 하나의 일꾼이 선택할 수 있는 벌통의 개수
C = Integer.parseInt(st.nextToken()); // 채취할 수 있는 꿀의 최대 양
map = new int[N][N]; // 초기화
selected = new int[2]; // 두명의 일꾼의 시작 지점
answer = 0;
for(int i=0;i<N;i++){
st = new StringTokenizer(br.readLine()," ");
for(int j=0;j<N;j++){
map[i][j] = Integer.parseInt(st.nextToken());
}
}
dfs(0,0);
System.out.printf("#%d %d \n",t,answer);
}
}
static void dfs(int depth,int idx){
// 두개의 벌통만 선택하고 그 뒤에 연속으로 M-1 개를 자동으로 고르게 하자
if(depth == 2){
// 두개의 벌통을 모두 선택했다
if(selected[0] >= selected[1] - (M-1)) return;
// 벌통 선택은 어짜피 일꾼의 앞뒤가 없기 때문에 뒤 부분만 확인해도 된다
if((selected[0] + M - 1) / N != selected[0] / N || (selected[1] + M - 1) / N != selected[1] / N) return;
// 같은 열에 있는지 확인해야한다
// 채취하는 벌통에서 가장 최대로 나올 수 있는 값을 구해보자
int honey = getHoney(selected[0],selected[1]); //
answer = Math.max(answer,honey);
return;
}
for(int i=idx;i<N*N; i++){
selected[depth] = i;
dfs(depth+1,i+1);
}
}
static int getHoney(int a,int b){
//최대 벌꿀양을 구하자
sumA = 0;
for(int r=1;r<=M;r++){
// i 만큼 뽑아보자
combination(a,a+M,r,0,0,0,1);
}
sumB = 0;
for(int r=1;r<=M;r++){
combination(b,b+M,r,0,0,0,2);
}
return sumA + sumB;
}
static void combination(int start,int end,int r,int depth,int sum,int rev,int type){
if(depth == r){
if(sum > C) return;
if(type == 1) sumA = Math.max(sumA,rev);
else sumB = Math.max(sumB,rev);
return;
}
for(int i=start;i<end;i++){ // 연속으로 꿀을 채취해야하기 때문에 visited 배열이 필요 없다
int h = map[i/N][i%N];
combination(i+1,end,r,depth+1,sum + h,rev + (int) Math.pow(h,2),type);
}
}
}import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
/**
* @author 신온유
* @performance
* @category
* @note
* 1.일꾼이 위치를 지정한다 (2차원 배열 -> 1차원 배열, 1차원 배열에서 두개의 수를 선택하는 조합을 모두 탐색한다)
* 2.일꾼 조합에서 유효하지 않은 좌표를 걸러낸다 (연속이어야 하며,겹치지 않아야함,일꾼의 좌표가 하나의 행 안에 있어야 함)
* 3.유효한 일꾼 조합에서 1 ~ M 까지 선택하며 최대 이익을 구한다. 단,캐는 양의 수가 최대 양 C를 넘지 않아야 한다
* @see
* https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu&categoryId=AV5V4A46AdIDFAWu&categoryType=CODE
* @since 2023/10/03
**/
public class Solution {
static int T,N,M,C,max;
static int sumA,sumB;
static int[][] map;
static int[] input;
static boolean[] visited; // 일꾼이 선택하는 꿀통
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
T = Integer.parseInt(br.readLine());
for(int t = 1; t < T + 1; t++){
st = new StringTokenizer(br.readLine()," ");
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
map = new int[N][N];
visited = new boolean[N*N];
max = Integer.MIN_VALUE;
input = new int[2];
for(int i=0;i<N;i++){
st = new StringTokenizer(br.readLine()," ");
for(int j=0;j<N;j++){
map[i][j] = Integer.parseInt(st.nextToken());
}
}
dfs(0,0);
System.out.printf("#%d %d\n",t,max);
}
}
static void dfs(int idx,int depth){
if(depth == 2){
//일꾼의 위치가 유효한지 확인한다
//겹치는 경우
if(input[0] < input[1] && input[0] + M > input[1]) return;
//가로로 연속된건지 확인하기
if(input[0] / N != (input[0] + (M-1)) / N) return; // 첫번째 일꾼의 좌표가 유효하지 않음
if(input[1] / N != (input[1] + (M-1)) / N) return; // 두번째 일꾼의 좌표가 유효하지 않음
max = Math.max(max,getSum(input[0],input[1]));
return;//일꾼 두명이 선택되면
}
for(int i=idx;i<N*N;i++){
input[depth] = i;
dfs(i+1,depth+1);
}
}
static int getSum(int a,int b){
sumA = 0;
for(int i=1;i<=M;i++){
check(0,a,a+M,i,0,0,0);
//일꾼 한명이 뽑을 수 있는 최대 꿀의 양
}
sumB = 0;
for(int i=1;i<=M;i++){
check(1,b,b+M,i,0,0,0);
//일꾼 한명이 뽑을 수 있는 최대 꿀의 양
}
int sum = sumA + sumB;
return sum; // 전체 수익을 더해주고
}
static void check(int type,int start,int end,int r,int sum,int depth,int rev){
// type : 어떤 일꾼
// start : 시작 벌집
// end : 마지막 벌집
// r : r개를 뽑음
// sum : 꿀양의 합
if(depth == r){
// r개 뽑는 경우
if(sum <= C){
// 제한 범위 안이면 이익을 갱신
if(type == 0) sumA = Math.max(sumA,rev);
else sumB = Math.max(sumB,rev);
}
return;
}
for(int i = start; i < end; i++){
int val = map[i/N][i%N];
check(type,i+1,end,r,sum+val,depth+1,rev + (int)Math.pow(val,2));
}
}
}마무리
모의 A형을 준비하면서 가장 공을 많이 들인 문제인 것 같다.
조합이 두번이나 사용되기 때문에 복잡했고,내가 원하는 값에 집중해야한다는 것을 느끼게해준 문제였다.
반갑습니다 ! 백엔드 개발 공부를 하고있습니다.