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



아이디어

  • 포함하고있는지 확인 >> 이분탐색

시간복잡도 계산

  • N개에 대해 정렬 : O(NlgN)
  • M개에 대해 이분 탐색 : O(M * lgK )
  • 합 : O(NlgN + MlgK)

인트 계산

  • 각 숫자의 최소 -1e7, 최대 1e7 > INT 가능

코드

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
#include <iostream>
#include <algorithm>
 
using namespace std;
 
int nums[500010];
 
 
void binsearch(int st, int en, int tar) {
    if(st==en) {
        if(nums[st] == tar) cout << 1 << ' ';
        else cout << 0 << ' ';
        return;
    }
    
    int mid = (st+en)/2;
    
    if(nums[mid] < tar) binsearch(mid+1, en, tar);
    else 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 >> nums[i];
    
    sort(nums, nums+N);
    
    int M; cin >> M;
    for(int i=0; i<M; i++){
        int a; cin >> a;
        binsearch(0,N-1,a);
    }
}
 
cs

문제유형

  • 이분탐색 기본

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

백준 4358 생태학 쉬운 풀이 (C++/CPP)  (0) 2021.02.28
백준 1654 랜선 자르기 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 1965 상자넣기 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 1715 카드 정렬하기  (0) 2021.02.21
백준 2023 신기한 소수 쉬운 풀이 (C++/CPP)  (0) 2021.02.21

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


문제 추상화


아이디어

  • N의 크기가 작으니까 DP로 해결
    • DP[X] = X 위치에서 한번에 넣을수 있는 상자 개수의 최대값
      • 점화식
    • DP[X] = max(if(arr[x] > arr[i]) DP[i]+1)
    • 순회 돌면서, 상자의 값이 더 클경우, DP값+1의 최대값

시간복잡도 계산

  • 각 노드에서 이전 노드 모두 돌아야함 : O(N^2) > 1e6

인트 계산

  • DP값 : 최대 1000 > INT 가능

코드

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
#include <iostream>
 
using namespace std;
 
int dp[1010];
int map[1010];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    
    int maxv = 1;
    
    int N; cin >> N;
    fill(dp, dp+N, 1);
    for(int i=0; i<N; i++) cin >> map[i];
    
    for(int j=0; j<N; j++) {
        for(int i=0; i<j; i++) {
            
            if(map[j] > map[i]) {
                dp[j] = max(dp[j], dp[i]+1);
                maxv = max(maxv, dp[j]);
            }
        }
    }
    
    cout << maxv << '\n';
    return 0;
}
 
cs

문제유형

  • DP - LIS
    • DP에서 순차적으로 오는것이 아닌, 여러 경로가 있을떄 사용
    • 특히 2차원에서 상하좌우를 모두 고려해줘야할 때

비슷한 문제

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

백준 1654 랜선 자르기 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 10815 숫자 카드 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 1715 카드 정렬하기  (0) 2021.02.21
백준 2023 신기한 소수 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 1248 맞춰봐 쉬운 풀이 (C++/CPP)  (0) 2021.02.21

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

 

아이디어

  • 두묶음씩 합칠때, 카드 개수가 많은 묶음일수록 합쳐지는 횟수가 적어야함
  • 정렬한다음, 두개씩 묶어나감
    • 이렇게하면 문제 발생
    • A,B,C,D 에서, A,B 더한값이 C,D보다 작을경우엔
    • (A + B) + (C+D) 보다, ((A+B)+C)+D 가 맞음
  • 그럼 정렬해서 앞의 두개씩만 더하자
    • pq 사용

 

시간복잡도 계산

  • 처음 정렬 : O(NlgN)
  • 앞의 두개씩 계산 : O(N * lgN)
  • 합 : O(NlgN)

 

인트 계산

  • 최대 카드 합의 값 : 1e3* 1e5 * lg(1e5) = 1e8 + 20 > 2e9, 안전하게 ll 사용

 

코드

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
#include <iostream>
#include <algorithm>
#include <queue>
 
using namespace std;
typedef long long ll;
 
 
int main() {
    int N; cin >> N;
    priority_queue<ll,vector<ll>, greater<ll>> pq;
 
    for(int i=0; i<N; i++) {
        ll a; cin >> a;
        pq.push(a);
    }
    
    
    ll rs=0;
    
    while(pq.size() != 1) {
        ll a = pq.top(); pq.pop();
        ll b = pq.top(); pq.pop();
        pq.push(a+b);
        rs+=(a+b);
    }
    
    
    cout << rs << '\n';
    
    return 0;
}
 
 cs

 

문제유형

  • 그리디 - 두개씩 합치기
    • 더할수록 이전 비용까지 합해서 발생하는 경우
    • 큰 수는 가장 마지막에 계산
    • 우선순위 큐를 사용하여 가장 앞에 두개씩 더해서 추가

 

 

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

백준 10815 숫자 카드 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 1965 상자넣기 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 2023 신기한 소수 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 1248 맞춰봐 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 2169 로봇 조종하기 쉬운 풀이 (C++/CPP)  (0) 2021.02.21

+ Recent posts

티스토리툴바