문제링크 : https://leetcode.com/problems/container-with-most-water/


문제 추상화

  • 물을 담을때 가장 많이 담기는 크기 구하기
  • 물이 담긴다 >> 두 막대중 더 작은것 * 두 막대의 거리
  • 둘다 높아야되고, 사이가 멀어야함

아이디어

  • 브루트포스 접근 : 각 막대에 대해서 모든 막대를 탐색해보자
    • 시간복잡도 : O(N^2) > 1e10 > 시간초과
  • 시간복잡도 줄일수 있는방법
    • 이진탐색? > 정렬하고 있지 않아서 불가
    • DP? > 이전 값을 재활용 할 수가 없음
    • 투포인터? > 전체에서 가장 큰 값을 찾아야함
      • st, en이 왼쪽에서 시작? > st, en을 움직이는 조건이 어려움
      • st은 왼쪽에서, en은 오른쪽에서 시작
        • 둘중에 작은 값을 움직이면 됨 > 이렇게 해보자
  • 투포인터 st 왼쪽에서, en 오른쪽에서
    • 최대값을 갱신해줌
    • 둘중에 더 작은값이 이동
    • 최대값 리턴

시간복잡도 계산

  • 투포인터 순회 : O(N)

자료구조

  • 막대 높이 : int[N]
    • 막대 최대높이 : 1e4 > INT 가능
  • 투포인터 최대값 : 1e4 * 1e5 > 1e9 > INT 가능

코드(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public:
        int maxArea(vector<int>& height) {
            int st = 0;
            int en = height.size()-1;
 
            int maxv = 0;
            while(st!=en) {
                int area = min(height[st], height[en]) * (en-st);
                maxv = max(maxv, area);
 
                // 더 작은값을 움직이자
                // 같을때 어떤 값을 움직이냐가 차이가 있을까? > 없을 듯
                if(height[st] > height[en]) en--;
                else st++;
            }
 
        return maxv;
    }
};
cs

문제유형

  • Two pointer - 배열 순회
    • N^2 를 N에 푸는 방법
    • 어떤 연산값을 구해야할때, 순차적으로 구해야하는 경우

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


아이디어

  • 접근 1. 배열 4개를 모든 경우의수로 더할경우
    • O(N^4) : 4000^4 > 시간초과
  • 접근 2. 두개씩 더해서 이진탐색 사용 가능할까?
    • 두개씩 더한다음
    • 한개만 정렬을 해줌
    • 그다음 각각 더해서 0이되는 수를 찾기
    • 0이 되는 여러개가 있을 수 있잖아 > 마지막에 같으면 여러개 구하기
    • 시간복잡도
      • 두개씩 곱함 : N^2 * 2
      • 한개 정렬 : N^2 * lgN^2
      • 모든 수에대해 더해서 0이되는 수를 이진탐색으로 찾기 : N^2 * lgN^2
      • 더해서 0이 되는거 여러개 있을경우, 계속 더해주기 : N
      • 총합 : O(N^2 * 2 + N^2 * lgN^2 + N*2 * lgN^2 * N) = O(N^3 * lgN^2) = 64e9 * 20 > 시간초과
  • 접근 3. 두개씩 더해서 투포인터 사용
    • 두개씩 더한 다음 모두 정렬
    • 각각의 배열에서 하나는 왼쪽(st)부터, 하나는 오른쪽(en)부터 시작해서 더해서 0이되는값 찾기
      • 더해서 0이 될경우, 각각 값이 같은 수 구해서 곱하기
      • 이떄, 더해서 0이될경우, 포인터 넘어가므로 O(N) 사용할 필요없음
    • 더해서 0보다 작을경우 st++, 클경우 en--

시간복잡도 계산

  • 두개 더한다음 정렬 : N^2 * 2 + N^2*lgN^2 * 2
  • 투포인터 수행 : N^2 * 2
  • 총합 : O(N^22 + N^2lgN^22 + N^22) = O(N^2*lgN^2)

자료구조

  • A,B,C,D 배열
    • 최대값 : 2^28 > INT 가능
  • 두개씩 더해준 값 : AB, CD
    • 최대값 : 2^29 > INT 가능
  • 합이 0이되는 쌍의 개수
    • 4000^4 > long long 사용

