18185.라면 사기(small) - 백준온라인
백준 알고리즘 문제 풀이
해당 문제는 탐욕(greedy) 문제로 현재 수행 하는것이 최선임을 정의하여 푸는 문제입니다.
그리디도 중요하지만 예외 처리가 중요한 부분이다.
링크 : 
18185.라면 사기(small)
라면매니아 교준이네 집 주변에는 N개의 라면 공장이 있다. 각 공장은 1번부터 N번까지 차례대로 번호가 부여되어 있다. 교준이는 i번 공장에서 정확하게 Ai개의 라면을 구매하고자 한다(1 ≤ i ≤ N).
교준이는 아래의 세 가지 방법으로 라면을 구매할 수 있다.
i번 공장에서 라면을 하나 구매한다(1 ≤ i ≤ N). 이 경우 비용은 3원이 든다. i번 공장과 (i+1)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N-1). 이 경우 비용은 5원이 든다. i번 공장과 (i+1)번 공장, (i+2)번 공장에서 각각 라면을 하나씩 구매한다(1 ≤ i ≤ N-2). 이 경우 비용은 7원이 든다. 최소의 비용으로 라면을 구매하고자 할 때, 교준이가 필요한 금액을 출력하는 프로그램을 작성하시오.
입력(Input)
첫째 줄에 센서의 개수 N(1 ≤ N ≤ 10,000), 둘째 줄에 집중국의 개수 K(1 ≤ K ≤ 1000)가 주어진다. 셋째 줄에는 N개의 센서의 좌표가 한 개의 정수로 N개 주어진다. 각 좌표 사이에는 빈 칸이 하나 있으며, 좌표의 절댓값은 1,000,000 이하이다.
출력(Output)
첫째 줄에 문제에서 설명한 최대 K개의 집중국의 수신 가능 영역의 길이의 합의 최솟값을 출력한다.
1. 문제 풀이
그리디 알고리즘을 이용하는 문제인데, 구매 가능한 행동이 3가지이다.
그리고, i 번째 공장 i + 1 번째 공장, i + 2 번째 공장의 라면 개수에 따라서 구매 방식을 다르게 접근해야 한다.
하나의 공장에서 3원으로 구매하는것 보다 두 개의 공장에서 5원으로 구매하는것이,
세 개의 공장에서 7원으로 구매하는것이 효율적이라는것은 누구나 알 수 있다.
그래서 처음에는 현 위치 i에서 i + 1 번째와 i + 2 번째 공장과의 살 수 있는 최대한으로 묶어서 구매하는 방식으로 문제를 풀어 봤다.
- 3개씩 묶어서 구매
1 2 3
최소값인 1개씩 구매하여
0 1 2
을 만들면, 현 위치에서 구매 한 금액은 최소 값 1 * 7 = 7원 - 2개씩 묶어서 구매
4 2 0 3
최소 값인 2개씩 구매하여
2 0 0 3
0 0 0 3
2 * 5 + 2 * 3 = 16원
그러나 위의 방식대로 접근하니 더 효율적으로 구매하지 못하는 예외 경우가 있었다.
바로 i + 1 번째가 i + 2 번째보다 큰 경우인데, 아래를 살펴보면
2 3 2 1
인근 최소값인 2개씩 구매하여
0 1 0 1
0 0 0 1
0 0 0 0
(2 * 7) + (1 * 3) + (1 * 3) = 20원
위와 같이 20원이 나오지만, 아래와 같이 앞의 2개씩 묶어서 뒤의 수와 일치 시켜주면
2 3 2 1
1 2 2 1
0 2 2 1
0 1 1 1
0 0 0 0
(1 * 5) + (1 * 3) + (1 * 5) + (1 * 7) = 19원
19원으로 더 싸게 구매가 가능한 것이다.
이는 i + 1 번째 값이 i + 2 번째 값보다 클 경우인데, 이 때에는 i 번째의 값과 [i + 1] - [i + 2] 의 값의 최소값 만큼 앞의 두개를 묶어서 사면 다음 구매에 더 싸게 구매가 가능하게 된다.
따라서 아래의 두 가지 방식으로 분기하여 그리디 방식으로 최대한 이익을 내서 구매를 한다면,
- [i + 1] 공장의 라면 > [i + 2] 공장의 라면
- [i], [i + 1] - [i + 2] 중의 최소값으로 선 구매 (2묶음)
- [i], [i + 1], [i + 2] 중의 최소값으로 구매 (3묶음)
- [i], [i + 1] - [i + 2] 중의 최소값으로 선 구매 (2묶음)
- [i + 1] 공장의 라면 < [i + 2] 공장의 라면
- [i], [i + 1], [i + 2] 중의 최소값으로 선 구매 (3묶음)
[i], [i + 1] 중의 최소값으로 구매 (2묶음)
- [i] 의 남은 개수 구매
- [i], [i + 1], [i + 2] 중의 최소값으로 선 구매 (3묶음)
가장 최소의 금액으로 구매 할 수 있는 금액이 나오게 된다.
이것을 코드로 표현하겠습니다.
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Ramyeon_18185 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int factory[] = new int[N + 2];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < N; i++) {
factory[i] = Integer.parseInt(st.nextToken());
}
int answer = 0;
for(int i = 0; i < N; i++) {
if(factory[i] > 0) {
// i + 1, i + 2 번 가게의 라면 유무를 확인
// 현재 살 수 있는 가장 많은 라면을 산다.
int min = 0;
if(factory[i + 1] > factory[i + 2]) {
// i + 1의 수가 i + 2의 수보다 크면,
// 맨 앞의 두개를 묶어서 먼저 사고, 세 개를 묶어서 사는게 싸다.
// 이 때, [i] > [i+1] - [i+2] 의 값을 비교하여 최소값으로 구매
min = Math.min(factory[i], factory[i + 1] - factory[i + 2]);
answer += min * 5;
factory[i] -= min;
factory[i + 1] -= min;
min = Math.min(factory[i], Math.min(factory[i + 1], factory[i + 2]));
answer += min * 7;
factory[i] -= min;
factory[i + 1] -= min;
factory[i + 2] -= min;
} else { // 반대는 세개 묶어 사고, 두개 묶어 사는게 싸다.
min = Math.min(factory[i], Math.min(factory[i + 1], factory[i + 2]));
answer += min * 7;
factory[i] -= min;
factory[i + 1] -= min;
factory[i + 2] -= min;
min = Math.min(factory[i], factory[i + 1]);
answer += min * 5;
factory[i] -= min;
factory[i + 1] -= min;
}
answer += factory[i] * 3;
factory[i] = 0;
}
}
System.out.println(answer);
}
}
