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


아이디어

  • N자리가 주어졌을때 모든자리 순회 > 1e9 > 시간초과
  • 1의자리부터 소수일경우 넘어가고 넘어가는 순으로 하면어떨까
    • 그럼 BFS로 1의자리부터 N의자리까지 숫자 넣어서 체크해보자
      • 이때 BFS이니까 중복체크 필요
      • But, 큐 사용할경우 메모리 초과
        • dfs로 해결
  • 에라토스테네스의 채 사용시 > 메모리 초과
    • 소수 확인 메소드로 사용

시간복잡도 계산

  • DFS 시복도 : O(V+E) : 1e9
  • 근데 1의 자리에서 4개밖에 없으니까 DFS 가능할듯

인트 계산

  • 최대 8자리이므로, 인트 가능

코드

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
#include <iostream>
#include <queue>
#include <string>
#include <cmath>
using namespace std;
 
bool decimalChk(int num) {
    // sqrt 까지 확인하면됨
    for(int i=2; i<=sqrt(num); i++) {
        if(num%i == 0) {
            return false;
        }
    }
    return true;
}
int N;
void dfs(int num) {
    if(to_string(num).size() == N) {
        cout << num << '\n';
        return;
    }
    
    for(int i=0; i<=9; i++) {
        string es = to_string(num) + to_string(i);
        int ei = stoi(es);
        if(decimalChk(ei) == 1) {
            dfs(ei);
        }
    }
}
 
 
int main() {
 
    cin >> N;
    
    for(int i=2; i<10; i++) {
        
        if(decimalChk(i) == 1) {
            dfs(i);
        }
    }
    
 
    return 0;
}
 
cs

문제유형

  • 그래프 탐색(BFS + DFS)

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

백준 1965 상자넣기 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 1715 카드 정렬하기  (0) 2021.02.21
백준 1248 맞춰봐 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 2169 로봇 조종하기 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 2467 용액 쉬운 풀이 (C++/CPP)  (0) 2021.02.17

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


문제 추상화

  • 숫자 갯수와, 각 구간합이 주어졌을때, 각 숫자 구하기

아이디어

  • 백트래킹으로 일일히 구하는 것이 가능할까?

    • A는 -10~10 > 21개
    • 21 ^ 10 가 일치해야함 > 너무큼
    • 다른방법이 있나?
      • 가지치기로 백트래킹 시간복잡도가 줄어들것 같긴한데...
      • 일단 해보자

시간복잡도 계산

  • 21^10

인트 계산

  • 숫자 범위 정해져있음 > 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
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
#include <iostream>
#include <string>
#include <vector>
#include <numeric>
 
using namespace std;
 
vector<int> v;
int N;
string s;
char ec[15][15];
 
bool chk() {
    int cnt=0;
    for(int j=0; j<v.size(); j++) {
        for(int i=j; i<v.size(); i++) {
//            int idx = N * j + i;
            int sumv = accumulate(v.begin()+j , v.begin()+i+1,0);
            if(ec[j][i] == '-') {
                if( sumv>=0) return false;
            }else if(ec[j][i] == '0') {
                if(sumv !=0)return false;
            } else {
                if(sumv <= 0) return false;;
            }
            cnt++;
        }
    }
    
    return true;
}
 
void dfs() {
    if(v.size() == N) {
        for(int x : v) {
            cout << x << ' ';
        }
        exit(0);
        return;
    }
    
    // 전에 합한 수에따라 값을 올려줘서 시작
    
    
    for(int i=-10; i<=10; i++) {
        v.push_back(i);
        if(chk()==1) dfs();
        v.pop_back();
    }
}
 
int main() {
    cin >> N >> s;
    int cnt=0;
    for(int j=0; j<N; j++) {
        for(int i=j; i<N; i++) {
            ec[j][i] = s[cnt++];
        }
    }
    
    dfs();
    
    
    return 0;
}
 
 
cs

문제유형

  • 백트래킹

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

백준 1715 카드 정렬하기  (0) 2021.02.21
백준 2023 신기한 소수 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 2169 로봇 조종하기 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 2467 용액 쉬운 풀이 (C++/CPP)  (0) 2021.02.17
백준 1915 가장 큰 정사각형 쉬운 풀이 (C++/CPP)  (0) 2021.02.17

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


