<Algorithm> 152. 벌꿀채취(SWExpert)
by BFine반응형
벌꿀채취(SWExpert)
사용 알고리즘 : 완전탐색
- 이 문제는 댓글을 보고 겹치는 구간에 대한 조건이 있었는데 이 조건을 안해야 통과되는 것을 알고 풀었다.
문제에 대한 접근&생각
- 일꾼은 두명으로 고정됨 -> 완전탐색!
- 정해진 용량이상 담을 수 없음 -> 종료조건
- 일꾼은 두명이지만 가져오는 꿀의 양은 같음 -> 두개의 라인만 선택하면됨
- 두개의 최대값 -> 정렬!
내 코드
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
|
import java.util.Arrays;
import java.util.Scanner;
public class Solution {
static int n,m,c;
static int[][] honey;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
for(int t = 1; t <= T; t++) {
/******************************
* 재귀를 이용해 각라인의 최대치를 구하고
* 정렬을 통해 가장 이득이 높은 두라인의
* 합을 구한다.
*******************************/
n = sc.nextInt();
m = sc.nextInt();
c = sc.nextInt();
honey = new int[n][n];
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
honey[i][j] = sc.nextInt();
}
}
res = new int[n];
selectLine();
Arrays.sort(res);
System.out.println("#"+t+" "+(res[n-1]+res[n-2]));
}
}
static boolean[] visited;
static int max;
public static void scv(int start, int benefit,int size,int deep,int[] line) {
if(size > c) return;
max = Math.max(benefit, max);
if(deep == m) return;
for(int i = start; i < start+m; i++) {
if(!visited[i]) {
visited[i] = true;
int h = line[i];
scv(start, benefit+(h*h), size+h, deep+1, line);
visited[i] = false;
}
}
}
static int[] res;
private static void selectLine() {
for(int i = 0; i < n; i++) {
for(int u = 0; u <= n-m;u++) {
max = 0;
visited = new boolean[n];
scv(u, 0, 0, 0, honey[i].clone());
res[i] = Math.max(res[i],max);
}
}
}
}
|
|
|
|
cs |
참고 & 출처
반응형
'공부(2018~2019) - 스킨변경전 > Algorithm' 카테고리의 다른 글
| <Algorithm> 154. 디저트카페(SWExpert) (0) | 2019.04.03 |
|---|---|
| <Algorithm> 153. 홈 방범 서비스(SWExpert) (0) | 2019.04.03 |
| <Algorithm> 151. 수영장(SWExpert) (0) | 2019.04.02 |
| <Algorithm> 150. 줄기세포배양(SWExpert) (0) | 2019.04.02 |
| <Algorithm> 149. 숫자만들기(SWExpert) (0) | 2019.04.01 |
블로그의 정보
57개월 BackEnd
BFine