[백준 - 15780] 멀티탭 충분하니?

 

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

15780번: 멀티탭 충분하니?

간단히 요약하면 멀티탭을 사용할 때 1개의 멀티탭에는 연달아서 끼우면 안됩니다.

 

이러한 조건에 맞춰서 과연 주어진 학생수와 주어진 멀티탭으로 모두의 멀티탭 사용을 만족시킬 수 있을까요?

---

문제에 규칙이 뚜렷하게 보이는 문제입니다.

 

멀티탭이 남는 지 안남는 지를 확인하는 게 아니라 모두가 멀티탭을 쓸 수 있는가?가 핵심입니다.

 

그냥 연달아 끼우지만 않으면 되기에 1칸씩만 띄우고 멀티탭을 채우면 됩니다.

 

이렇게 하면 조건을 만족하면서 가장 많이 채울 수 있습니다.

---

우리가 해결해야하는 것은 2가지입니다.

< 생각 >

1. 주어지는 멀티탭 한개에 최대로 꽂을 수 있는 콘센트는 몇개인가?

2. 콘센트는 어떻게 구현할 것인가?

입력을 보면 멀티탭의 구 개수가 모두 같다는 보장을 할 수 없습니다.

 

구 갯수가 입력들어올때마다 처리를 해줘야합니다.

 

1. 전체 학생 수를 멀티탭에 꽂는 최대 수를 계산할 때마다 처리를 해준다고 생각했습니다.

 

멀티탭은 최대로 꽂기 위해서는 1개의 코드가 2칸을 차지한다고 생각하면 됩니다. 즉 2로 나눠주면 됩니다.

 

2. 하지만 순수하게 2로만 나눠주면 문제가 발생합니다. 바로 홀수의 경우입니다.

 

홀수의 구멍이 있는 멀티탭은 마지막에 1개가 더 꽂을 수 있습니다.

 

이 경우를 위해 홀수는 +1을 해줘야 합니다.

 

3. 사실 저는 이 문제를 맨 처음에 스택을 이용해서 풀었습니다. 하지만 이 글을 쓰기 위해서 문제를 본 결과 스택이 필요가 없었네요....;;

---

 

#include <iostream>
using namespace std;

int check(int num) // 멀티탭에 규칙으로 꽂을 수 있는 최대 콘센트 수
{
    int result{0};
    if (num % 2 == 0)
    {
        result = num / 2;
    } else if (num % 2 != 0)
    {
        result = num / 2 + 1;
    }
    return result;
}

int main()
{
    int multi, people, hole;
    
    cin >> people >> multi;
    
    int pass = people;
    
    for (int i = 0; i < multi; i++) // 멀티탭	 구 갯수 입력
    {
        cin >> hole;
        
        pass -= check(hole);
    }
    
    
    
    if (pass <= 0)
    {
        cout << "YES\n";
    } else if (pass > 0)
        cout << "NO\n";
    
    return 0;
}

 

깃허브 - https://github.com/cow-coding/algorithm/blob/master/BOJ/15780.cpp