아이디어

  • DP - DFS 방법으로, 끝에서부터 시작하여 거꾸로 시작점까지 오면 될것으로 예상

  • 그런데 왼쪽으로 이동할 수 있다는 것이 기존 문제 유형과 다른점

  • 왼쪽에서 이동할경우 무한루프가 발생할 수 있으니까, 이전 좌표를 인식하고, 해당 좌표 제외한것만 DP 하면 어떨까?

    • 이러면 무한루프 발생할 수 있음

  • DP에 각 방향을 정해서, 해당 방향에서 들어온 경우를 나눔

    • DP[y][x]에서 k 방향으로 들어온 경우, DP[y+dy[k]][x+dx[k]]방향에서는 k방향으로 들어온것 제외하고 계산
    • 마지막에 k값중 최대값을 답으로

  • 점화식

    • DP[y][x][k] = y, x 좌표에서 이전에 k방향에서 들어와서 탐사한 결과의 최대값
    • 예시 : DP[y][x][0] = DP[y+dy[k0]][x+dx[0]][0] + DP[y+dy[k0]][x+dx[0]][1]

시간복잡도 계산

  • 한 노드는 *3번
  • O(NN3) = 3e6 >> 가능

인트 계산

  • DP가 가질수 있는 최대값 : 1000 * 1000 * 100 = 1e8 >> 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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include <iostream>
 
using namespace std;
 
int map[1010][1010];
int dp[1010][1010][3];
int chk[1010][1010];
 
const int inf = -1e9;
int dy[] = {-1,0,0};
int dx[] = {0,1,-1};
int N,M;
// pre 값이라면 제외
int get_dp(int y, int x, int pre) {
    // dp가 이미 결정된 값인지 확인하는 여부 >> 초기화를 -1e9로
    if(dp[y][x][pre] != inf) return dp[y][x][pre];
    int maxv = inf;
    for(int k=0; k<3; k++) {
        if(pre == 1) if(k==2) continue;
        if(pre == 2) if(k==1) continue;
        int py = y +dy[k];
        int px = x +dx[k];
        if(py>=0 && py<N && px>=0 && px < M) {
            maxv = max(maxv, get_dp(py, px,k) + map[y][x]);
        }
         
    }
 
    return dp[y][x][pre] = maxv;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    fill(&dp[0][0][0], &dp[1009][1009][3], inf);
    fill(&chk[0][0], &chk[1009][1010], false);
    
    cin >> N >> M;
    for(int j=0; j<N; j++) {
        for(int i=0; i<M; i++) {
            cin >> map[j][i];
        }
    }
    for(int k=0; k<3; k++) {
        dp[0][0][k] = map[0][0];
    }
    
    
    cout << max(max(get_dp(N-1,M-1,0), get_dp(N-1,M-1,1)), get_dp(N-1,M-1,2)) << '\n';
    
    
    return 0;
}
 
cs

문제유형

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

백준 2023 신기한 소수 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 1248 맞춰봐 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 2467 용액 쉬운 풀이 (C++/CPP)  (0) 2021.02.17
백준 1915 가장 큰 정사각형 쉬운 풀이 (C++/CPP)  (0) 2021.02.17
백준 1339 단어수학 쉬운 풀이 (C++/CPP)  (0) 2021.02.16

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


아이디어

  • 각 숫자를 순회하면서 0에 가까운 수를 찾으면
    • O(N^2) = 1e10 > 시간초과
  • 한 숫자를 정하고 나머지 숫자에 대해서 반대값을 이진탐색
    • O(N * lgN)
  • lower ? upper ?
    • lower로 찾고, 만약 0보다 클경우, 하나 인덱스 뺀것도 같이 계산해주자
  • 이진탐색 범위
    • 오름차순이기 때문에, 자기 자신의 다음위치만 찾으면 됨
    • 자기자신 이전에 있을 경우는 어짜피 쌍으로되기때문에 이전에서 찾아줌

