(C++) - 백준(BOJ) 15051 : Máquina de café

https://www.acmicpc.net/problem/15051

15051번: Máquina de café

모든 경우의 수를 다 확인하는 brute force 문제였습니다.

 

📕 풀이방법

📔 입력 및 초기화

 1. 층마다 사람 수를 입력하기 위한 일차원 배열 peoplePerFloor를 선언합니다. 답을 출력할 변수 ans를 선언합니다.

 2. 층마다 사람 수를 입력해줍니다.

📔 풀이과정

커피머신을 0층부터 2층까지 차례대로 설치해보면서 모든 사람이 이동하는 시간의 최솟값을 찾습니다. 

 1. 커피머신을 x층에 놓기로 결정했다면 사람들이 왕복하는데 걸리는 시간은 (x - 사람들이 있는 층) * 사람수 * 2가 됩니다.  

 2. 이를 0 ~ 2층 모두에 대해 수행한 누적합을 ans와 비교해 최솟값을 ans에 저장합니다.

 

*단순히 가장 사람이 많은 층에 커피머신을 둘 경우 괜찮지 않을까란 생각을 할 수 있습니다. 하지만 여기에는 반례가 존재합니다.

input이

99
98
100
인 경우 각 층에 커피머신을 둘 경우 계산을 해봤을 때
0층에 두기 : 98*2 + 100*4 = 596
1층에 두기 : 99*2 + 100*2 = 398
2층에 두기 : 98*2 + 99*4 = 592
가 되기 때문에 가장 사람이 많은 2층에 커피머신을 두게되면 손해입니다. 따라서 모든 경우에 대해 수행해야 합니다.

📔 정답출력

ans를 출력합니다.

---

📕 Code

#include <bits/stdc++.h>
using namespace std;
int peoplePerFloor[3], ans = 0x3f3f3f3f;
int main(){
    for(int i = 0; i < 3; i++) cin >> peoplePerFloor[i];
    for(int floor = 0; floor < 3; floor++){
        int sum = 0;
        for(int i = 0; i < 3; i++) 
            sum += abs(i - floor) * peoplePerFloor[i] * 2;
        ans = min(ans, sum);
    }
    cout << ans;
}

---

📕 Test Case

앞서 설명했던 반례입니다.

input

99
98
100

답 : 398