[APS] 백준 9998. 블록 쌓기 C++ 풀이 (이분 탐색)

 Gold IV  https://www.acmicpc.net/problem/9998

9998번: 블록 쌓기

 

 

 Problem 

1. 윤형이와 동혁이가 너비 N(1 ≤ N ≤ 300,000, N은 홀수), 최대 높이 10¹²의 블록을 쌓는다.

2. 블록을 쌓거나 빼면서 두 개의 똑같은 건물을 만든다. 이때, 인접한 두 열의 블록의 개수는 정확히 한 개씩만 차이나야 하며 블록의 개수가 가장 적은 열은 정중앙이어야 한다. (V 모양이 되도록)

3. 무한히 많은 블록이 있을 때, 블록을 빼거나 쌓는 횟수의 최솟값을 구한다.

 

 

 Solution 

먼저, 높이가 int형의 범위를 훨씬 벗어나기 때문에 입력을 받을 때도, 숫자를 다룰 때도 long long으로 선언해야 합니다. 다행히 최대 너비와 최대 높이를 곱해도 long long형의 범위는 벗어나지 않습니다. 또한, 입력값이 매우 크기 때문에 시간 복잡도를 logN 정도인 알고리즘을 사용해야겠네요.

아무 생각 없이 생각해보면(?) 전체 블록 높이의 평균 정도로 맞추면 최솟값이 아닐까...? 라는 생각이 드는데요. 그대로 평균값을 구하는 문제는 아니고 양 끝을 설정하고 그 가운데 값으로 답을 점점 찾아가는 이분 탐색 문제입니다. 일반적인 이분 탐색과 비슷하게, 저는 탐색할 값을 '블록을 빼거나 쌓는 횟수'라고 두고, '블록의 가장 가운데 값(가장 낮은 높이)'을 기준으로 변수를 갱신하고 종료 조건을 설정했습니다.

 

1. left는 가장 최솟값인 0, right는 가장 최댓값인 10¹² - N / 2, 그리고 mid는 그 가운데 값으로 시작한다.
   * 이 때, 가장 최댓값을 10¹²이나 N 등으로 설정하면 틀리게 되니 유의해주세요!
2. 블록을 비교하면서 가장 가운데 블록의 높이가 left와 right일 때 블록을 빼거나 쌓는 횟수를 구한다. (아래에서 calc() 함수에 해당)
3. left의 횟수가 right의 횟수보다 작으면 right에 mid - 1을 대입해주고, 새로운 right의 횟수를 구한다. 반대의 경우라면 left에 mid + 1을 대입해주고, 새로운 left의 횟수를 구한다.
4. left의 횟수보다 right의 횟수가 작아지면 반복문을 종료하고, 둘 중 최솟값을 출력한다.

 

 

 Code 

위에서 left, right, left의 횟수, right의 횟수는 min_low, max_low, min_block, max_block 변수입니다.