시간복잡도 계산

  • 모든 숫자에 대해서 : O(N)
  • 이진탐색 진행 : O(lgN)
  • 시간복잡도 : O(N*lgN) : 1e5 * 20 = 2e6

인트 계산

  • 최소값 2개 더할경우 : -2e9
  • 최대값 2개 더할경우 : 2e9
  • 인트 사용 가능

코드

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
#include <iostream>
#include <vector>
 
using namespace std;
 
vector<int> nums;
 
int binsearch(int st, int en, int tar) {
    if(st==en) return st;
    
    int mid = (st+en)/2;
    if(nums[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++) {
        int a; cin >> a;
        nums.push_back(a);
    }
    
    int minv =2e9+10;
    int fn = -1;
    int sn = -1;
    
    // 모든 숫자에 대해서, 마지막은 빼주기
    for(int i=0; i<N-1; i++) {
        int eachNum = nums[i];
        
        // eachNum에 반대되는값을 이진탐색
        int target = eachNum * -1;
        int idx = binsearch(i+1,nums.size()-1, target);
        
        // idx 이전값이랑 비교할때, 같은 값이 아닌지 주의
        if(idx >0 && idx-1 != i) {
            if( abs(nums[idx] + eachNum) > abs(nums[idx-1] + eachNum)) idx = idx-1;
        }
        
        if(minv > abs(nums[idx] + eachNum)) {
            minv =abs(nums[idx] + eachNum);
            fn = eachNum;
            sn = nums[idx];
        }
        
    }
    
    if(fn > sn) cout << sn << ' ' << fn << '\n';
    else cout << fn << ' ' << sn << '\n';
    
    
    
    return 0;
}
 
cs

문제유형

  • 이진탐색 - 리스트 내의 값으로 이진탐색
    • 리스트 안에 있는 값중 하나로, 자기와 반대되는 값을 탐색
    • 자기 자신부터 끝까지 이진탐색 수행
    • 마지막 원소는 이진탐색 해주지 않음
    • 쌍을 찾는것이기 때문에 마지막 원소는 찾지 않아도됨

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

백준 1248 맞춰봐 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 2169 로봇 조종하기 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 1915 가장 큰 정사각형 쉬운 풀이 (C++/CPP)  (0) 2021.02.17
백준 1339 단어수학 쉬운 풀이 (C++/CPP)  (0) 2021.02.16
백준 1107 리모컨  (1) 2021.02.16

아이디어

  • 그래프 순회하면서 대각선만 DFS로 가면 안될까?
    • 노드 개수 : O(N^2)
    • 각 노드에서 순회해야할 갯수, 대각선만 보면 됨, O(N)
    • O(N^3) = 1e9 > 시간초과
  • 이전에 구한 정사각형을 다음에 활용 가능? > DP 사용
    • DP[j][i] = j, i칸에서 가장 큰 정사각형의 크기
    • 해당 노드가 0일경우 넘어감
    • 해당 노드가 1일경우, 왼쪽, 왼쪽위 대각선, 위쪽 중 가장 작은값에 1 더한 값으로 갱신

시간복잡도 계산

  • O(N^2) 순회
  • 각 노드에서 3개 지점만 확인
    • 시간복잡도 : O(3*N^2) = 3e6

인트 계산

  • 정사각형 크기 : 최대 1e6 > 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 <string>
 
using namespace std;
 
int dp[1010][1010];
int map[1010][1010];
int main() {
    //dp 초기화
    fill(&dp[0][0], &dp[1009][1010], 0);
    
    int N,M; cin >> N >> M;
    for(int j=0; j<N; j++) {
        string s; cin >> s;
        for(int i=0; i<M; i++) {
            map[j][i] = s[i]-'0';
        }
    }
    
    int maxv = 0;
    for(int j=0; j<N; j++) {
        for(int i=0; i<M; i++) {
            if(j==0 || i==0) dp[j][i] = map[j][i];
            else if(map[j][i] == 1){
                // 3방향중 가장 작은 값에다 1더한값으로 갱신
                dp[j][i] = min(min(dp[j-1][i], dp[j-1][i-1]), dp[j][i-1]) + 1;
            }
            maxv = max(maxv, dp[j][i]);
        }
    }
    
    cout << maxv*maxv << '\n';
    return 0;
}
 
cs

문제유형

  • DP - 2차원 배열
    • 단순히 모양이 2차원일뿐, 1차원 DP와 같이 앞의 값을 활용해 풀면 됨

비슷한 문제

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

백준 2169 로봇 조종하기 쉬운 풀이 (C++/CPP)  (0) 2021.02.21
백준 2467 용액 쉬운 풀이 (C++/CPP)  (0) 2021.02.17
백준 1339 단어수학 쉬운 풀이 (C++/CPP)  (0) 2021.02.16
백준 1107 리모컨  (1) 2021.02.16
백준 2143 두 배열의 합 쉬운 풀이(C++/CPP)  (0) 2021.02.15

문제 추상화

  • 알파벳에 숫자를 대입해서 최대의 수를 찾는문제
  • 앞자리일수록 큰게 좋음 >> 그리디 - 숫자

아이디어

  • 모든 숫자를 알파벳에 대입해서 최대값을 찾는 경우
    • 시간복잡도가 관건
    • 시간복잡도 : 알파뱃 최대 갯수 ^ 알파벳 최대갯수 > 10^10 > 시간초과
  • 앞자리일수록 큰 숫자로
    • 만약 두개의 단어가 길이가 같은데 첫자리가 다른경우?
    • 뒤에 더 앞자리가 들어오는 알파벳에 큰 숫자를 넣어야함
    • 각 알파벳이 들어간 위치를 계산하여 점수를 매기는 수밖에없음
  • 단어의 길이를 먼저 구함
  • 단어의 위치에서 알파벳의 평가점수를 넣어줌
  • 평가점수가 높은 순으로 높은 숫자를 넣음
  • 단어의 합을 구함

시간복잡도 계산

  • 모든 단어에 대해서 : O(N)
  • 단어의 길이를 먼저 구함 : O(1)
  • 단어의 위치에서 알파벳의 평가점수를 넣어줌 : O(10)
  • 평가점수가 높은 순으로 높은 숫자를 넣음
  • 단어의 합을 구함 : O(N)
  • 시간복잡도 : O(N*10 + N) : O(10N) = 100

인트 계산

  • 단어의 합 최대값 : 10 * 9999999999 = 1e11 >> long long 사용
  • 알파벳의 평가점수 : 평가점수 최대값 : 10 * 1e10 >> long long 사용

코드

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>
#include <string>
#include <cmath>
#include <algorithm>
 
using namespace std;
 
int alpha[26];
 
int main() {
    int N; cin >> N;
    
    fill(alpha, alpha+26, 0);
    
    for(int i=0; i<N; i++) {
        string s; cin >> s;
        for(int i=0; i<s.size(); i++) {
            // 알파벳 숫자로 변환
            int ec = s[i] - 'A';
            // 알파벳 평가점수
            alpha[ec] += pow(10,s.size()-1-i);
        }
    }
    
    sort(alpha, alpha+26, greater<int>());
    
    int rs=0;
    int tmp = 10;
    
    for(int i=0; i<10; i++) {
        tmp--;
        rs += alpha[i] * tmp;
    }
    
    cout << rs << '\n';
    
    return 0;
}
 
cs

문제유형

  • 그리디 - 숫자관련 최소 최대
    • 최대 : 앞자리일수록 큰 수 사용, 최소는 그 반대
    • 엣지값 -1,0,1 조심

비슷한 문제

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

백준 2467 용액 쉬운 풀이 (C++/CPP)  (0) 2021.02.17
백준 1915 가장 큰 정사각형 쉬운 풀이 (C++/CPP)  (0) 2021.02.17
백준 1107 리모컨  (1) 2021.02.16
백준 2143 두 배열의 합 쉬운 풀이(C++/CPP)  (0) 2021.02.15
백준 2565 전깃줄 쉬운 풀이(C++/CPP)  (0) 2021.02.15

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

아이디어

  • BFS로 채널을 누르고, 위아래로 누를때 원하는 채널로 이동하는 최소의 값
  • 버튼 누르는건 어떻게?
    • 1~6번째만, 해당 자리수의 숫자 큐에 넣음
    • 에시 : 2번쨰 누르는 경우엔, 10~99까지
    • 고장난 버튼 : 각 자리에서 고장난 버튼 확인
      • 이떄 BFS이므로 중복체크 해주기

시간복잡도 계산

  • 큐에 최대 들어갈수 있는수(노드) : 5e5
  • 큐에 들어가는 노드에서, 고장난 버튼 확인 : 10
  • 최대 움직일수 있는 수(간선) : 5e5
  • BFS 시간복잡도 : O(V*10+E) : 5e6 + 5e5 = 5.5e6

인트 계산

  • 누르는 횟수 : 최대 5e5

코드

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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <queue>
#include <vector>
#include <cmath>
#include <algorithm>
 
using namespace std;
 
vector<int> f;
bool chk[1000010];
//bool chk[10000];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int target; cin >> target;
    
    // 중복체크 초기화
//    fill(chk, chk+500010, false);
    
    int M; cin >> M;
    for(int i=0; i<M; i++) {
        int a; cin >> a; f.push_back(a);
    }
    
    queue<int> q;
    q.push(100);
    chk[100] = 1;
    int cnt=0;
    while(!q.empty()) {
        int qsize = q.size();
        while(qsize--) {
            int eq = q.front(); q.pop();
            
            if(eq == target) {
                cout << cnt << '\n';
                return 0;
            }
            
            // 더하고
            if(eq+1 <=500000) {
                if(chk[eq+1] == false) {
                    chk[eq+1] = 1;
                    q.push(eq+1);
                }
            }
            
            // 빼기
            if(eq-1 >=0) {
                if(chk[eq-1] == false) {
                    chk[eq-1] = 1;
                    q.push(eq-1);
                }
            }
            
            
            
        }
        
        if(cnt<6) {
            int st = pow(10,cnt);
            if(st==1) st = 0;
            int en = pow(10,cnt+1)-1;
            
            for(int i=st; i<=en; i++) {
                if(chk[i]) continue;
                bool sw = false;
                // 각 자리수에서 금지된 숫자 있는지 확인
                for(int j=0; j<=cnt; j++) {
                    // 각자리숫자
                    int num = (int)(i/pow(10,j)) % 10;
                    if(find(f.begin(), f.end(), num) != f.end()) {
                        sw = true;
                        break;
                    }
                    
                }
                
                // 금지된 숫자에 걸리는 것이 없다면 큐에 넣기
                if(sw == false){
                    chk[i] = 1;
                    q.push(i);
                }
            }
        }
        
        cnt++;
    }
    
    return 0;
}
 
