문제링크 : 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://www.acmicpc.net/problem/1662


아이디어

  • 스택을 사용하여 (을 사용하면 나오는 위치를 우선 구해놓자
    • 재귀함수를 사용해서 (만나면 앞에 숫자에서 곱하기 사용

시간복잡도 계산

  • 스택사용해서 괄호 시작 및 끝나는 위치 매핑 : O(S)
    • 재귀함수 중 순회 : O(S)
  • 총합 : O(S)

자료구조

  • 괄호 시작 및 끝나는 위치 계산용 스택 : stack(int)
    • 스택안에 들어가는 값 : 각각 문자열 인덱스
    • 최대값 : 50 > INT 가능
      • 괄호 시작 및 끝나는 위치 기록 : map[60]
    • 들어가는 값 : 문자열 인덱스
    • 최대값 : 50 > INT 가능
      • 압축안된 문자열 길이 rs
    • 한번 괄호 쌍에 필요한 문자열 최소 3개
    • 그럼 최대 50/3 = 17번이 곱해질수 있음
    • 최대 9^17 > 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
#include <iostream>
#include <stack>
#include <string>
 
using namespace std;
typedef long long ll;
 
int map[60];
string s;
 
ll recur(int st, int en) {
    ll rs=0;
    for(int i=st; i<=en; i++) {
        
        // 만약 괄호 만나면 해당 괄호 끝에 해당하는 부분까지 곱해주기
        if(s[i] == '(') {
            // 이전글자 빼주기
            rs--;
            ll preChar = s[i-1]-'0';
            rs += preChar * recur(i+1,map[i]-1);
            // 괄호로 인덱스 이동
            i = map[i];
        } else {
            rs++;
        }
    }
    
    return rs;
}
 
int main() {
    fill(map, map+60, 0);
    
    cin >> s;
    stack<char> st;
    
    // 괄호 끝나는 위치 기록함
    for(int i=0; i<s.size(); i++) {
        char ec = s[i];
        if(ec == '(') {
            st.push(i);
        } else if(ec==')') {
            int ei = st.top(); st.pop();
            // 괄호 끝나는 위치 기록
            map[ei] = i;
        }
    }
    
    cout << recur(0, s.size()-1) << '\n';
    
    return 0;
}
 
cs

문제유형

  • 시뮬레이션 - 스택 압축
    • 괄호 통해서 압축하는문제
    • 사전에 스택으로, 각각 괄호에서 끝나는 부분 구해놓은 뒤
    • 재귀함수 통해서 괄호 나올때마다 계산해주는 문제

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

백준 1300 내리막길  (0) 2021.03.18
백준 1920 수 찾기  (0) 2021.03.18
백준 2304 창고 다각형  (0) 2021.03.17
백준 14719 빗물  (0) 2021.03.17
백준 14499 주사위 굴리기  (0) 2021.03.17

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


아이디어

  • 오목하게 들어간 부분이 없으니까, 최대값까지 점점 증가해야함
  • 최대값을 기준으로 왼쪽에서는 계속 증가해야하고, 오른쪽에서는 계속 감소해야함
  • 맨 오른쪽부터 시작해서 최대값까지 점점 증가하면 됨

시간복잡도 계산

  • 최대값 인덱스 구하기 : O(N)
  • 왼쪽에서부터, 오른쪽에서부터 최대값까지 순회 : O(N)

자료구조

  • 기둥 높이 기록 : map[N]
    • 최대값 : 1000 > INT 가능
      • 왼쪽에서부터 최대값 int maxLeft
    • 최대값 : 1000 > INT 가능
      • 오른쪽에서부터 최대값 int maxRight
    • 최대값 : 1000 > INT 가능
      • 모두 더한값 rs
    • 1000 * 1000 > 1e6 > 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
#include <iostream>
 
using namespace std;
 
int map[1010];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N; cin >> N;
    int maxv = 0;
    int maxi = 0;
    // 값 받으면서 최대값 인덱스 찾자
    for(int i=0; i<N; i++) {
        int a,b; cin >> a >> b;
        map[a] = b;
        if(map[a] > maxv ) {
            maxi = a;
            maxv = map[a];
        }
    }
    
    int rs=0;
    
    // 왼쪽에서부터 최대값 더함
    int maxLeft = 0;
    for(int i=0; i<maxi; i++) {
        maxLeft = max(maxLeft, map[i]);
        rs += maxLeft;
    }
    
    // 오른쪽쪽에서부터 최대값 더함
    int maxRight = 0;
    for(int i=1000; i>=maxi; i--) {
        maxRight = max(maxRight, map[i]);
        rs += maxRight;
    }
    
    cout << rs << '\n';
    return 0;
}
 
cs

문제유형

  • 시뮬레이션 - 히스토그램
    • 히스토그램 문제는 전체를 한번에 구하려면 어려워짐
    • 각각 위치에서 값을 더해주면 쉽게 할수있음

비슷한 문제

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

백준 1920 수 찾기  (0) 2021.03.18
백준 1662 압축  (0) 2021.03.17
백준 14719 빗물  (0) 2021.03.17
백준 14499 주사위 굴리기  (0) 2021.03.17
백준 1062 가르침  (0) 2021.03.17

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


아이디어

  • 전체에서 빗물이 어떻게 담기는지 계산하는건 어려움
    • 이런 히스토그램에서는 x축에서 한칸한칸 계산해주는 것이 쉬움
    • 빗물이 담기는 기준 : 왼쪽에서 가장 큰값과 오른쪽에서 가장큰값 중 더 작은값까지 채워짐
    • 왼쪽과 오른쪽에서 최대값을 각각 구함
    • 각 x 칸에서, 왼쪽과 오른쪽값 중 더 작은값과, 현재 값을 비교해서 현재값이 더 작으면 그 차이만큼 더함

시간복잡도 계산

  • 왼쪽, 오른쪽 모두 최대값 구하기 : O(W)
    • 모든x축에 대해서 : O(W)
    • 차이구하기
    • 총합 : O(W + W) : O(W) > 가능

자료구조

  • int maxLeft[510] : 왼쪽중 최대값
    • 최대값 500이므로 INT 가능
      • int maxRight[510] : 오른쪽 중 최대값
    • 최대값 500이므로 INT 가능
      • int map[510] : 각 칸에서의 높이
      • 총합 : int cnt
    • 최대값 : 500*500 = 250000 > 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
#include <iostream>
 
using namespace std;
 
int map[510];
int maxLeft[510];
int maxRight[510];
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int H,W; cin >> H >> W;
    int maxv = 0;
    for(int i=0; i<W; i++) {
        // 값 기록하면서 왼쪽부터 최대값 등록하기
        cin >> map[i];
        maxv = max(maxv, map[i]);
        maxLeft[i] = maxv;
    }
    
    // 오른쪽에서부터 최대값 구하기
    maxv = 0;
    for(int i=W-1; i>=0; i--) {
        maxv = max(maxv, map[i]);
        maxRight[i] = maxv;
    }
    
    int cnt=0;
//    모든 위치순회
    for(int i=0; i<W; i++) {
        int minv = min(maxLeft[i], maxRight[i]);
        if(minv > map[i]) cnt += minv - map[i];
    }
    
    cout << cnt << '\n';
    return 0;
}
 
cs

문제유형

  • 시뮬레이션 - 히스토그램
    • 이런 히스토그램 문제 나올떄, 일정 구간 * 높일를 구하면 어려워짐
    • 각각 위치에서 값을 더해주면 쉽게 할수있음

비슷한 문제

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

백준 1662 압축  (0) 2021.03.17
백준 2304 창고 다각형  (0) 2021.03.17
백준 14499 주사위 굴리기  (0) 2021.03.17
백준 1062 가르침  (0) 2021.03.17
백준 9663 N-Queen  (0) 2021.03.16

+ Recent posts

티스토리툴바