코드(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <algorithm>
 
using namespace std;
typedef long long ll;
 
int A[4010];
int B[4010];
int C[4010];
int D[4010];
int AB[16000010];
int CD[16000010];
 
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n; cin >> n;
    for(int i=0; i<n; i++) {
        cin >> A[i] >> B[i] >> C[i] >> D[i];
    }
    
    // 두개씩 더하기
    int k=0;
    for(int j=0; j<n; j++) {
        for(int i=0; i<n; i++) {
            AB[k] = A[j] + B[i];
            CD[k] = C[j] + D[i];
            k++;
        }
    }
    
    // 정렬
    sort(AB, AB+k);
    sort(CD, CD+k);
    
    ll cnt=0;
 
    int st = 0;
    int en = k-1;
    
    while(st <k && en >=0) {
        int sumv =AB[st] + CD[en];
        if(sumv == 0) {
            // 두개가 같은게 여러개 있을 수 있음
            // 같은 값을 곱해서 더해주기
            int originSt = st;
            int sameSt = 0;
            while(AB[st] + CD[en] == 0) {
                sameSt++;
                st++;
                if(st==k) break;
            }
           
            int sameEn = 0;
            while(AB[originSt] + CD[en] == 0) {
                sameEn++;
                en--;
                if(en<0) break;
            }
            cnt += sameSt * sameEn;
        } else if(sumv < 0) {
            st++;
        } else {
            en--;
        }
    }
    
    cout << cnt << '\n';
    return 0;
}
 
cs

문제유형

  • Two pointer - 두 배열의 pointer
    • 두배열의 합이나 곱으로 모든 경우의 수를 따져야할때
    • 양쪽에서 st, en놓고 올라가고 줄어드는 방법
    • 이때 조심해야할것 : 배열이 같은 값이 중복될 수 있음
    • 이떄 중복되는것 계산해줘야함

'알고리즘 > 백준' 카테고리의 다른 글

백준 18233 민준이와 마산 그리고 건우  (0) 2021.04.20
백준 1238 파티  (0) 2021.04.20
백준 2581 소수  (0) 2021.03.18
백준 12865 평범한 배낭  (0) 2021.03.18
백준 8983 사냥꾼  (0) 2021.03.18

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


아이디어

  • 소수구하는방법 1 : 2~sqrt(N)까지 나눠서 구할 수 있음
    • 시간복잡도 : O(N^1/2)
  • 소수 더 빨리 구하는법 : 에라토스테네스의 채
    • 2부터 원하는 숫자까지
    • 숫자를 배수가 되게 더해가면서 체크를해줌(이 수는 소수가 아님)
    • 처음에 체크가 되어있지 않은 수는 소수이므로 별도로 체크
    • 시간복잡도 : O(NlgNlgN)
  • 소수를 에라토스테네스의 채로 미리 구해놓을떄
  • M보다 클경우, 소수의 합을 구하고, 최솟값 출력

시간복잡도 계산

  • 소수구하면서 합, 최솟값 구함 : O(NlgNlgN)

자료구조

  • 이미 지나간것 체크 : bool chk
  • 소수 합 : 최대 1e4 * 1e4 > INT 가능