cs

문제유형

  • BFS - 최소 횟수

비슷한 문제

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

백준 1915 가장 큰 정사각형 쉬운 풀이 (C++/CPP)  (0) 2021.02.17
백준 1339 단어수학 쉬운 풀이 (C++/CPP)  (0) 2021.02.16
백준 2143 두 배열의 합 쉬운 풀이(C++/CPP)  (0) 2021.02.15
백준 2565 전깃줄 쉬운 풀이(C++/CPP)  (0) 2021.02.15
백준 1946 신입 사원  (0) 2021.02.15

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


아이디어

  • A,B의 각각 부배열을 구하는 방법
    • 애초에 들어올떄 해당 인덱스까지의 합을 받아옴
    • 각 인덱스 순회하면서 모든 경우의 수를 구함
    • O(N^2)
  • A,B 각각 더해서 값을 구할경우 : O(N^2 * N^2) = O(N^4) = 1e12 > 시간초과
  • A의 값을 고정한다음에, 더해서 0이되는 값을 B에서 이진탐색으로 찾음
  • B 배열에서 같은 값이 여러개일경우에??
    • 이진탐색을 lower bound, upper bound 같이 수행해서 차이만큼 빼기

시간복잡도 계산

  • B 정렬 : N^2lgN^2
  • A순회하면서 이진탐색 :N^2 lgN^2
  • O( N^2lgN^2 + N^2lgN^2) = O( N^2lgN^2) = 1e6 * lg(1e6) = 1e6 * 20 = 2e7

