[SWEA] 벌꿀채취

About this offer

문제 https://swexpertacademy.com/main/solvingProblem/solvingProblem.do 전체코드 import java.io.*; import java.util.*; class Solution { private static int calMax(int[] honeys, int c) { int max=0; for (int i = 0; i < (1<< honeys.length); i++) { int sum=0; int profit=0; for (int j = 0; j < honeys.length; j++) { if ((i & 1<< j) !=0 ) { sum += honeys[j]; profit+= honeys[j]*honeys[j]; } } if (sum <= c) max= Math.max(max, profit); } return max; } public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); int t = Integer.parseInt(br.readLine()); StringTokenizer st; StringBuilder sb= new StringBuilder(); for (int test_case = 1; test_case <= t; test_case++) { st = new StringTokenizer(br.readLine()); int answer = Integer.MIN_VALUE; int N = Integer.parseInt(st.nextToken()); int M = Integer.parseInt(st.nextToken()); int C = Integer.parseInt(st.nextToken()); int[][] honeys = new int[N][N]; // 시작점에서 M 크기만큼 int[][] dp = new int[N][N-M+1]; for (int i = 0; i < N; i++) { st = new StringTokenizer(br.readLine()); for (int j = 0; j < N; j++) honeys[i][j] = Integer.parseInt(st.nextToken()); } // 합 미리 넣어놓기 for (int i = 0; i < N; i++) { for (int j = 0; j <= N - M; j++) { int tmp= 0; for (int k = 0; k < M; k++) { tmp += honeys[i][j+k]; } if (tmp <= C) { for (int k = 0; k < M; k++) dp[i][j] += (honeys[i][j+k])*(honeys[i][j+k]); } else { int[] arr= new int[M]; for (int k = 0; k < M; k++) arr[k]= honeys[i][j+k]; // c를 넘지 않는 최대 수집 수익 dp[i][j]= calMax(arr,C); } } } for (int i = 0; i < N ; i++) { for (int j = 0; j <= N-M ; j++) { int first= dp[i][j]; // 같은 행일 때 int second; for (int l = j+M; l <= N-M; l++) { second= dp[i][l]; answer= Math.max(answer, first+ second); } // 다른 행일 때 for (int k = i+1; k < N; k++) { for (int l = 0; l <= N-M; l++) { second= dp[k][l]; answer= Math.max(answer, first+ second); } } } } sb.append("#").append(test_case).append(" ").append(answer).append("\n"); } bw.write(sb.toString()); bw.flush(); bw.close(); br.close(); } } 풀이 1. 모든 점에 대하여 크기가 M인 벌꿀통에 담기 일꾼은 가로로 연속된 M개의 벌통을 선택해야 한다. 그래서 각 행 i에서 시작점 j는 0부터 N-M까지만 가능하다. 두 일꾼의 조합을 따질 때 같은 구간의 수익을 계속 다시 계산하면 비효율적이기 때문에 시작점 (i, j)에서 M칸을 선택했을 때 얻을 수 있는 최대 수익을 먼저 전부 계산해 dp[i][j]에 저장했다. // dp[i][j] : (i, j)에서 시작하는 M칸 벌통에서 얻을 수 있는 최대 수익 int[][] dp = new int[N][N-M+1]; 점화식이 있는 DP라기보다는 메모이제이션을 사용하며 한 번 계산한 값을 저장해두고 재사용한다. 이렇게 해두면 매번 크기 M만큼의 벌꿀 합을 계산하지 않고 배열 값을 꺼내 더하기만 하면 된다. 2. C를 고려해 채취 가능한 벌꿀양과 이익 계산하기 선택한 M칸의 꿀을 모두 채취할 수 있는지는 꿀의 합이 C 이하인지에 따라 달라진다. 1. M칸의 합이 C 이하인 경우 전부 채취할 수 있으므로 각 칸 꿀 양의 제곱을 모두 더하면 된다. if (tmp <= C) { for (int k = 0; k < M; k++) dp[i][j] += honeys[i][j+k] * honeys[i][j+k]; } 2. M칸의 합이 C를 초과하는 경우 일부 벌통만 골라야 하는데 큰 값부터 고르는 그리디 방식은 성립하지 않는다. 예를 들어 C=10 꿀이 [6, 5, 5]라면 6을 먼저 고르면 수익이 36이지만 5와 5를 고르면 25+25=50으로 더 크다. 그래서 부분집합을 전부 탐색해야한다. M은 최대 5이므로 부분집합은 최대 25 = 32개로 충분히 작기에 비트마스크로 각 부분집합을 표현하고 합이 C 이하인 경우 중 제곱합의 최댓값을 구했다. private static int calMax(int[] honeys, int c) { int max = 0; for (int i = 0; i < (1 << honeys.length); i++) { // 모든 부분집합 int sum = 0, profit = 0; for (int j = 0; j < honeys.length; j++) { if ((i & (1 << j)) != 0) { // j번째 벌통 선택 sum += honeys[j]; profit += honeys[j] * honeys[j]; } } if (sum <= c) max = Math.max(max, profit); // C 이하일 때만 갱신 } return max; } 사실 calMax는 전체를 고르는 경우(비트가 모두 1)도 포함하므로 경우 1까지 처리할 수 있다. 합이 C 이하일 때 바로 계산하는 분기는 불필요한 부분집합 탐색을 줄이기 위한 최적화입니다. 3. 두 채집자의 벌꿀통 선택해서 최대 구하기 두 일꾼이 고른 벌통은 겹치면 안 됩니다. 첫 번째 일꾼의 시작점을 (i, j)로 고정했을 때 두 번째 일꾼이 선택할 수 있는 위치는 두 가지입니다. 같은 행일 때에는 첫 번째 일꾼이 j ~ j+M-1을 쓰므로, 두 번째 일꾼은 j+M부터 시작해야 겹치지 않습니다. for (int l = j + M; l <= N - M; l++) { answer = Math.max(answer, first + dp[i][l]); } 다른 행일 때는 행이 다르면 절대 겹치지 않으므로 아래 행의 모든 시작점이 가능하다. for (int k = i + 1; k < N; k++) { for (int l = 0; l <= N - M; l++) { answer = Math.max(answer, first + dp[k][l]); } } 두 경우 모두 두 번째 일꾼을 첫 번째 일꾼보다 뒤쪽(같은 행의 오른쪽, 또는 아래 행) 에서만 찾는데 이렇게 하면 (A, B)와 (B, A) 같은 중복 조합을 자연스럽게 제거할 수 있다. 시간 복잡도 N ≤ 10, M ≤ 5 기준으로 메모리제이션은 칸 수 N2 × 부분집합 2M × M이라 약 100 × 32 × 5 수준이고 조합 탐색은 시작점 쌍이므로 최대 (N2)2 ≈ 104 메모리제이션 덕분에 조합 탐색 단계에서는 덧셈과 비교만 하므로 매우 빠르게 동작한다.