문제

문제 링크

어떻게 접근할 것인가

  • 전혀 감이 잡히지 않다가 욱제님의 블로그를 가보고 문제를 어떻게 접근할지 생각할 수 있게 되었다.욱제님의 블로그
  • i번째 숫자들 중에서 임의의 숫자 m을 넘지 않는 애들을 다 모아주면 된다.
  • 그렇다면 일일이 매 행마다 m을 넘지 않을 때까지 세주려고 했으나…

i행의 개수 세기

  • i행의 숫자들은 i*1, i*2, i*3, …, i*j 까지 m과 작거나 같다고 하자.
  • 그럼 i * j <= m 이라는 식이 나온다.
  • 이 식을 변형하면 j <= m / i 라고 할 수 있다.
  • 즉, j의 최대값은 m / i 인 것이다.

여기서 문제는 j의 최대값이 행렬의 사이즈를 초과할 수는 없기 때문에 min(m/i, n)의 값으로 취한다.

어떻게 이분탐색할 것인가?

  • 임의의 수 mid에 대해서 mid와 같거나 작은 수의 개수를 cnt에 다 더해줄 때
  • cnt의 값이 k 값보다 크거나 같게 되는 최소 mid값을 찾아주면 된다.
  • 즉, 위의 조건을 만족하는 lower bound를 찾아주면 된다.
  • lower bound라면 cnt가 k보다 크거나 같게 하는 mid의 최종값을 저장하면 된다.(right 값을 mid -1로 업데이트할 때 ans도 업데이트한다.)

코드

#include <cstdio>

int main(){
    long long l = 1, r, n, k, mid, cnt, ans;
    scanf("%lld %lld", &n, &k);
    r = k;
    while(l <= r){
        printf("%lld %lld\n", l, r);
        mid = (l+r)/2, cnt = 0;
        for(int i = 1; i <= n; i++)cnt = mid / i < n ? cnt + mid / i : cnt + n;
        if(cnt >= k) ans = mid, r = mid - 1;
        else l = mid + 1;   
    }
    printf("%lld", ans);
}

느낀점

  • 이해하더라도.. 이건 말이 안된다…
  • 갯수 세는 과정(n^2)을 n으로 바꿨다… 내 머리에서 이런게 나올까 싶다.
  • 일단 내가 이해한 것에 만족하고 다시한번 정확하게 잡고 넘어가자
  • lower_bound는 right을 업데이트할 때 answer을 같이 업데이트
  • upper_bound는 left를 업데이트할 때 answer을 같이 업데이트
  • 다음에는 좀더 자아아알 접근해보자아:) 그래도 잘했따!!