인트 계산

  • 더해서 최악의 캐이스 : N * 1e6 * 2 = 1e3 * 1e6 * 2 = 2e9 > INT 가능
    • 결과값 : 1e6개 * 1e6개 = 1e12개 >> 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
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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
#include <iostream>
#include <algorithm>
 
using namespace std;
typedef long long ll;
 
int sumA[1010];
int sumB[1010];
int partA[1000010];
int partB[1000010];
 
int binsearchlower(int st, int en, int target) {
    if(st==en) {
        if(partB[st] == target) return st;
        return -1;
    }
 
    int mid = (st+en)/2;
    if(partB[mid] < target) return binsearchlower(mid+1, en, target);
    else return binsearchlower(st, mid, target);
}
 
int binsearchupper(int st, int en, int target) {
    if(st==en) {
        if(partB[st] == target) return st;
        return -1;
    }
 
    int mid = (st+en+1)/2;
    if(partB[mid] <= target) return binsearchupper(mid, en, target);
    else return binsearchupper(st, mid-1, target);
}
 
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    int T; cin >> T;
    int N; cin >> N;
    cin >> sumA[0];
    partA[0] = sumA[0];
    for(int i=1; i<N; i++) {
        cin >> sumA[i];
        // 이전값이랑 합함
        sumA[i] += sumA[i-1];
    }
 
    int cntA=0;
    for(int j=0; j<N; j++) {
        partA[cntA] = sumA[j];
        cntA++;
        for(int i=0; i<j; i++) {
            partA[cntA] = sumA[j] - sumA[i];
            cntA++;
        }
    }
 
 
    int M; cin >> M;
    cin >> sumB[0];
    partB[0] = sumA[0];
    for(int i=1; i<M; i++) {
        cin >> sumB[i];
        // 이전값이랑 합함
        sumB[i] += sumB[i-1];
    }
 
    int cntB=0;
    for(int j=0; j<M; j++) {
        partB[cntB] = sumB[j];
        cntB++;
        for(int i=0; i<j; i++) {
            partB[cntB] = sumB[j] - sumB[i];
            cntB++;
        }
    }
 
    sort(partB, partB+cntB);
 
    ll rs=0;
    for(int i=0; i<cntA; i++) {
        int tar = T - partA[i];
        // 같은 값을 나오는걸 어떻게 할까 >> lower, upper 둘다 구해서 인덱스 더하자
        int st = binsearchlower(0,cntB-1,tar);
        if(st != -1) {
            int en =binsearchupper(0,cntB-1,tar);
            rs += (en-st+1);
        }
    }
 
    cout << rs << '\n';
    
    return 0;
 
}
 
 
 
