[BOJ][2343번] 기타 레슨

안녕하세요 Dibrary입니다.

이번에는 이진탐색을 사용해서 풀어야 하는 문제를 정리해보겠습니다.

처음에 나름 알머리 굴리다가 시간초과로 실패를 겪은 문제입니다.

2343번: 기타 레슨

 

---

문제를 처음 보자마자 떠오른 생각은 아래와 같습니다.

1. M만큼만 자르면 된다. (이걸 반복문에서 캐치해야 할 것 같다.)
2. M만큼 자르는 M-1 포인터를 for문으로 돌리면 어떨까.

근데 2번에서 생각해보니 거의 100000! 번에 가까운 연산이 이뤄질 수도 있다는 생각이 들어서 위 방법은 곧바로 포기 했습니다.

 

다른 생각은 이렇습니다.

1. M이 1은 아닌이상 적어도 주어진 배열 값의 '총합' 만큼은 아닐 것이다. 즉, 반복문을 돌더라도 절반 혹은 2/3정도 까지의 합부터 for문으로 돌려도 되지 않을까.
2. 그리고 배열에 요소를 더해 나가면서 기준값을 넘으면 count를 증가시키고, 그 count가 M이면서 동시에 max_size가 가장 작은 값을 찾으면 된다.

그래서 아래와 같은 코드를 작성했었죠

근데, 위 코드는 시간초과 걸립니다.

왜냐면, for k in range(val, -1, -1): 부분에서 결국, val부터 0까지를 '전부 탐색'하는 꼴이 되어 버리니까요...

 

---

시간초과 없는 해답은 이진탐색이었습니다.

이 코드를 요모조모 뜯어보면서 이진탐색에 대해 좀 더 알게 된거 같아서 좋았습니다.

먼저, 이진탐색을 할 때 가장 중요한 것은 '뭘 기준으로 mid값을 구해 나갈것이냐'는 것입니다.
위 코드는 주어진 배열을 M 숫자만큼 그룹을 지었을 때, 그 그룹의 최대값을 mid로 찾아내고자 하는 코드 입니다.

예제에서 주어진 1,2,3,4,5,6,7,8,9를 실행 해 보면

l,   r,  mid, ans,cnt
9, 26, 27,  27,  2
9, 16, 17,  17,  3
13, 16, 12, 17, 5
15, 16, 14, 17, 5
16, 16, 15, 17, 4
17, 16, 16, 17, 4

이렇게 값들이 변경됩니다. 여기서 우리는 cnt가 M인 것을 찾아야 하고, 그 와중에 ans가 가장 작은 것을 찾아야 하죠.

위 요건을 만족하는 경우는 ans가 17이고, cnt가 3인 경우밖에 없습니다.

그래서 예제의 출력은 17로 나오게 되는 것이죠.

 

저는 이 코드를 볼 때 헷갈렸던 부분은 아래 2곳 코드 부분입니다.

먼저 첫 번째는 for문입니다.

mid라는 총합 값을 기준으로 배열의 값을 계속 더해나가는 것이죠.
if는 배열요소를 합한 값이 mid값보다 큰 경우에 한해 그룹 갯수(cnt)를 1 증가시키고 다시 배열요소의 합(sum)을 0으로 변경한 것입니다.

이때 mid값이 뭔지 몰랐었기 때문에 왜 mid를 기준으로 나눠지는 것인가.... 이런 생각이 들었었죠.

 

두 번째는 왼쪽 경계, 오른쪽 경계를 움직이는 부분입니다.

그룹 지은 갯수가 m보다 크다면, m이 너무 작다는 말입니다. 그래서 왼쪽 경계(l)을 mid 위로 올려주는 것이죠. (이렇게 하면 mid 계산할 때 l+r이 커지므로 mid값이 커지게 됩니다)

이 cnt와 m의 비교로 왼쪽 경계(l)을 왜 저렇게 움직이는지 고민을 많이 했었습니다.

 

이진탐색이 곧바로 떠오르지는 않지만, 떠올랐다 하더라도 구현이 꽤나 어려웠을것 같은 문제네요.