오늘 풀어볼 문제는 ⭐꿀 따기 입니다
1. 문제 요약
위와 같은 N개의 장소가 있고, 각 장소마다 벌이 딸 수 있는 꿀이 존재합니다.
1) 벌 두 마리와, 벌집이 존재합니다. (위치는 주어지지 않습니다.)
2) 벌 두 마리는 해당 벌집을 향해 일직선으로만 날아가며 꿀을 땁니다. (벌이 되돌아가지 않습니다.)
3) 벌의 출발 장소에 해당하는 곳은 꿀을 딸 수 없습니다.
4) 동일한 장소에서 두 벌 모두 채집이 가능합니다.
5) 벌이 딸 수 있는 최대 꿀을 구하세요.
예시를 들어보자.
1.1 예시 케이스(1)
연한 회색 = 벌이 있는 곳 / 진한 회색 = 벌집이 있는 곳.
각 벌은 모두 2번 인덱스-6번 인덱스의 꿀을 딸 수 있다. -> 4+1+4+9+9
해당 케이스에서 딸 수 있는 꿀 = 54
1.2 예시 케이스(2)
0번 인덱스에 위치한 벌은 9+4+4+4+9+9 만큼의 꿀을 딸 수 있다. (35)
3번 인덱스에 위치한 벌은 4+9+9 만큼의 꿀을 딸 수 있다. (22)
해당 케이스에서 딸 수 있는 꿀 = 57
그래서 해당 케이스에서 최대로 딸 수 있는 꿀은 57이다. 더 이상 딸 수 있는 경우는 없다.
1.3 또 다른 문제 케이스
이렇게 꿀통이 중앙에 오는 경우도 있다!
2. 문제 접근
보자마자 누적합일 것이라 생각했다. 한 가지 이슈는 벌 2마리와 벌꿀의 위치가 입력값으로 주어지지 않기에, 해당 기준점을 잡는 것이 어려웠다.
그래서 벌과 꿀통의 기준점은 다음과 같이 생각했다.
경우의 수
1) 벌통이 왼/오 맨 끝에 있는 경우
-> 1번 벌 : 벌통 반대편
-> 2번 벌 : ?2) 벌통이 중간에 있는 경우 -> 벌통은 가장 최댓값에 위치하는 게 좋음!
-> 1번 벌과 2번 벌 모두 맨끝에 위치
1번 경우에서, 처음에는 2번 벌이 벌통과 1번 벌 사이의 최솟값에 위치하면 될 것이라 생각했다.
(단순하게 벌의 시작점의 꿀은 딸 수 없으니, 제일 최솟값에 2번 벌이 위치하며 되겠네 라고 판단)
그러나 이렇게 판단하면 무조건 반례가 생긴다.
그래서 깨달았다.
아! 이건 브루트포스다.
최종적인 해결 접근법은 다음과 같다.
- 누적합 배열 및 원본 꿀 배열 2개 생성
- 만약 벌통이 왼/오에 있다고 가정, 브루트 포스를 통해 두 번째 벌의 위치를 구함
- 두 번째 벌의 위치? 변경된 2번 벌의 위치에 따른 채집 꿀이 최대인 경우
- 만약 벌통이 중간에 위치한다는 가정
- 벌들의 시작위치(첫 인덱스, 끝 인덱스)를 제외한 가장 최대 꿀을 가진 장소 = 벌통 위치
- why? 해당 최대 꿀 장소는 2마리의 벌 모두 가는 게 좋기 때문
3. 핵심 코드
각 케이스별 누적합을 사용하는 방법이 다르다.
3.1 벌통이 가장 왼쪽에 위치하는 경우?
static int honeyHouseIsLeft() {
int b1Honey = honey[N-2];
int answer=0;
for (int i=1; i<N-1; i++){
int nowB1Honey = b1Honey-original[i];
int nowB2Honey = honey[i-1];
answer = Math.max(answer, nowB1Honey+nowB2Honey);
}
return answer;
}3.2 벌통이 가장 오른쪽에 위치하는 경우?
45 - 9 라는 건, 누적합 배열[벌통 위치 인덱스] - 누적합 배열 [현재 벌 위치 인덱스] 라는 걸 의미한다!!
해당 식은 벌 2의 꿀을 구할때도 동일하게 적용되며, 마찬가지로 브루트 포스를 돌며 1번 벌 + 2번 벌을 합쳤을 때 가장 큰 꿀을 구하면 된다.
static int honeyHouseIsRight() {
int b1Honey = honey[N-1]-original[0];
int answer = 0;
for (int i=1; i<N-1; i++){
int nowB1Honey = b1Honey-original[i];
int nowB2Honey = honey[N-1]-honey[i];
answer = Math.max(answer, nowB1Honey+nowB2Honey);
}
return answer;
}벌통이 중간에 있는 경우?
이건 위에서도 설명했듯, 벌들의 시작위치가 아닌 곳에서 가장 많은 벌을 가진 장소가 벌집 위치이다. 해당 벌집을 기준으로 왼, 오에 대한 누적합을 더하면 끝이다.
static int honeyHouseIsMiddle(int honeyDex){
int left = honey[honeyDex] - honey[0];
int right = honey[N-2] - honey[honeyDex-1];
return left+right;
}4. 전체 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static int [] honey;
static int [] original;
static int maxDex=0, N;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
N = Integer.parseInt(br.readLine());
honey=new int[N];
original=new int[N];
st = new StringTokenizer(br.readLine());
honey[0] = Integer.parseInt(st.nextToken());
original[0] = honey[0];
int max = 0;
for(int i=1; i<N; i++) {
original[i] = Integer.parseInt(st.nextToken());
honey[i] = honey[i-1]+original[i];
if(i!=0 && i!=N-1){
max = Math.max(max, original[i]);
if(max==original[i]) maxDex=i;
}
}
int answer = 0;
//꿀통이 왼쪽에 있는 경우
answer = honeyHouseIsLeft();
//꿀통이 오른쪽에 있는 경우
answer = Math.max(honeyHouseIsRight(), answer);
//꿀통이 중앙에 있는 경우(max = 꿀통 위치)
answer = Math.max(honeyHouseIsMiddle(maxDex), answer);
System.out.println(answer);
}
static int honeyHouseIsLeft() {
int b1Honey = honey[N-2];
int answer=0;
for (int i=1; i<N-1; i++){
int nowB1Honey = b1Honey-original[i];
int nowB2Honey = honey[i-1];
answer = Math.max(answer, nowB1Honey+nowB2Honey);
}
return answer;
}
static int honeyHouseIsRight() {
int b1Honey = honey[N-1]-original[0];
int answer = 0;
for (int i=1; i<N-1; i++){
int nowB1Honey = b1Honey-original[i];
int nowB2Honey = honey[N-1]-honey[i];
answer = Math.max(answer, nowB1Honey+nowB2Honey);
}
return answer;
}
static int honeyHouseIsMiddle(int honeyDex){
int left = honey[honeyDex] - honey[0];
int right = honey[N-2] - honey[honeyDex-1];
return left+right;
}
}