[Programmers] 입국심사 Solution (C++)

문제 원문 링크 : https://programmers.co.kr/learn/courses/30/lessons/43238

코딩테스트 연습 - 입국심사

이 문제의 핵심은 binary search보다도, overflow handling에 있는 것 같다.

 

binary search를 이용하는 것은 그리 어렵지 않다.

 

우리가 구하고자 하는 것은 결국 n명을 심사하기까지 걸리는 최소의 "시간"이다.

따라서 시간의 범위를 정해주고, 그 범위 내에서 binary search를 통해 원하는 값을 찾도록 설계해주면 된다.

---

시간의 최댓값은 무엇이 될까?

 

정답부터 말하자면, "가장 빠르게 심사하는 사람이 걸리는 시간 × 사람 수"가 된다.

예시를 통해 자세히 알아보자.

 

n=100, times={1, 100, 100, 100}와 같은 경우, 답은 100이 되는데,

이는 한 명을 심사하는데 100분이나 걸리는 사람들은 실제로 심사를 하지 않는다는 뜻이다.

그리고 이 사람을 대신하여, 가장 빠르게 심사하는 사람 혼자서 심사를 하게 된다.

 

즉, 아무리 시간이 오래 걸린다한들, 가장 빠르게 심사하는 사람 혼자서 n명을 심사하는 시간이 최댓값이라는 것이다.

---

그렇다면 반대로 최소값은 어떻게 될까?

 

어떠한 경우에서든 최소 한 명은 일을 해야 하므로, "가장 빠르게 심사하는 사람이 걸리는 시간"이 된다.

 

시간의 범위를 알아냈으니, 지금부턴 이 범위 내에서 binary search를 하며 n명을 모두 심사 가능한 시간을 찾으면 된다.

---

logic 구성은 끝났으니, 이제 앞서 말한 코드를 구현함에 있어 조심해야할 overflow case들을 다루겠다.

 

시작하기에 앞서 overflow의 뜻부터 정리를 해보자.

 

우리는 변수를 선언할 때 data type을 같이 지정해주는데, 이때 내부적으로는 각 data type에 맞는 특정 수의 byte들을 할당받게 된다.

 

예를 들면 int는 4 byte를 할당받고, 2,147,483,648 ~ 2,147,483,647 범위의 수를 표현할 수 있다.

long long의 경우는 8 byte를 할당받고, –9,223,372,036,854,775,808 ~ 9,223,372,036,854,775,807 범위의 수를 표현할 수 있다.

 

이때 int형 값을 다루다가 4 byte를 넘는 상황이 발생하면?

→ 이 상황을 overflow라고 부른다.

---

문제의 조건은 아래와 같다.

1 ≤ 사람 수 ≤ 1,000,000,000

1 ≤ 심사관의 심사 시간 ≤ 1,000,000,000

1 ≤ 심사관 수 ≤ 100,000

 

그리고 

 

위 조건을 바탕으로 고려해야할 overflow case들은 아래와 같다.

---

『 고려해야할 overflow cases 』

1. 심사시간은 1,000,000,000 × 1,000,000,000와 같은 경우처럼 int의 범위를 넘어갈 수 있다. 

∴ long long으로 선언해야 한다.

 

2. int × int 연산을 할 때, 결괏값이 int 범위보다 큰 경우, int의 범위 밖의 bit가 손실될 수 있다.

∴ 둘 중 하나는 long long으로 upcasting 하고 연산을 해야 한다.

 

 

보다 자세한 내용은 코드에 달린 주석을 참고해주세요~!

---

Code

https://github.com/changyeon2/Algorithm/blob/master/programmers/%EC%9E%85%EA%B5%AD%EC%8B%AC%EC%82%AC/C%2B%2B/solution%201.cpp

---

Reference

https://docs.microsoft.com/ko-kr/cpp/cpp/data-type-ranges?view=msvc-160