백준 1300 내리막길

문제링크 : https://www.acmicpc.net/problem/1300

아이디어

• 일단 브루트포스로, N*N 탐색 수행
  • 시간복잡도 : O(N^2) = 1e10 > 시간초과
    • 내가 어떤 수를 정했을때, 그 수보다 작거나 같은수의 개수를 구하는 방법
  • 최소 시간복잡도 : O(N)
  • A[j][i]에서, j만큼 나눠서 더하면 됨
    • 단, 이때 최대값은 N 초과하면 안됨
      • 그럼 숫자를 이진탐색하면서
      • k보다 그 숫자보다 작은 숫자가 크거나 같은 값을 구하면 됨

시간복잡도 계산

• 작거나 같은 수 구하는 방법 : O(N)
  • 이진탐색 : lgN
  • 총합 : O(NlgN)

자료구조

• 해당 수보다 작은 수 구할때
  • 최대값 : N * N = N^2 = 1e10 > long long 사용

코드(C++)

#include <iostream>
 
using namespace std;
typedef long long ll;
 
int N,K;
 
ll cal(int num) {
    int rs=0;
    for(int i=1; i<=N; i++) {
        // 한 줄에 최대 N개까지 있음
        rs += min(N, num/i);
    }
    return rs;
}
 
int binsearch(int st, int en, int tar) {
    if(st== en) {
        return st;
    }
    
    int mid = (st+en)/2;
    if(cal(mid) < (ll)tar) return binsearch(mid+1, en, tar);
    else return binsearch(st, mid, tar);
}
 
int main() {
    cin >> N >> K;
    
    // 구하려는 값은 최대 K보다 클 수 없음
    cout << binsearch(1,K,K) << '\n';
    return 0;
}
 

문제유형

• 이진탐색 - 케이스를 이분탐색

비슷한 문제

• https://www.acmicpc.net/problem/1300
• https://www.acmicpc.net/problem/1939
• https://www.acmicpc.net/problem/2805
• https://www.acmicpc.net/problem/1654