cs

문제유형

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

비슷한 문제

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

백준 1339 단어수학 쉬운 풀이 (C++/CPP)  (0) 2021.02.16
백준 1107 리모컨  (1) 2021.02.16
백준 2565 전깃줄 쉬운 풀이(C++/CPP)  (0) 2021.02.15
백준 1946 신입 사원  (0) 2021.02.15
백준 1937 욕심쟁이 판다 풀이(C++/CPP)  (0) 2021.02.14

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


문제 추상화

  • DP로 LCS를 구하는 문제
  • LCS인 이유
    • 전깃줄이 교차하지 않아야함
    • A이나 B중 하나를 정렬하면
    • 전깃줄이 교차하지 않으면 나머지 것이 순차적으로 증가와 같음

아이디어

  • DP로 LCS 풀기
    • DP[i] = i번째 위치에서 LCS 개수
    • 처음에 DP[i]를 1로 초기화
    • DP[i] = for(j=0~i-1) if(num[i] > num[j]) DP[i] = max(Dp[i], DP[j]+1)

시간복잡도 계산

  • O(N^2) : 1e4
  • 만약 숫자 클경우 이진탐색을 통해서 풀경우 O(NlgN)으로 가능

인트 계산

  • 전깃출 최대 100
  • 위치 최대 500
  • 모두 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
#include <iostream>
#include <algorithm>
 
