이분탐색(백준 1300번)

백준 1300번

개인적으로 좀 어려웠던 문제였다. 정말 무수하게 틀렸다. 이 문제 정답 비율을 낮추는데 기여한 것 같다. 

 

웩... 무수하게 틀린 나와 다른 이들의 흔적

우선 내가 짠 코드부터 올려보면.. 

//
//  main.cpp
//  1300
//
//  Created by CFox on 2020/03/11.
//  Copyright © 2020 CFox. All rights reserved.
//

#include <iostream>


long long min(long long a, int b){
    if(a>=b) return b;
    else return a;
}

int main(int argc, const char * argv[]) {
    long long n;
    long long k;
    
    scanf("%lld",&n);
    scanf("%lld",&k);
    long long lo = 1;
    long long hi = n*n;
    long long ans = 0;
    while(lo<=hi){
        long long mid = (lo+hi)/2;
        long long count = 0;
        
        for(long long i=1;i<n+1;i++){
            count += min(mid/i, n);
        }
        
        if(count>=k){
            ans = mid;
            hi = mid-1;
        }
        else lo = mid+1;
    }
    
    printf("%lld",ans);
    
}

/* 만약 23, 24번째가 20인 경우, 23번째와 24번째를 물어봤을 때, 둘 다 답이 20이 나와야함
   구상한 코드를 바탕으로 읽어가는 경우 20이 lo, 21이 hi 값에 도달
   그 다음, 코드를 끝내야 하는데 계속 돌아서 문제가 생김 이것을 예외 처리를 하던가 해서 해결해야함
   그리고 지난번부터 생각하던 문제... 만약 n,n+1,n+2 번째가 20을 답으로 갖는다고 하자(가정)
   중간에 mid 값이 20이 나온 경우, 다음 hi 값은 19다. 따라서 20에 접근을 할 수 없다. 이 경우를 해결 하려면
   또 예외 처리를 해주어야 한다. 이 모든 경우를 저 예외 처리로 할 수 있을 것 같다는 생각이 든다..
 1 2 3 4 5
 2 4 6 8 10
 3 6 9 12 15
 4 8 12 16 20
 5 10 15 20 25
 6 12 18 24 30
  
 
 
*/

정말 엄청나게 틀리고 틀려서 얻어낸 답이다. 우선 접근부터 어려웠는데.. 

처음에는 단순하게 NXN 모든 값들을 비교해서 이분탐색으로 하려했는데 시간복잡도가 N 제곱이 되는 바람에 시간초과가 계속 났다. 

 

이를 해결하기 위해서 도입한 코드가 다음과 같다. 

 

---

for(int i=1;i<n+1;i++){
            count += min(mid/i, n);
        }

시간 복잡을 N 제곱에서 NlongN 으로 낮추는데 기여한 코드이다. 

어차피 모든 input들은 잘 생각해보면 

 

1의 배수 .... 

2의 배수.... 

3의 배수.....

4의 배수...

..

.. 

N의 배수... 

 

이런 정사각형 구조를 띄고 있는데, 만약 우리가 이분탐색으로 통해, 답이라고 가정하는 mid의 값이 몇번째인지 알려면 

 

이것을 i로 나누게 되면 i번째 줄에서 자기보다 작은게 몇개나 있나 알 수 있다. 

 

가령, N 이 5인 5X5 정사각형에서 세 번째 줄은 3,6,9,12,15 인데 주어진 mid의 값이 13이라고 해보자. 

 

3번째 줄에서는 13보다 작은 값들이 3,6,9,12 인데 이는 13/3 과 같다. 당연하게도. 이렇게 몫을 이용하면 각 줄마다 주어진 mid 의 값보다 작은 값들이 몇 개 있는지 알 수 있다. 이걸 반복문을 통해 모든 줄에서 검사해보면, 당연히 mid보다 작거나 같은 값들이 몇 개 있는지 알 수 있다. (만약 mid가 12 이여도, 3으로 나눈 몫은 4이기 때문에, 같은 값들도 카운팅된다.) 

 

여기서 생각을 한 번 해야 하는게, min을 쓴 것인데, n 과 비교하여 썼다. 그 이유는 예를 들면 mid의 값이 25이고, 첫번째 줄에서 테스트 하는 경우, 나눈 몫이 25가 되는데(5X5 인 경우), 이 경우 첫번째 줄에서 mid인 25보다 작은 값들의 개수가 5개 이므로 25개는 당연히 말이 안된다. 즉 몫이 각 줄의 우측끝값보다 큰 경우, 각 줄에서 mid 값보다 작은 것의 개수는 그 줄에 있는 모든 값들의 개수(여기서는 5개)와 같으므로 min을 써서 해결했다 .

 

그리고도 틀렸는데 이번에는 뒤에 이분탐색 예외처리가 잘못되었다. 

 

위 코드에는 ans이라는 변수를 넣어 중간에 하이잭하는데 성공했지만, 이전에는 그런게 없었다. 

 

---

 if(count>=k){
            hi = mid;
        }
        else lo = mid;

또한 하던대로 hi와 lo를 mid 로 설정했는데, 이러면 틀리게 됩니다. 

 

가령 예를 들자면 4X4 를 생각해봅시다. 14,15번째는 12의 값을 갖게 됩니다. 

근데 만약 mid 가 13인 경우, count는 마찬가지로 15를 가지게 됩니다. 14번째를 구하는 input 이면 상관 없지만 15번째를 구하는 input 이면, 13이어도 문제가 없기 때문에 결국 답이 13으로 나오게 된다. 이는 mid의 값이 14,15 여도 마찬가지이다. 

 

이를 해결하기 위해 hi 인 경우, mid-1을 통해 바로 아래 값을 한 번 검증하고, lo 인 경우도 바로 위의 값을 검증한다.(반대로 생각하면 당연) 

 

또한 정답이 만약 20인데 lo 가 20, hi 가 21인 경우, mid의 값은 20이 되어버리고 이 경우, hi가 19가 되어버리기에, 반복문이 종료되지만 hi 값을 답으로 배출하면 틀리게 된다. 따라서 ans라는 변수를 만들어 보관해주는 용도로 사용해 배출한다. 

 

---

 

마지막으로 처음에는 n, k를 int 라는 변수로 받았었다. 크기로는 충분히 들어가기 때문에. 근데 계속 틀려서 진짜 어디서 틀렸나 엄청 고민했는데 .. 

 

long long hi = n*n;

에서 에러가 났다. n이 100000인 경우 제곱하게 되면 hi 값에 담기기 전에, 오버플로우가 생겨버려서... 

 

애초에 받을 때, n을 long long 자료형으로 받아도 되고 

또는 int 로 받고 

 

hi의 값을 n*n이 아닌, k라고 설정해도 된다. 

 

* 저게 가능한 이유는 엄밀하게 증명하기는 어렵지만 대충 생각해봤을 때, 모든 숫자를 나열하면 그것의 인덱스보다 작기 때문이다.  

 

3x3 의 경우를 생각해보자.              1,2,2,3,3,4,6,6,9 

인덱스는                                        1,2,3,4,5,6,7,8,9 

 

근데 뭔가 일반화 시키기가 어렵다. 아시는 분 알려주시면 감사하겠습니다. 

 

아무튼 이렇게 해서, 힘든 과정이 전부 끝났다. 나에게는 어려웠던 이분탐색이었다.