코드(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
 
using namespace std;
 
bool chk[10010];
int main() {
    fill(chk, chk+10010, 0);
    
    int M,N; cin >> M >> N;
    
    int sumv= 0;
    int minv = 10010;
    for(int i=2; i<=N; i++) {
        // 소수일때
        if(chk[i] == 0) {
            chk[i] = 1;
            // M보다 크다면
            if(i>=M) {
                sumv += i;
                minv = min(minv, i);
            }
        }
        
        int cur = i;
        while(cur<=N) {
            chk[cur] = 1;
            cur += i;
        }
    }
    
    if(sumv == 0) cout << -1 << '\n';
    else {
        cout << sumv << '\n';
        cout << minv << '\n';
    }
    return 0;
}
 
cs

문제유형

  • 에라토스테네스의 채
    • 일반적으로 소수인지 확인할떄 2부터 sqrt(N)까지 확인 >> N * sqrt(N) >> 시간초과
    • 소수 개수 NlglgN으로 구할수 있음
    • 각 배수를 체크해주고, 그 배수 오면 넘어가는 방법

'알고리즘 > 백준' 카테고리의 다른 글

백준 1238 파티  (0) 2021.04.20
백준 7453 합이 0인 네 정수  (0) 2021.03.19
백준 12865 평범한 배낭  (0) 2021.03.18
백준 8983 사냥꾼  (0) 2021.03.18
백준 2805 나무 자르기  (0) 2021.03.18

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

아이디어

  • 대표적인 knapsack 문제
  • 가치와, 종류로 dp를 나눠서 계산
  • dp[N][K] : K의 무게에서, N개의 종류를 가지고있을때 최대의 가치
    • dp[N][K] = max(dp[N-1][K] : 안담는경우, dp[K-stuff[N]][N-1] : 담는경우)
    • 초기값 : dp[0][all] = 0
      • dp[1][stuff[1] ~ 끝 = stuff[1]

시간복잡도 계산

  • 모든 종류에 대해 : N
  • 모든 가치의 값을 구할 때 : K
  • O(N*K)

자료구조

  • dp 배열 : dp[N][K]
    • 가질수 있는 최대가치 : 1e5 * 1e3 = 1e8 > INT 가능
    • 이떄, dp 배열을 재활용해서 dp[K]으로만 사용할 수 도 있음
      • 이전값 덮어쓰는 경우
      • 단 이떄, 중복해서 물건 넣을 수 있는 경우는 상관없지만,
      • 한개씩밖에 넣지 못할 경우 뒤에서부터 값을 갱신해줘야함
  • stuff pair<int, int>[]
    • 무게 최대값 : 1e5 > INT 가능
    • 가치 최대값 : 1e3 > INT 가능

코드(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <iostream>
 
using namespace std;
typedef pair<int, int> pi2;
 
int dp[110][100010];
pi2 stuff[110];
int main() {
    
    fill(&dp[0][0], &dp[109][100010], 0);
    int N,K; cin >> N >> K;
    
    for(int i=1; i<=N; i++) {
        int a,b; cin >> a >> b;
        stuff[i] = make_pair(a,b);
    }
    
    // 초기값 : dp[1][stuff[1] ~ 끝] = stuff[1]
    for(int i=stuff[1].first; i<=K; i++) {
        dp[1][i] = stuff[1].second;
    }
    
    for(int j=2; j<=N; j++) {
        for(int i=0; i<=K; i++) {
            // 안담는경우
            dp[j][i] = dp[j-1][i];
            // 무게를 담을 수 있으면
            if(i-stuff[j].first >=0) dp[j][i] = max(dp[j][i], dp[j-1][i-stuff[j].first] + stuff[j].second);
            
        }
    }
    
    cout << dp[N][K] << '\n';
    
    return 0;
}
 
cs

1차원 배열 사용해서 푸는경우 코드(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <iostream>
 
using namespace std;
typedef pair<int, int> pi2;
 
int dp[100010];
pi2 stuff[110];
int main() {
    
    fill(dp, dp+100010, 0);
    int N,K; cin >> N >> K;
    
    for(int i=1; i<=N; i++) {
        int a,b; cin >> a >> b;
        stuff[i] = make_pair(a,b);
    }
    
    // 초기값 : dp[1][stuff[1] ~ 끝] = stuff[1]
    for(int i=stuff[1].first; i<=K; i++) {
        dp[i] = stuff[1].second;
    }
    
    for(int j=2; j<=N; j++) {
        // 이미 담은 물건을 다시 담을수있기 때문에 뒤에서부터 dp만들어줌
        for(int i=K; i>=0; i--) {
            // 무게를 담을 수 있으면
            if(i-stuff[j].first >=0) dp[i] = max(dp[i], dp[i-stuff[j].first] + stuff[j].second);
            
        }
    }
    
    cout << dp[K] << '\n';
    
    return 0;
}
 
cs

문제유형

  • DP - 이전 종류값 만을 포함
    • dp[N][K] = N개의 종류를 가지고있을때, K가치를 가질때의 dp 값
      • 단, 이전값만을 활용하는경우, dp[N]으로 줄여서 사용할 수 있음
      • 단 한번만 빼줘야함, 뺀곳에 여러번 뺀 경우의 수가 담겨있음
    • 대표문제 : knapsack
      • https://www.acmicpc.net/problem/12865
      • 여러 종류의 아이템을 한번씩 넣을수있을때, 한정된 비용에서의 최대가치 구하는 문제
      • dp[N][K] : N개의 종류를 들고, K만큼의 무게에서의 가질수 있는 최대 가치

비슷한 문제

'알고리즘 > 백준' 카테고리의 다른 글

백준 7453 합이 0인 네 정수  (0) 2021.03.19
백준 2581 소수  (0) 2021.03.18
백준 8983 사냥꾼  (0) 2021.03.18
백준 2805 나무 자르기  (0) 2021.03.18
백준 1939 중량제한  (0) 2021.03.18

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


아이디어

  • 접근 1. 모든 사대 위치에서 동물의 위치를 비교
    • 모든 사대위치 : O(M)
    • 동물 위치 : O(N)
    • 총합 : O(NM) > 시간초과
  • 접근 2. 모든 동물에서 사정거리 안에 있는 사대가 있는지 확인
    • 사정거리 - 동물 y좌표 안에 사대가 있으면 됨
    • 사대를 정렬해서, 그 사이에 있는 값을 찾음
    • 사이에 있는 값을 찾는 방법
      • A와 B 사이의 값을 찾는다고 했을떄
      • A와 같거나 큰값을 찾은다음에
      • B값보다 작은지 확인

시간복잡도 계산

  • 사대 정렬 : MlgM
  • 모든 동물 : N
  • 사대 이진탐색 : lgM
  • 총합 : MlgM + NlgM = O(NlgN) > 가능

자료구조

  • 동물 위치 : pair<int, int> []
    • y,x 좌표 최대 1e9 > INT 가능
  • 사대 위치 : int[]
    • x 좌표 최대 1e9 > INT 가능
  • 잡을수 있는 동물수 cnt
    • 최대 1e5 > INT 가능

코드(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <algorithm>
 
using namespace std;
typedef pair<int, int> pi2;
 
pi2 animal[100010];
int gun[100010];
int N,M,L;
 
bool binsearch(int st, int en, int lx, int rx) {
    if(st==en) {
        // lx와 rx 사이에 있을경우 true
        if(lx<=gun[st] && gun[st] <= rx) return 1;
        return 0;
    }
    
    int mid = (st+en)/2;
    if(gun[mid] <lx) return binsearch(mid+1, en, lx, rx);
    else return binsearch(st, mid, lx, rx);
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> M >> N >> L;
    for(int i=0; i<M; i++) cin >> gun[i];
    for(int i=0; i<N; i++) {
        int x,y; cin >> x >> y;
        animal[i] = make_pair(y,x);
    }
    
    // 사대 정렬
    sort(gun, gun+M);
    
    int cnt=0;
    // 모든 동물에 대해 잡을 수 있는 사대 있는지 확인
    for(int i=0; i<N; i++) {
        int ey = animal[i].first;
        int ex = animal[i].second;
        
        int dy = L - ey;
        if(dy < 0) continue;
        
        // x좌표 내에 사대 있으면 카운트 증가
        if(binsearch(0,M-1,ex-dy, ex+dy)) cnt++;
    }
    cout << cnt << '\n';
    
    return 0;
}
 
cs

문제유형

  • 이진탐색 - 모든케이스에서 이분탐색

비슷한 문제

'알고리즘 > 백준' 카테고리의 다른 글

백준 2581 소수  (0) 2021.03.18
백준 12865 평범한 배낭  (0) 2021.03.18
백준 2805 나무 자르기  (0) 2021.03.18
백준 1939 중량제한  (0) 2021.03.18
백준 1300 내리막길  (0) 2021.03.18

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


아이디어

  • 접근 1. 브루트포스로 일단 접근
    • 모든 높이에 대해, 모든 나무를 탐색하여 높이의 최대값을 구함
    • O(K * N) = O(1e9 * 1e6) > 시간초과
  • 접근 2. 높이를 이진탐색하여, 그떄마다 가져갈 수 있는 나무를 탐색
    • 이떄, 가능한것중에 가장 큰 값을 가져가야함

시간복잡도 계산

  • 높이를 이진탐색 : O(lgK)
    • 각 높이에서 모든 나무를 순회 : O(N)
    • 총합 : O(NlgK) = 1e6 * lge9 = 1e6 * 30 = 3e7 > 가능'

자료구조

  • 전체 나무 : int[]
    • 나무 최대 길이 : 2e9 > int 가능
  • 자르는 나무 높이 총합
    • 최대값 : 나무수 * 나무길이 최대 = 1e6 * 2e9 > long long 사용

코드(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <iostream>
 
using namespace std;
typedef long long ll;
 
int tree[1000010];
int N,M;
 
bool chk(int num) {
    ll rs=0;
    for(int i=0; i<N; i++) {
        // 나무 자르고 남은값
        int et = tree[i] - num;
        if(et > 0) rs += et;
    }
    
    if(rs >= M) return 1;
    return 0;
}
 
int binsearch(int st, int en) {
    if(st==en) return st;
    
    // 여기서 (st+en)/2 로 계산하게되면,
    // 가능한 것중 가장 낮은값을 찾게됨
    // 가능한 것중 가장 높은 값 찾기위해 (st+en)/2 로 사용
    int mid = (st+en+1)/2;
    if(chk(mid) == true) return binsearch(mid, en);
    else return binsearch(st, mid-1);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    cin >> N >> M;
    // 나무값 먼저 받아옴
    for(int i=0; i<N; i++) cin >> tree[i];
    
    cout << binsearch(0,1e9) << '\n';
    
    return 0;
}
 
cs

문제유형

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

비슷한 문제

'알고리즘 > 백준' 카테고리의 다른 글

백준 12865 평범한 배낭  (0) 2021.03.18
백준 8983 사냥꾼  (0) 2021.03.18
백준 1939 중량제한  (0) 2021.03.18
백준 1300 내리막길  (0) 2021.03.18
백준 1920 수 찾기  (0) 2021.03.18

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


아이디어

  • 접근 1. BFS로 두 섬을 잇는 경로 확인
    • 근데 BFS를 통해 최대값 구하기? > 불가능
  • 접근 2. 최소값이므로, 다익스트라?
    • 다익스트라는 간선의 가중치가 주어질떄 최소 거리를 구하는 문제
    • 이 문제는 연결할 수 있는 최대값을 구하는 문제이므로 불가능
  • 접근 3. 이진탐색으로 중량의 최대값을 구하기
    • 중량이 정해지면 BFS로 건널수 있는지 확인

시간복잡도 계산

  • 중량의 최대값 구하기 : lgC
    • BFS로 건널수 있는지 확인
      • BFS : O(V+E)
      • V : N
      • E : 2M (다리가 양방향이므로 2배)
      • O(V+E) = O(N + 2M) = O(N)
  • 총합 : O(lgC * N)
    • N : 1e5
    • lgC : 30
    • 총합 : 3e6 > 가능

자료구조

  • BFS 사용할 인접리스트 vector<pair<int, int>>
    • 거리는 최대 1e9이므로 INT 가능

코드(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
 
vector<pair<int, int>> adj[100010];
int st,en;
 
bool bfs(int num) {
    bool chk[100010];
    fill(chk, chk+100010, 0);
    
    queue<int> q;
    q.push(st);
    chk[st] = 1;
    
    while(!q.empty()) {
        int eq = q.front(); q.pop();
        if(eq==en) return 1;
        
        for(auto x : adj[eq]) {
            int ec = x.first;
            int ei = x.second;
            
            if(ec < num) continue;
            if(chk[ei]) continue;
            
            chk[ei] = 1;
            q.push(ei);
        }
        
    }
    
    return 0;
    
}
int binsearch(int st, int en) {
    if(st==en) {
        return st;
    }
 
    // 여기서 내림을 하게되면, 가능한 수중 가장 낮은 값을 찾게됨
    // 그래서 올림을해줘야 가능한수 중 가장 높은값을 찾음
    int mid = (st+en+1)/2;
    if(bfs(mid) == true) return binsearch(mid, en);
    else return binsearch(st, mid-1) ;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N,M; cin >> N >> M;
    for(int i=0; i<M; i++) {
        int a,b,c; cin >> a >> b >> c;
        adj[a].push_back(make_pair(c,b));
        adj[b].push_back(make_pair(c,a));
    }
    
    cin >> st >> en;
    
    cout << binsearch(1,1e9) << '\n';
    return 0;
}
 
 
cs

문제유형

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

비슷한 문제

'알고리즘 > 백준' 카테고리의 다른 글

백준 8983 사냥꾼  (0) 2021.03.18
백준 2805 나무 자르기  (0) 2021.03.18
백준 1300 내리막길  (0) 2021.03.18
백준 1920 수 찾기  (0) 2021.03.18
백준 1662 압축  (0) 2021.03.17

문제링크 : 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++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#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;
}
 
cs

문제유형

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

비슷한 문제

'알고리즘 > 백준' 카테고리의 다른 글

백준 2805 나무 자르기  (0) 2021.03.18
백준 1939 중량제한  (0) 2021.03.18
백준 1920 수 찾기  (0) 2021.03.18
백준 1662 압축  (0) 2021.03.17
백준 2304 창고 다각형  (0) 2021.03.17

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


아이디어

  • 일단 브루트포스로 모두 순회하면서 탐색할 경우
    • 쿼리 M개동안 N번을 돌아야함
    • 시간복잡도 : O(NM) = 1e10 > 시간초과
  • 이진탐색 사용해서, 해당 값 찾기
    • 찾은다음 인덱스 반환해서 같은 값인지확인

시간복잡도 계산

  • N개 정렬 : O(NlgN)
  • 쿼리 M번 : O(M)
  • 이진탐색 : O(lgN)
  • 총합 : O(NlgN + MlgN) = O(MlgN)

자료구조

  • 정수 저장 : map[100010];
    • 모든 정수 범위 : 2^31보다 작음 > INT 가능

코드(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <iostream>
#include <algorithm>
 
using namespace std;
 
int map[100010];
 
int binsearch(int st, int en, int tar) {
    if(st==en) {
        // 타겟이랑 값이 같은지 확인
        if(map[st] == tar) return 1;
        return 0;
    }
    
    // 이진탐색 lower bound
    int mid = (st+en)/2;
    if(map[mid] < tar) return binsearch(mid+1, en, tar);
    else return binsearch(st, mid, tar);
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N; cin >> N;
    for(int i=0; i<N; i++) cin >> map[i];
    sort(map, map+N);
    
    int M; cin >> M;
    for(int i=0; i<M; i++) {
        int num; cin >> num;
        cout << binsearch(0,N-1,num) << '\n';
    }
    return 0;
}
cs

문제유형

  • 이진탐색 - 모든케이스에서 이분탐색

비슷한 문제

'알고리즘 > 백준' 카테고리의 다른 글

백준 1939 중량제한  (0) 2021.03.18
백준 1300 내리막길  (0) 2021.03.18
백준 1662 압축  (0) 2021.03.17
백준 2304 창고 다각형  (0) 2021.03.17
백준 14719 빗물  (0) 2021.03.17

문제링크 : https://programmers.co.kr/learn/courses/30/lessons/49190


아이디어

  • 사방이 막히는 경우
    • 이미 지난 점을 다시 지나올때, 단, 이전에 도착한 방향과 똑같지 않아야함
      • 지난점을 체크하고
      • 지나온 방향도 체크해야함, 이때 역방향도 체크
    • X자를 그리며 화살표가 이동하는 경우
      • 점을 2번 이동하는 걸로 하자
      • 방이 최대 200000
      • 중복체크할때 배열로 하면 너무커짐
      • map으로 중복 체크하자

시간복잡도 계산

  • 배열 크기 전체 순회 : O(N)

자료구조

  • 중복체크 : map<pair<int, int>, bool>
    • 들어가는값 : 각각 y,x축 좌표
    • 최소값 : -2e5
    • 최대값 : 2e5
      • 중복 방향 체크 : map<tuple<int, int, int, int>,bool>
      • int pre : 이전 방향을 확인

코드(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <iostream>
#include <vector>
#include <map>
#include <tuple>
 
using namespace std;
 
map<pair<int, int>, bool> chk;
map<tuple<int, int, int, int>, bool> dirchk;
 
int dy[] = {-1,-1,0,1,1,1,0,-1};
int dx[] = {0,1,1,1,0,-1,-1,-1};
 
int solution(vector<int> arrows) {
    int cnt=0;
    
    int y = 0;
    int x = 0;
    chk[make_pair(y,x)] = 1;
    
    
    for(int i=0; i<arrows.size(); i++) {
        int tmp = 2;
        while(tmp--) {
            int ed = arrows[i];
            
            int ny = y + dy[ed];
            int nx = x + dx[ed];
            
            // 도착점이 중복값이면서, 같은 방향이 아닐경우
            if(chk[make_pair(ny,nx)] && dirchk[{ny,nx,y,x}] ==false) {
                cnt++;
            }
            
            chk[{ny, nx}] = 1;
            dirchk[{ny,nx,y,x}] = 1;
            dirchk[{y,x,ny,nx}] = 1;
            
            y = ny;
            x = nx;
        }
        
    }
    return cnt;
}
 
cs

문제유형

  • 시뮬레이션 - 새로생기는 영역 구하기
    • 새로 영역 생기는 경우 : 이미 지나온 간선 && 같은 방향으로 들어오지 않아야함
    • map 사용할경우 노드 너무많아지고, 음수 사용하기 위해 map 사용

+ Recent posts

티스토리툴바