using namespace std;
 
pair<int, int> nums[110];
int dp[110];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    fill(dp, dp+110, 1);
    int N; cin >> N;
    for(int i=0; i<N; i++) {
        int a,b; cin >> a >> b;
        nums[i] = make_pair(a,b);
    }
    
    sort(nums, nums+N);
    int maxv= 1;
    for(int i=1; i<N; i++) {
        for(int j=0; j<i; j++) {
            if(nums[i].second > nums[j].second) {
                dp[i] = max(dp[i], dp[j]+1);
            }
        }
        maxv = max(maxv, dp[i]);
    }
    
    cout << N-maxv << '\n';
    
    return 0;
}
 
cs

문제유형

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

비슷한 문제

  • DP - LCS

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

백준 1107 리모컨  (1) 2021.02.16
백준 2143 두 배열의 합 쉬운 풀이(C++/CPP)  (0) 2021.02.15
백준 1946 신입 사원  (0) 2021.02.15
백준 1937 욕심쟁이 판다 풀이(C++/CPP)  (0) 2021.02.14
백준 10999 구간 합 구하기2 쉬운 풀이(C++/CPP)  (0) 2021.02.14

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

 

문제 접근

  • 문제를 추상화 하면
    • A와 B 과목에서 하나라도 다른 사람에 비해 떨어지면 안됨
  • 모두 떨어지는 경우를 구하는게 쉬울듯
  • 접근 1 : 각 노드당 모든 노드를 순회하면서 모두 떨어지는 경우를 구할경우
    • O(N^2) > e10 시간초과
  • 접근 2 : 하나를 기준으로 나머지 값의 최소값을 갱신
    • A,B 과목이 있을때 A 과목을 기준으로 정렬
    • A과목의 순위가 가장 높은 지원자의 B과목 순위를 최소값의 초기 셋팅
    • A과목 순위가 낮은 것들을 순회
      • A 과목 순위가 낮기 때문에, B과목은 더 순위가 높아야함
      • B과목의 순위를 최소값으로 갱신하면서 순회

 

시간복잡도 계산

  • 테스트케이스 : T
  • A과목을 기준으로 정렬 : NlgN
  • 모든 지원자 순회 : N
  • 시간복잡도 : O(T * (NlgN + N)) = O(TNlgN) =20* 1e5 * 20 = 4e7

인트 계산

  • 면접 지원자숫자 최대 1e6 > 인트 가능

 

코드

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>
#include <algorithm>
 
using namespace std;
 
pair<int, int> people[100010];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int T;cin >> T;
    while(T--) {
        int N; cin >> N;
        for(int i=0; i<N; i++) {
            int a,b; cin >> a >> b;
            people[i] = make_pair(a,b);
        }
        
        sort(people, people+N);
        
        int minv= people[0].second;
        int cnt=0;
        for(int i=1; i<N; i++) {
            // A과목 순위가 높은 사람의 B과목 순위도 순위가 높다면 카운트
            if(minv < people[i].second) {
                cnt++;
            }
            // 최소 순위 갱신, 왜냐하면 다음 사람은 최대값과 비교
            minv = min(minv, people[i].second);
        }
        
        cout << N-cnt << '\n';
    }
    return 0;
}
 
 cs

 

문제유형

  • 그리디 - 두과목 모두 낮은 경우
    • A 과목을 기준으로 정렬한 후
    • A가 가장 높은 사람의 B 점수를 기록
    • A 과목을 순회하면서 B점수를 보다 높은값으로 갱신하며
    • 두과목 모두 낮은 경우 조회

 

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

백준 2143 두 배열의 합 쉬운 풀이(C++/CPP)  (0) 2021.02.15
백준 2565 전깃줄 쉬운 풀이(C++/CPP)  (0) 2021.02.15
백준 1937 욕심쟁이 판다 풀이(C++/CPP)  (0) 2021.02.14
백준 10999 구간 합 구하기2 쉬운 풀이(C++/CPP)  (0) 2021.02.14
백준 2042 구간 합 구하기 쉬운 풀이(C++/CPP)  (0) 2021.02.14

+ Recent posts

티스토리툴바