[SWEA] #2115 - 벌꿀채취
2022. 4. 15. 22:41
728x90
반응형
💡 출처
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu
SW Expert Academy
SW 프로그래밍 역량 강화에 도움이 되는 다양한 학습 컨텐츠를 확인하세요!
swexpertacademy.com
💡 문제
[설명]
N*N 개의 벌통이 정사각형 모양으로 배치되어 있다.
각 칸의 숫자는 각각의 벌통에 있는 꿀의 양을 나타내며, 꿀의 양은 서로 다를 수 있다.
아래 [Fig. 1]은 N=4인 16개의 벌통을 나타낸다.
각 벌통에 있는 꿀의 양이 주어졌을 때, 다음과 같은 과정으로 벌꿀을 채취하여 최대한 많은 수익을 얻으려고 한다.
① 두 명의 일꾼이 있다. 꿀을 채취할 수 있는 벌통의 수 M이 주어질 때,
각각의 일꾼은 가로로 연속되도록 M개의 벌통을 선택하고, 선택한 벌통에서 꿀을 채취할 수 있다.
단, 두 명의 일꾼이 선택한 벌통은 서로 겹치면 안 된다.
아래 [Fig. 2]는 M=2일 때, 두 일꾼이 각각 벌통을 선택하는 다양한 예를 보여준다.
② 두 명의 일꾼은 선택한 벌통에서 꿀을 채취하여 용기에 담아야 한다.
단, 서로 다른 벌통에서 채취한 꿀이 섞이게 되면 상품가치가 떨이지게 되므로, 하나의 벌통에서 채취한 꿀은 하나의 용기에 담아야 한다.
하나의 벌통에서 꿀을 채취할 때, 일부분만 채취할 수 없고 벌통에 있는 모든 꿀을 한번에 채취해야 한다.
두 일꾼이 채취할 수 있는 꿀의 최대 양은 C 이다.
예를 들어, 아래 [Fig. 3]에서 C=10이고, 두 명의 일꾼이 선택한 벌통이 그림과 같을 때,
첫 번째 일꾼은 꿀의 양이 6과 1인 두 개의 벌통에서 모두 꿀을 채취할 수 있다.
하지만 두 번째 일꾼은 꿀의 양이 8과 5인 두 개의 벌통에서 모두 꿀을 채취할 경우,
채취한 꿀의 양이 13이 되어 C=10을 초과하기 때문에 두 개의 벌통에서 모두 꿀을 채취할 수 없다.
따라서 두 번째 일꾼은 꿀의 양이 8과 5인 벌통 중 하나를 선택하여 꿀을 채취해야 한다.
[Fig. 3]은 그 중 한 예를 보여주고 있다.
③ 채취한 꿀은 시장에서 팔리게 된다. 이때 하나의 용기에 있는 꿀의 양이 많을수록 상품가치가 높아, 각 용기에 있는 꿀의 양의 제곱만큼의 수익이 생긴다.
예를 들어 위 [Fig. 3]과 같이 꿀을 채취할 경우, 꿀의 양이 6, 1, 8인 세 개의 용기가 얻어지며 이때 수익의 합은, (6*6) + (1*1) + (8*8) = 36 + 1 + 64 = 101 이 된다.
벌통들의 크기 N과 벌통에 있는 꿀의 양에 대한 정보, 선택할 수 있는 벌통의 개수 M, 꿀을 채취할 수 있는 최대 양 C가 주어진다.
이때 두 일꾼이 꿀을 채취하여 얻을 수 있는 수익의 합이 최대가 되는 경우를 찾고, 그 때의 최대 수익을 출력하는 프로그램을 작성하라.
[예시 1]
벌통들의 크기 N=4, 선택할 수 있는 벌통의 개수 M=2, 채취할 수 있는 꿀의 최대 양 C=13 이고,
아래 [Fig. 4]와 같이 벌통에 있는 꿀의 양의 정보가 주어진 경우를 보자.
최대 수익을 얻을 수 있는 경우 중 하나로 [Fig. 4]와 같이 벌통을 선택하여 선택하여 꿀을 채취하게 되면, 총 수익이 174가 되어 최대가 된다.
따라서 이 경우 정답은 174이다.
[예시 2]
벌통의 크기 N=3, 선택할 수 있는 벌통의 개수 M=3, 채취할 수 있는 꿀의 최대 양 C=10 이고,
아래 [Fig. 5]와 같이 벌통에 있는 꿀의 양의 정보가 주어진 경우를 보자.
최대 수익을 얻을 수 있는 경우 중 하나로 [Fig. 5]와 같이 벌통을 선택하여 꿀을 채취하게 되면, 총 수익이 131이 되어 최대가 된다.
따라서 이 경우 정답은 131이다.
💡 아이디어
우선 한 행에서만 벌꿀을 채취할 수 있기 때문에 한 행을 기준으로 생각한다.
배열을 살펴보면서 어떤 위치에 도착했을 때 현재 위치에서부터 M만큼의 벌통을 채취할 수 있다면
배열에 저장한 뒤 이 배열에서 최대의 수익을 얻을 수 있는 조합을 구한다.
그 후 ArrayList에 배열의 위치와 최대의 수익을 저장한다.
이 과정을 모든 배열의 위치에서 반복한다.
그러면 ArrayList에는 모든 위치와 각 위치에 대한 최대 수익이 저장될 것이다.
이 ArrayList를 내림차순으로 정렬한 뒤에 첫 번째 값은 결과값에 더하고,
두 번째 값부터는 첫 번째 값과 위치가 겹치지 않는지 확인하여 만약에 위치가 겹치지 않으면 결괏값에 더해준다.
그러면 최대의 수익을 구할 수 있다.
💡 소스코드
package SWEA;
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
class set implements Comparable<set> {
int row;
int col;
int max;
set(int row, int col, int max) {
this.row = row;
this.col = col;
this.max = max;
}
@Override
public int compareTo(set o) {
if (this.max < o.max)
return -1;
else if (this.max == o.max)
return 0;
else
return 1;
}
}
public class SWEA_P2115_벌꿀채취 {
static int[][] map; // 벌통을 저장하는 2차원 배열
static int N; // 벌통의 크기
static int M; // 채취할 수 있는 벌통의 수
static int C; // 채취할 수 있는 꿀의 최대양
static int max;// 각 행에서 채취할 수 있는 벌통의 수의 최대 가치
static ArrayList<set> list;// 최대 가치를 가지는 (행, 열)의 값과 가치를 저장
public static void main(String[] args) throws Exception {
System.setIn(new FileInputStream("./SWEA_INPUT/SWEA_P2115_input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer sz;
int T = Integer.parseInt(br.readLine());
for (int TC = 1; TC <= T; TC++) {
// 초기화
sz = new StringTokenizer(br.readLine());
N = Integer.parseInt(sz.nextToken());
M = Integer.parseInt(sz.nextToken());
C = Integer.parseInt(sz.nextToken());
map = new int[N][N];
list = new ArrayList<set>();
// 입력
for (int i = 0; i < N; i++) {
sz = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(sz.nextToken());
}
}
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (j + M - 1 < N) {
int[] array = new int[M]; // 채취가능한 벌통을 임시로 저장
int idx = 0; // array의 index
boolean[] visited = new boolean[M]; // 조합을 위해 방문한 곳을 표시
// 현재 위치를 기준으로 채취가능한 벌통을 저장
for (int k = 0; k < M; k++)
array[idx++] = map[i][j + k];
// max값 초기화
max = 0;
// 1자리에서 M자리의 조합을 모두 탐색하며 그 중에서 가장 가치가 높은 값을 찾음
for (int l = 1; l <= M; l++)
combination(array, visited, 0, M, l);
// 현재 위치와 max값을 ArrayList에 저장
list.add(new set(i, j, max));
}
}
}
// ArrayList를 max기준으로 정렬한 후 뒤집어서 내림차순으로 만듦
Collections.sort(list);
Collections.reverse(list);
int sum = 0; // 최종값
int idx = 0; // list에서 두 번째로 높은 가치를 찾기위한 인덱스
set first = list.get(idx++);// 가장 가치가 높은 것
sum += first.max;
while (true) {
set second = list.get(idx++);// 두 번째로 가치가 높은 것
// 만약 행이 다르다면 first와 겹칠 일이 없기 때문에 sum에 max값을 더하고 break
if (first.row != second.row) {
sum += second.max;
break;
}
// 행은 같지만 두 개의 열의 차이가 최대 벌통의 개수 이상이면 겹치지 않기 때문에 sum에 max값을 더하고 break
else if (first.row == second.row && Math.abs(first.col - second.col) >= M) {
sum += second.max;
break;
}
}
// 출력
System.out.println("#" + TC + " " + sum);
}
br.close();
}
/*
* 모든 조합을 구하는 method array : 조합을 구할 배열 visited : 방문한 곳을 check start : 시작점 n :
* 배열의 크기 r : 찾고자 하는 조합의 크기 Ex) n이 4이고 r이 1이면 4개중에서 1개짜리를 모두 구하는 것
*/
static void combination(int[] array, boolean[] visited, int start, int n, int r) {
if (r == 0) {// 모두 찾았을 때
int sum = 0;
// 현재 조합의 합을 구함
for (int i = 0; i < n; i++) {
if (visited[i]) {
sum += array[i];
}
}
// 합이 꿀의 최대양 보다 크면 종료
if (sum > C)
return;
// 합이 꿀의 최대양 보다 작으면 max을 값을 구하고 갱신
else {
sum = 0;
for (int i = 0; i < n; i++) {
if (visited[i]) {
sum += squared(array[i]);
}
}
if (sum > max)
max = sum;
return;
}
}
// 재귀호출
for (int i = start; i < n; i++) {
visited[i] = true;
combination(array, visited, i + 1, n, r - 1);
visited[i] = false;
}
}
// 제곱을 구하는 method
public static int squared(int n) {
return (int) Math.pow(n, 2);
}
}💡 결과
한 행에서 M만큼의 칸이 총 몇 개 나올 수 있는지에 대한 것도 생각해야 하고,
그 칸 안에서 어떻게 조합해야 최대의 수익을 얻을 수 있는지도 생각해야 해서
조금은 복잡하게 느껴지는 완전 탐색 문제였다.
728x90
반응형
'Algorithm > SW Expert Academy' 카테고리의 다른 글
| [SWEA] #4012 - 요리사 (0) | 2022.04.21 |
|---|---|
| [SWEA] #4008 - 숫자 만들기 (0) | 2022.04.18 |
| [SWEA] #1952 - 수영장 (0) | 2022.04.15 |
| [SWEA] #1949 - 등산로 조성 (0) | 2022.04.14 |
| [SWEA] #1861 - 정사각형 방 (0) | 2022.04.13 |
