https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV5V4A46AdIDFAWu
[1회차] 10월 2일날 풀었어서 코드만 첨부
더보기
코드
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
public class Solution {
static int N, M, C, ans, max;
static int map[][], honeys[];
static boolean isVisited[];
static List<Honey> list;
static class Honey{
int x, s_y, e_y, cnt, total;
public Honey(int cnt, int total){
this.cnt = cnt;
this.total = total;
}
public Honey(int x, int s_y, int e_y, int total){
this.x = x;
this.s_y = s_y;
this.e_y = e_y;
this.total = total;
}
}
public static void main(String args[]) throws Exception {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(in.readLine());
for (int test_case = 1; test_case <= T; test_case++) {
StringTokenizer st = new StringTokenizer(in.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
map = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(in.readLine());
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
ans = Integer.MIN_VALUE;
getHoneys();
sb.append("#" + test_case + " " + ans + "\n");
}
System.out.println(sb);
}
private static void getHoneys() {
list = new ArrayList<>();
for (int i = 0; i < N; i++) {
for (int j = 0; j <= N - M; j++) {
honeys = new int[M];
for (int k = 0; k < M; k++) {
honeys[k] = map[i][j+k];
}
isVisited = new boolean[M];
max = Integer.MIN_VALUE;
findMaxHoney(0);
list.add(new Honey(i, j, j + M, max));
}
}
isVisited = new boolean[list.size()];
Honey[] order = new Honey[2];
combi(0, 0, order);
}
private static void combi(int depth, int start, Honey[] order){
if(depth == 2){
if(order[0].x == order[1].x && order[0].e_y > order[1].s_y){
return;
}
if(order[0].total + order[1].total < ans) return;
ans = Math.max(ans, order[0].total + order[1].total);
return;
}
for (int i = start, size = list.size(); i < size; i++) {
if(!isVisited[i]){
isVisited[i] = true;
order[depth] = list.get(i);
combi(depth+1, i+1, order);
isVisited[i] = false;
}
}
}
private static void findMaxHoney(int depth) {
if(depth == M) {
Honey h = new Honey( 0, 0);
for (int i = 0; i < M; i++) {
if(isVisited[i]){
h.cnt += honeys[i];
h.total += honeys[i] * honeys[i];
}
if(h.cnt > C){
h.total = 0;
return;
}
}
max = Math.max(h.total, max);
return;
}
// arr에 있는 값들 중 합이 C를 넘기지 않으면서 제곱의 값의 합이 가장 큰 것을 찾아야 함 -> 부분집합?
isVisited[depth] = true;
findMaxHoney(depth + 1);
isVisited[depth] = false;
findMaxHoney(depth + 1);
}
}
아마 이 문제 푸는데 시간이 조금 오래 걸렸었던 것 같다. 뭔가 하나 조건에 안 맞았던 것 같은데...
[2회차] 10월 25일
문제 접근 방법 (사용 자료구조, 알고리즘)
1. 입력 => T(테스트 케이스 개수), N, M, C, 벌꿀장
2. M개의 벌꿀통에서 채취할 수 있는, C를 넘지 않는 최대 벌꿀양의 수익량을 계산 → 부분집합
이 때, 무조건 M개를 채취해야하는 건 아니고 M=3, C=10일 경우 [7, 2, 9] 에서는 9만 채취를 하는게 가장 벌꿀 수익량이 많다.
나는 이 조건을 자세히 안 봐서 결국 다시 돌아와서 추가했다. -> 부분집합으로 완전탐색 시전 -> 뭔가 더 간단한 방법이 있을 것 같다...
3. 채취한 경우의 수 중에서 2개 선택해서 범위에 겹치는지 판별, 겹치지 않는다면 ans를 최대값으로 갱신 → 조합
나는 벌꿀을 채취하는 사람이 특정 2명이 아니고 A명도 될 수 있다고 확장해서 생각해서 boolean 2차원 배열로 판별해주었다.
문제를 푼 시간 (문제 해석 + 문제 접근 + 코드 구현)
문제 해석 | 문제 로직 설계 | 코드 구현 |
3분 | 10분 | 40분 |
코드
더보기
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;
public class Solution {
static int N, M, C, map[][], ans, selected[], total;
static List<Honey> honeys;
static boolean[] visited;
static class Honey{
int x, start, end, amount;
public Honey(int x, int start, int end, int amount) {
this.x = x;
this.start = start;
this.end = end;
this.amount = amount;
}
}
public static void main(String[] args) throws Exception {
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
int T = Integer.parseInt(in.readLine());
for (int test_case = 1; test_case <= T; test_case++) {
// 1. 입력
StringTokenizer st = new StringTokenizer(in.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
C = Integer.parseInt(st.nextToken());
map = new int[N][N];
for (int i = 0; i < N; i++) {
st = new StringTokenizer(in.readLine());
for (int j = 0; j < N; j++) {
map[i][j] = Integer.parseInt(st.nextToken());
}
}
// 2. M 개 채취 배열생성 -> 채취량이 C를 넘으면 안 되면서 && 최댓값을 찾아 주어야 함
honeys = new ArrayList<>();
for (int i = 0; i < N; i++) {
for (int j = 0; j < N - M + 1; j++) {
// 여기서도 조합을 쓰는게 맞을까..?
int[] catchHoneys = new int[M];
for (int k = 0; k < M; k++) {
catchHoneys[k] = map[i][j + k];
}
total = 0;
visited = new boolean[M];
getHoneyMax(catchHoneys, 0);
honeys.add(new Honey(i, j, j + M - 1, total));
}
}
// 3. 채취한 경우의 수 중 2개 선택, 조합
visited = new boolean[honeys.size()];
selected = new int[2];
ans = Integer.MIN_VALUE;
combi(0, 0);
sb.append("#" + test_case + " " + ans + "\n");
}
System.out.println(sb);
}
private static void getHoneyMax(int[] catchHoneys, int depth) {
if(depth == M) {
int[] amount = new int[2];
for (int i = 0; i < M; i++) {
if(visited[i]) {
amount[0] += catchHoneys[i];
if(amount[0] > C) return;
amount[1] += Math.pow(catchHoneys[i], 2);
}
}
total = Math.max(total, amount[1]);
return;
}
visited[depth] = true;
getHoneyMax(catchHoneys, depth+1);
visited[depth] = false;
getHoneyMax(catchHoneys, depth+1);
}
private static void combi(int depth, int start) {
if(depth == 2) {
boolean[][] check = new boolean[N][N];
int amount = 0;
// 같은 위치거나 겹치면은 안됨 -> 그렇지 않으면 정답 갱신
for (int i = 0; i < 2; i++) {
Honey h = honeys.get(selected[i]);
for (int j = h.start; j <= h.end; j++) {
if(check[h.x][j]) return;
check[h.x][j] = true;
}
amount += h.amount;
}
ans = Math.max(ans, amount);
return;
}
for (int i = start; i < honeys.size(); i++) {
if(!visited[i]) {
visited[i] = true;
selected[depth] = i;
combi(depth+1, i+1);
visited[i] = false;
}
}
}
}
메모리 & 시간
메모리 ⬆, 시간 2초 ⬆
아마 판별 과정에서 boolean 배열을 사용해서 더 커진 것 같다
아마 채취 과정에서 좀 더 효율적으로 생각할 수 있는 방법이 있을 것 같다
체감 난이도
中
'JAVA > 알고리즘 서브 노트' 카테고리의 다른 글
[BJ 17406] 배열 돌리기4 (0) | 2022.10.27 |
---|---|
[SWEA 1952] 수영장 (0) | 2022.10.27 |
[백준 17472] 다리만들기2 (0) | 2022.10.09 |
[SWEA 2805] 농작물 수확하기 (0) | 2022.08.17 |
[프로그래머스: JAVA] 키패드 누르기 (0) | 2022.08.15 |