[SWEA] 2115 - 벌꿀채취

[문제링크]

SW Expert Academy

 

0. x,y지점에서 총 m칸, 최대 무게 c를 고려해 채취할 수 있는 꿀의 최대 가치는 항상 동일하다

  - 미리 연산해서 저장 후 활용한다

 

1. 위에서 구한 가치들 중, 구간이 겹치지 않으면서 가치의 합이 최대가 되는 두 구역을 찾는다

 

2. 가치가 큰 순서로 정렬한다

  - 최대 가치 구간을 한 구간으로 잡고 그리디하게 계산한 최댓값이 최댓값이 아니려면

  - 최대 가치 구간과 영역이 겹치는 다른 구간에서 나온 값만이 가능하다

 

3. 영역이 겹치는 구간의 수는 2*m-1개로, 정렬된 구간을 그만큼만 살펴보면

  - 그리디하게 구한 결과의 가능한 모든 반례를 고려한 결과가 나온다

 

* 최대 가치를 가지는 영역 X와, 이에 속하지 않는 영역중 최대 가치를 가진 Y의 합 : 그리디한 해결법 으로 생각하면

  - X+Y의 가치보다 큰 값은 X와 영역이 일부 겹치는 X'들이 서로 합쳐졌을때만 가능하다

 

  - m이 3이라면, n이 충분할 때 겹치는 영역은 최대 5개(자기 자신 포함) 

  - 1위가 최대영역 X이고, 2,3,4,5위가 X와 영역을 공유할 때 그리디한 답은 1위 + 6위

  - 2,3,4,5위의 해답만이 1+6위의 결과를 넘을 수 있다.

 

 

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Solution{
	public static void main(String[] args)throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		
		int tc = pint(br.readLine());
		for (int testcase = 1; testcase <= tc; testcase++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			n = pint(st.nextToken());
			m = pint(st.nextToken());
			c = pint(st.nextToken());
			map = new int[n][n];
			for (int i = 0; i < n; i++) {
				st=new StringTokenizer(br.readLine());
				for (int j = 0; j < n; j++) {
					map[i][j]=pint(st.nextToken());
				}
			}
			collect = new ArrayList<>();
			for (int i = 0; i < n; i++) {
				for (int j = 0; j < n-m+1; j++) {
					int temp =calMax(i,j,0,0,0); 
					collect.add(new int[] {i, j, temp});
				}
			}
			
			Collections.sort(collect, new Comparator<int[]>() {
				@Override
				public int compare(int[] o1, int[] o2) {
					return o2[2]-o1[2];
				}
			});
			
			int max=0, len = Math.min(m*2-1, n-m+1);
			for (int i = 0; i < len; i++) {
				int[] fst = collect.get(i);
				for (int j = i+1; j < collect.size(); j++) {
					int[] snd = collect.get(j);
					if(fst[0]==snd[0] && Math.abs(fst[1]-snd[1])<m)continue;
					
					if(max<fst[2]+snd[2]) {
						max=fst[2]+snd[2]; break;
					}
				}
			}
			sb.append("#").append(testcase).append(" ").append(max).append("\n");
		}System.out.println(sb);
	}
    
	static int n,m,c;
	static int[][]map;
	static ArrayList<int[]>collect;
    
	static int calMax(int i,int j, int cost, int wid, int cnt) {
		if(wid>c)return 0;
		if(cnt==m) {
			return cost;
		}
		int temp=0;
		temp = calMax(i,j+1, cost+map[i][j]*map[i][j], wid + map[i][j], cnt+1);
		temp = Math.max(temp, calMax(i,j+1, cost, wid, cnt+1));
		return temp;
	}
	
	static int pint(String s) {
		return Integer.parseInt(s);
	}
}

결과 화면