본문 바로가기
Algorithm 알고리즘/SWEA 스웨아

SWEA_2115_벌꿀채취_모의역량

by 개복치96 2023. 2. 23.
반응형

 

 

이 문제를 처음 보았을 때는 주어진 벌통의 크기인 배열에서 서로 겹치지 않게 가로로 연속된 M칸을 뽑아서 비교하는 것을 생각했었다.
하지만 결국 우리는 꿀의 양과 값까지 고려해야한다.
따라서 뽑기 전에 꿀의 값을 최대로 할 수 있는 것들을 남겨놓으려고 한다.
예시를 들며 설명해보겠다.

1. 꿀의 양에 대한 정보가 담긴 배열을 바탕으로 최대 수익 정보가 담긴 배열을 만들어준다.

6 1 9 7
9 8 5 8
3 4 5 3
8 2 6 7

위와 같은 배열이 주어졌다고 가정해보자.
N은 4이고 M은 2이고, C는 10이다.
M이 2이기에 1행을 보았을때  [(0,0),(0,1)] | [(0,1),(0,2)] | [(0,2),(0,3)] 가 선택될 수 있다.


[(0,0),(0,1)] 을 보면

6 1

위와 같은 값이 저장되어 있다. 이때 최대 수익을 구하면 6*6 + 1*1 = 37 이다.

그렇다면 [ (0,1),(0,2) ] 을 선택하면 어떻게 될까?

9 7

위와 같은 값이 저장되어있다.
이때 (0,0),(0,1)을 선택했던 것 처럼 하게되면 9 + 7은 16이 되어 두칸 모두에서 채취를 할 수 없다.
즉, M의 크기에 따라서 선택한 것은 채취의 대상이고
그 대상을 어떻게 채취해서 최대 수익을 낼지는 우리가 정하는 것이다.

그렇다면 9,7이 채취의 대상일때 채취를 하는 경우는 총 4가지이다.
- 첫번째 아무것도 채취하지 않는다.
- 두번째 9만 채취한다.
- 세번째 7만 채취한다.
- 네번째 9와 7 모두 채취한다.
이 4가지 중에서 어떤 것이  C이하이면서 최대수익일지는 해봐야한다. 즉 공식이 없다.
따라서 부분집합을 구하는 방법을 이용하여 최대 수익을 계산한다.
이 경우에는 2번 9만 채취하는 방법이 최대 수익이다.

자, 그렇다면
[ (0,0),(0,1) ] 을 선택해서 채취했을때의 최대 수익과
[ (0,1),(0,2) ] 을 선택해서 채취했을때의 최대 수익을 계산하였다.
그렇다면 이 최대 수익의 정보를 배열에 저장해보자.

최대 수익을 저장하기 위한 profit이라는 배열을 만들어준다.
[ (0,0),(0,1) ] 을 선택해서 채취했을때의 최대 수익을 profit 배열의 (0,0) 자리에 저장한다.
[ (0,1),(0,2) ] 을 선택해서 채취했을때의 최대 수익을 profit 배열의 (0,1) 자리에 저장한다.

뭔가 규칙성을 보이지 않는가?
1행에서 2칸씩 선택하면  [ (0,0),(0,1) ] [ (0,0),(0,1) ] [ (0,1),(0,2) ]  3가지 경우가 있고,
각 경우의 최대 수익을 부분집합을 통해 계산해서 각 경우에 선행되는 인덱스에 값으로 넣어준다.

6 1 9 7
9 8 5 8
3 4 5 3
8 2 6 7
37 82 81
81 64 64
25 41 34
68 40 49

이를 정리하면 위와 같다.
벌통이 4 * 4 라면 → 최대수익배열은 4 * 3이다.
이를 변수로 나타내면
벌통: N * N → 최대수익: N * (N - M + 1) 이다.

자 그러면 이제 최대 수익 배열까지 만들어주었다.
최대 수익 배열은 두칸이 채취의 대상일때 최고의 수익을 낼 수 있는 선택이 이미 이루어진 상태이다.
따라서 일꾼 두명이 벌통의 가로로 연속된 두칸(M이 2일 경우)을 겹치지 않도록 선택만하면,
그 선택에 따른 수익을 계산할 수 있다.

일꾼 두명을 A와 B라고 하자.
A가 먼저 선택을 하고 나서 B가 선택을 한다고 하면,
A가 선택한 행만 아니라면 B가 어디를 선택하든 겹치지 않는다.
그리고 애초에 최대 수익을 나타낸 이차원 배열 자체가 M칸을 고르는 것으로 짠 것이기에
최대수익배열에서 선택 작업을 진행하면 겹치지 않는다.

