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

+ Recent posts

티스토리툴바