[SWEA] 2115 벌꿀채취

1. 문제

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu

SW Expert Academy

2. 접근방법

구현 자체는 그렇게 어렵지 않다

가로로 M크기 만큼 선택할 수 있는 모든 경우에 대해서

제곱 시키고 합했을 때 가장 큰 값이 될 수 있는 2가지 경우를 고르면 되는 문제다.

 

근데 고민해 볼 부분이

 

제곱 시키고 합할때 C라는 제한안에서 골라야 하는데

이 때 가장 큰값 부터 고른다 라고 생각하게 되면

 

위 그림에서 5 , 5 , 7 , C= 10 일때 7 * 7 = 49, 5*5 + 5*5 = 50;

이런 특이케이스가 존재한다.

 

이것과 비슷한 문제가 있는데

0/1 Knapsack 즉 dp문제이다. dp로 풀이하면 참 이쁘게 해결되게 생겼다.

 

그래서 나도 dp로 풀이했는데 M의 최대 크기가 겨우 5밖에 안되다보니

그냥 모든 부분집합을 구하는 2의 M제곱이 32밖에 안돼서

최악이 C * M = 150회인 dp에 비해 더 빠르다 .. 허 참;;

 

 

두번째로 고민해볼 문제는

겹치는 것을 어떻게 해결할까인데

 

1
4 2 18
8 9 9 8
1 1 1 1
1 1 1 1
1 1 1 1

 

이 테케를 보면

가장 큰 값인 9와 9 를 고르면

그 양옆인 8, 9 와 9 , 8을 고르지 못하는데

그러면 실제 정답으로는 8 ,9 와 9,8을 골라야 한다.

 

나는 이 부분은 그냥 완탐으로 해결하되 정렬해서 max보다 작아지는 경우엔 더 이상 비교안하도록 했다.

3. 자바 코드

package D3;

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

public class P2115벌꿀채취 {

	static class range implements Comparable<range> {
		int x;
		int y;
		int sum;

		public range(int x, int y, int sum) {
			this.x = x;
			this.y = y;
			this.sum = sum;
		}

		@Override
		public int compareTo(range o) {
			// TODO Auto-generated method stub
			return o.sum - this.sum;
		}

	}

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; tc++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			int M = Integer.parseInt(st.nextToken());
			int C = Integer.parseInt(st.nextToken());
			int 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] = Integer.parseInt(st.nextToken());
				}
			}
			List<range> a = new ArrayList<range>();
			for (int i = 0; i < N; i++) {
				for (int j = 0; j <= N - M; j++) {
					a.add(new range(i, j, calc(map, i, j, C, M)));
				}
			}
			Collections.sort(a);
			range first = null;
			range second = null;
			int max = 0;
			for (int i = 0; i < a.size(); i++) {
				first = a.get(i);
				for (int j = i + 1; j < a.size(); j++) {
					second = a.get(j);
					if (second.x == first.x && first.y < second.y && second.y < first.y + M)
						continue;
					if (second.x == first.x && second.y < first.y && first.y < second.y + M)
						continue;
					if(first.sum + second.sum < max)
						break;
					max = Math.max(max, first.sum+second.sum);
				}
			}
			System.out.println("#" + tc + " " + max);
		}
	}

	static int calc(int map[][], int x, int y, int C, int M) {
		int nums[] = new int[M];
		int dp[][] = new int[M + 1][C + 1];
		for (int i = y; i < y + M; i++) {
			nums[i - y] = map[x][i];
		}
		for (int i = 1; i <= M; i++) {
			int num = nums[i - 1];
			for (int j = 1; j <= C; j++) {
				dp[i][j] = dp[i - 1][j];
				if (j >= num) {
					dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - num] + num * num);
				}
			}
		}
		return dp[M][C];
	}

}

 

4. 마치며

N의 크기가 작아지면 dp가 완탐보다 효율이 안나올수도 있구나를 깨닫게 해준 문제였다..