따라서 최대 수익 배열에서 같은 행에서 선택하는 경우와 다른 행에서 선택하는 두가지 경우로 나누어
진행한다.

아래는 코드이다.

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class Main {
	static int N, M, C, ans; // 통크기, 선택 벌통 수, 꿀의 최대양, 테스트 케이스 정답
	static int[][] map, profit; // profit: 각 좌표에서 이익의 최대 양
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("src/data/sw-input2115.txt"));
		Scanner sc = new Scanner(System.in);
		int T = sc.nextInt(), t = 0;
		while(t++ < T) {
			N = sc.nextInt();
			M = sc.nextInt();
			C = sc.nextInt();
			map = new int[N][N]; //벌통의 크기만큼 꿀의 양에대한 정보를 담는 map배열 생성
			profit = new int[N][N-M+1]; //벌통의 크기만큼 이익의 정보를 담는 profit 배열 생성
			for(int i = 0; i < N; i++) { //꿀의 양에 대한 정보를 입력한다.
				for (int j = 0; j < N; j++) {
					map[i][j] = sc.nextInt();
				}
			}
			
			//기본 데이터 세팅이 되었으니 이제 두가지 작업을 할 것이다.
			//이익부터 설정한다.
			setProfit(); //각 좌표 자리에서의 최대 이익
			setPosition(); //조합의 자리 결정
			System.out.println("#" + t + " " + ans);
			ans = 0; // 정답은 우선 0으로 초기화
		}
		
	}
	//일꾼 1의 위치를 map[i][j]이라고 할때 일꾼 2의 위치
	private static void setPosition() {
		for(int i = 0; i < N; i++) {
			for(int j = 0; j <= N - M; j++) {
				//N-M을 해주는 이유는 일꾼 A도 두칸을 차지하고, 일꾼 B도 두칸을 차지해서 앞에있는 칸을 기준으로 하기 때문이다.
				//즉, 4 x 4여도 M이 2일때 포지션은 4 x 3 으로 표시된다.
				//일꾼 1의 위치를 map[i][j]이라고 할때
				//일꾼 2의 위치: 같은 행일때 - 일꾼 1의 위치와 같은 행에 있을 때(행=row)
				for(int c = j + M; c <= N - M; c++) { //같은 행이니까 row는 필요없다.
					ans = Math.max(ans, profit[i][j] + profit[i][c]);
				}
				//다른행일때
				for(int r = i+1; r < N; r++) {
					for(int c = 0; c <= N - M; c++) {
						ans = Math.max(ans, profit[i][j] + profit[r][c]);						
					}
				}
			}
		}
		
	}
	
	private static void setProfit() {
		for(int i = 0; i < N; i++) {
			for (int j = 0; j <= N - M; j++) {
				setMaxProfit(i,j, 0, 0, 0);
			}
		}
	}
	
	private static void setMaxProfit(int i, int j, int cnt, int cSum, int pSum) {
		if(cSum > C) return;
		if(cnt == M) { //M의 크기만큼 비교해야함. 왜냐하면 M개의 수로 만들 수 있는 모든 부분집합을 가지고 오니까.
			profit[i][j-M] = Math.max(profit[i][j - M], pSum);
			return;
		}
		setMaxProfit(i, j+1, cnt+1, cSum, pSum); //선택하지 않음
		setMaxProfit(i, j+1, cnt+1, cSum + map[i][j], pSum + map[i][j] * map[i][j]); 
        //선택했음
	}
/*
N개의 수로 만드는 부분집합이라고 할 때

private static void subset(int cnt) {
		if(cnt == N) {
			for(int i = 0; i < N; i++) {
				if(!selected[i]) continue; // 선택되지 않으면 나가고 선택된거면 아래로
				System.out.println(input[i] + " ");
			}
			System.out.println();
			return;
		}
		selected[cnt] = true;
		subset(cnt + 1);
		selected[cnt] = false;
		subset(cnt + 1);
	} 
*/
}

 

추가!!!

setMaxProfit(int i, int j, int cnt, int cSum, int pSum)
여기서 profit[i][j-M] = Math.max(profit[i][j-M], pSum);

이 부분에서 j-M을 해주는 것에 유의해야한다. M을 꼭 빼줘야한다.
profit[i][j] 으로 하게되면 배열인덱스 초과 오류가 난다.
가로로 벌통을 하나씩 증가해주면서 최댓값을 구하기때문에
예를 들어 M=2라고 하면 j는 2가 된 후에 j++로 3이 되고 그 상태에서 재귀가 시작되려할때 return으로 나가게 된다.
따라서 j-M을 해주어야한다.

 

반응형

'Algorithm 알고리즘 > SWEA 스웨아' 카테고리의 다른 글

[SWEA][D4] - Ladder1(1210번)  (0) 2023.02.09