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


아이디어

  • BFS를 사용해서 최소 시간을 구하자

    • 각 숫자에 대해 각각 연산한 뒤 값이 맞으면 출력
    • 값이 다르면 큐에 넣고 계속 수행
    • 이때 연산한 값을 가지고 있기 위해서, q에 과거 수행한 연산도 같이 등록

  • 주의해야할 것

    • L과 R 연산에서 4자리를 맞추기 위해 0을 채운 뒤 연산 수행
    • 그리고 반환할때는 앞의 0을 없애기

시간복잡도 계산

  • BFS연산 최대 1e4번
  • D, S 연산 : O(1)
  • L, R 연산 : O(1)

인트 계산

  • q<pair<int, string>> : 숫차 최대값이 1e4로 정해져 있어서 괜찮음

코드(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
#include <iostream>
#include <queue>
#include <string>
 
using namespace std;
 
 
bool chk[10010];
int main() {
 
    int T; cin >> T;
    while(T--) {
        // 메모리 초기화
        fill(chk, chk+10010, 0);
        
        int N,M; cin >> N >> M;
        queue<pair<int, string>> q;
        q.push(make_pair(N, ""));
        chk[N] = 1;
        while(!q.empty()) {
            auto eq = q.front(); q.pop();
            int en = eq.first;
            string cal = eq.second;
            
            // 비교
            if(en == M) {
                cout << cal << '\n';
                break;
            }
            
            int calD =en*2%10000;
            if(chk[calD] == 0) {
                q.push(make_pair(calD, cal+"D"));
                chk[calD] = 1;
            }
            
            int calS = en-1;
            if(calS == -1) calS = 9999;
            if(chk[calS] == 0) {
                q.push(make_pair(calS, cal+"S"));
                chk[calS] = 1;
            }
            
            int cl = en%1000 * 10 + en/1000;
            if(chk[cl] == 0) {
                q.push(make_pair(cl, cal+"L"));
                chk[cl] = 1;
            }
            
            int cr = en%10 * 1000 + en/10;
            if(chk[cr] == 0) {
                q.push(make_pair(cr, cal+"R"));
                chk[cr] = 1;
            }
        }
    }
    
    return 0;
}
 
cs

문제유형

  • BFS - 최소 거리 구하기

비슷한 문제

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

백준 1926 그림  (0) 2021.03.14
백준 1038 감소하는 수  (0) 2021.03.14
백준 1747 소수&팰린드롬  (0) 2021.03.13
백준 2638 치즈  (0) 2021.03.13
백준 11066 파일 합치기  (0) 2021.03.09

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


아이디어

  • 큰수에 대해 각각 소수인지, 팰린드롬인지 확인해보자
  • 예외의 수 1을 조심!!

시간복잡도 계산

  • 큰 수에 대해서 : O(N)
  • 소수인지 확인 : O(sqrt(N))
  • 팰린드롬인지 확인 : O(lg(N))
  • 총합 : O(NlgN * sqrt(N))
    • 시간 초과될것 같지만
    • 더 팰린드롬인지 확인을 먼저할경우
    • 시간복잡도를 줄일수 있음

인트 계산

  • 큰 수가 어느수까지 가는지 예상하기가 어려우니 가장 큰 수(1000000)를 입력해보고 가능한지 확인해보자

코드(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
#include <iostream>
#include <string>
#include <cmath>
#include <climits>
 
using namespace std;
 
bool chk_pelin(int N) {
    string s = to_string(N);
    string subs = s.substr(0,(s.size()+1)/2);
    
    
    for(int i=0; i<subs.size(); i++){
        if(subs[i] != s[s.size()-1-i]) return 0;
    }
    return 1;
}
 
bool chk_prime(int N) {
    if(N==1) return 0;
    
    for(int i=2; i<=sqrt(N); i++) {
        if(N%i == 0) return 0;
    }
    return 1;
}
int main() {
    int N; cin >> N;
    
    for(int i=N; i<INT_MAX; i++) {
        if(chk_pelin(i)) {
            if(chk_prime(i)) {
                cout << i << '\n';
                return 0;
            }
        }
    }
    return 0;
    
}
 
cs

문제유형

  • 문자열 - 팰린드롬
    • 팰린드롬 : 앞에서 읽으나 뒤에서 읽으나 같은 단어
    • 문자열 반 자른뒤 앞과 뒤가 같은지 확인 : O(N)
    • 문자열 하나에 대해 범위를 다르게 해서 팰린드롬을 확인해야하는 경우 DP 사용
      • DP[st][en] : st부터 시작해서 en까지 끝날때 팰린드롬 true, false
      • DP[st][en] = true일때, 각각 앞뒤 문자열이 같을경우 팰린드롬
      • 문자길이 1,2, 3이상일때 각각 나눠서 수행

비슷한 문제

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

백준 1038 감소하는 수  (0) 2021.03.14
백준 9019 DSLR  (0) 2021.03.13
백준 2638 치즈  (0) 2021.03.13
백준 11066 파일 합치기  (0) 2021.03.09
백준 10775 공항  (0) 2021.03.09

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


아이디어

  • 모든 노드 돌면서 주변에 2변 이상 외부 공기에 접촉되어있는지 확인

    • 이럴경우, 안쪽에 있는 공기도 외부공기로 간주되게 됨

  • 바깥 공기에 접촉하는지를 확인

    • 0,0부터 bfs 사용해서 이어져있는 공기 먼저 색칠하기
    • 단 계속 확대될 것이기 때문에 원래대로 색칠 안해줘도됨

  • 접촉되어있을경우 리스트에 넣었다가 한번에 지우기

  • 모두 없어질때까지 반복


시간복잡도 계산

  • Flood-fill로 외부공기 확인 : O(NM) = O(N^2)
  • 모든 노드 순회 : O(NM) = O(N^2)
  • 반복하는 최대상황 : O(N)
    • 가장자리 제외하고 모두 치즈가 꽉찬경우
  • 총합 : O((N^2 * N^2) * N) = O(N^3) : 1e6 가능

인트 계산

  • 치즈 위치 map : 0,1
  • 2변이상 노출시 넣을 벡터 : pair<int, int>
  • 없어지는데 걸리는 최대 횟수 : 100

코드(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
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int map[110][110];
bool chk[110][110];
int dy[] = {0,1,0,-1};
int dx[] = {1,0,-1,0};
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N,M; cin >> N >> M;
    
    // map 먼저 세팅
    for(int j=0; j<N; j++) {
        for(int i=0; i<M; i++) {
            cin >> map[j][i];
        }
    }
    
    // 없어질 치즈
    vector<pair<int, int>> v;
    int t=0;
    while(1) {
        v.clear();
        
        // 바깥 공기 먼저 설정
        fill(&chk[0][0], &chk[109][110], 0);
        queue<pair<int, int>> q;
        q.push(make_pair(0,0));
        chk[0][0] = 1;
        
        
        while(!q.empty()) {
            auto eq = q.front(); q.pop();
            int ey = eq.first;
            int ex = eq.second;
            map[ey][ex] = 2;
            
            for(int k=0; k<4; k++) {
                int ny = ey + dy[k];
                int nx = ex + dx[k];
                if(ny>=0 && ny<N && nx>=0 && nx< M) {
                    if(chk[ny][nx] == 0 && (map[ny][nx] == 0 || map[ny][nx] == 2)) {
                        chk[ny][nx] = 1;
                        q.push(make_pair(ny, nx));
                    }
                }
            }
        }
        
        // 모든 노드 순회하면서 없어질 치즈 확인
        for(int j=0; j<N; j++) {
            for(int i=0; i<M; i++) {
                if(map[j][i] == 1) {
                    int cnt=0;
                    for(int k=0; k<4; k++) {
                        int ny = j + dy[k];
                        int nx = i + dx[k];
                        if(ny>=0 && ny<N && nx>=0 && nx < M) {
                            if(map[ny][nx] == 2) cnt++;
                        }
                    }
                    if(cnt>=2) v.push_back(make_pair(j,i));
                }
            }
        }
        
        // 없앨 치즈 없을경우 종료
        if(v.empty()) break;
        
        // 치즈 없애기
        for(auto x : v) {
            int ej = x.first;
            int ei = x.second;
            map[ej][ei] = 0;
        }
        
        t++;
    }
    
    cout << t << '\n';
    
    return 0;
}
 
cs

문제유형

  • BFS - Flood Fill
    • 이어져있는 노드를 연결하는 문제
    • BFS 사용해서, 이어져 있는 노드 확인

비슷한 문제

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

백준 9019 DSLR  (0) 2021.03.13
백준 1747 소수&팰린드롬  (0) 2021.03.13
백준 11066 파일 합치기  (0) 2021.03.09
백준 10775 공항  (0) 2021.03.09
백준 2820 자동차 공장 쉬운 풀이 (C++/CPP)  (0) 2021.03.05

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


문제 추상화

  • 연속해있는 값들을 두개씩 합칠 때마다 각 값을 더한 비용이 생긴다
  • 모든 값을 하나로 합칠때, 최소의 비용을 구하기

아이디어

  • 모든 경우의 수를 확인 가능?
    • 경우의 수 : 각 위치에서 앞의 것과 합칠떄, 그리고 합치지 않을때를 각각 계산
    • 그럼 중간에 하나씩 떨어져 있는 것을 계산이 불가
  • DP 사용
    • 개념이 복잡해서 헷갈릴수 있는데 천천히 읽어보자.
    • DP[x][y] : x부터 y까지 더할때 최소값
    • DP[x][y] = min(DP[x][z] + DP[z+1][y]) + sum(x~y)
    • 3중 루프를 돌아야하는데
      • y-x 값 기준
      • 시작값 x
      • 중간에 끊는 z값을 기준
    • 즉, 3중루프가 다음처럼 구현됨
      • 일단, dp[1][2], dp[2][3], dp[3][4] ... 구하고
      • dp[1][3] = dp[1][2] + dp[2][3], dp[2][4] = dp[2][3] + dp[3][4], ...
      • dp[1][4] = min(dp[1][2] + dp[2][4], dp[1][3] + dp[3][4]) ...
        • 이걸 시험 중 생각해낼 수 있을까? > 불가능
    • 문제 유형을 외우자

시간복잡도 계산

  • O(T * K^3) : T * 1.25e8

인트 계산

  • DP 최대값 : 모든 숫자가 K번 더해질경우 : 10000 * 500 * 500 = 25e8 > INT 불가, LL 사용

코드(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
#include <iostream>
 
using namespace std;
typedef long long ll;
 
const ll inf  = 2.6e9;
ll dp[510][510];
int sum[510];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int t; cin >> t;
    while(t--) {
        fill(&dp[0][0], &dp[509][510], 0);
        fill(sum, sum+510, 0);
        
        int K; cin >> K;
        
        // 합을 추후 계산해야해서 미리 구함
        for(int i=1; i<=K; i++) {
            int ei; cin >> ei;
            sum[i] = sum[i-1] + ei;
        }
        
        for(int d=1; d<K; d++) {
            for(int st=1; st+d<=K; st++) {
                int en = st+d;
                
                // 초기값 무한대로 설정
                dp[st][en] = inf;
                for(int mid = st; mid<en; mid++) {
                    dp[st][en] = min(dp[st][en], dp[st][mid] + dp[mid+1][en] + sum[en]-sum[st-1]);
                }
                
            }
        }
        
        cout << dp[1][K] << '\n';
        
    }
    return 0;
}
 
cs

문제유형

  • DP - 연속한 값끼리 더해서 최소값구하기
    • 일반적 DP 사용할 경우, 중간에 홀로 떨어지는 값 발생
    • DP[st][en] : st부터 en까지의 최소값
    • DP[st][en] = min(DP[x][z] + DP[z+1][en]) + sum(st~en)
    • 3중루프가 다음처럼 구현됨
      • 일단, dp[1][2], dp[2][3], dp[3][4] ... 구하고
      • dp[1][3] = dp[1][2] + dp[2][3], dp[2][4] = dp[2][3] + dp[3][4], …
      • dp[1][4] = min(dp[1][2] + dp[2][4], dp[1][3] + dp[3][4]) ..

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

백준 1747 소수&팰린드롬  (0) 2021.03.13
백준 2638 치즈  (0) 2021.03.13
백준 10775 공항  (0) 2021.03.09
백준 2820 자동차 공장 쉬운 풀이 (C++/CPP)  (0) 2021.03.05
백준 6549 히스토그램에서 가장 큰 직사각형 쉬운 풀이 (C++/CPP)  (0) 2021.03.04

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


문제 추상화

  • 문제가 잘 이해가 안되서 한참을 해석했다.
    • 각 비행기가 1~gi에 도킹
    • 이때 최대한 도킹할 수 있는 개수 구하기

아이디어

  • 모든 경우 탐색
    • 각 비행기를 모든 게이트에 주차할 수 있는지 확인
    • 모든 게이트(G) * 비행기수(P) : G*P = 1e10 > 시간초과
      • 각 게이트가 빈 게이트를 바라보도록 함
    • union-find
    • p 배열 : 각 게이트보다 작은 게이트 중 비어있는 값
    • p 배열의 0을 지시 : 더이상 주차할 게이트가 없음 >> 종료

시간복잡도 계산

  • 모든 비행기에서 : O(G) = 1e5
  • 게이트를 확인 : O(1)
  • 게이트에 비행기 넣은후 이전 비어있는 게이트를 재확인 : O(1)

인트 계산

  • p : 게이트 최대 값 : 1e5 > 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
#include <iostream>
 
using namespace std;
 
int p[100010];
int find(int v) {
    if(p[v] == v) return p[v];
    return p[v] = find(p[v]);
}
 
void merge(int v1, int v2) {
    v1 = find(v1);
    v2 = find(v2);
    p[v1] = v2;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int G,P; cin >> G >> P;
    int cnt=0;
    // 부모 배열 초기 셋팅
    for(int i=1; i<=G; i++) {
        p[i] = i;
    }
    
    for(int i=0; i<P; i++) {
        int gate; cin >> gate;
        
        // 게이트 비어있는 곳이 없을경우
        int parentGate = find(gate);
        if(parentGate == 0) {
            break;
        }
        
        // 비어있는 게이트가 있을 경우
        cnt++;
        merge(parentGate, parentGate-1);
        
    }
    
    cout << cnt << '\n';
    
    
    
    return 0;
}
 
cs

문제유형

  • Union Find - 앞의 노드 중 비어있는 값 확인
    • 부모노드를 찾은 다음
    • 부모노드가 빈값이 없으면 종료
    • 빈값이 있을경우, 부모노드와 부모노드 이전값이랑 merge 수행

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

백준 2638 치즈  (0) 2021.03.13
백준 11066 파일 합치기  (0) 2021.03.09
백준 2820 자동차 공장 쉬운 풀이 (C++/CPP)  (0) 2021.03.05
백준 6549 히스토그램에서 가장 큰 직사각형 쉬운 풀이 (C++/CPP)  (0) 2021.03.04
백준 1865 웜홀 쉬운 풀이 (C++/CPP)  (0) 2021.03.04

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


아이디어

  • 상사와의 관계를 인접 행렬로 관리

    • 업데이트 할경우 인접행렬을 업데이트
    • 시간복잡도 : O(M * N) : 2.5e11 > 시간초과

  • 레이지 개념 사용할 수 있을까?

    • a의 부하의 월급을 증가할떄 : a에 임시로 달아놓음
    • u로 출력할때 : 상사에서부터 lazy 업데이트 후 출력
    • 시간복잡도 : 편향트리일때 O(MN) > 시간초과

  • 자식 관계를 세그먼트 트리에 입력

    • 트리가 편향되어있을때 O(NM)을 세그먼트에 넣어 O(NlgM)으로 만듬
    • 세그먼트에 넣도록 노드를 배열에 각각 넣음
    • l 배열 : 자기자신 인덱스, 다음값부터 자식 인덱스
    • r 배열 : 자식 마지막 인덱스
    • 업데이트 시 l+1 부터 r까지 업데이트

시간복잡도 계산

  • 세그먼트 트리 생성 : O(NlgN)
  • 출력 : O(MlgN)

인트 계산

  • 트리 : 항상 2^31-1 이하이지만 중간에 넘칠 수 있으므로 > ll 사용
  • lazy :중간에 넘칠수 있으므로 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
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <iostream>
#include <vector>
#include <cmath>
 
using namespace std;
typedef long long ll;
 
vector<ll> tree;
vector<ll> lazy;
 
int initSalary[500010];
int l[500010];
int r[500010];
int segToOrigin[500010];
vector<int> child[500010];
 
void dfs(int cur, int &idx) {
    l[cur] = ++idx;
    for(int x : child[cur]) dfs(x, idx);
    r[cur] = idx;
}
 
void make(int node, int st, int en) {
    if(st== en) {
        tree[node] = initSalary[segToOrigin[st]];
        return;
    }
    
    int mid = (st+en)/2;
    make(node*2, st, mid);
    make(node*2+1, mid+1, en);
}
 
void lazy_update(int node, int st, int en) {
    if(lazy[node] != 0) {
        if(st == en) tree[node] += lazy[node];
        else {
            lazy[node*2] += lazy[node];
            lazy[node*2+1] += lazy[node];
        }
        lazy[node] = 0;
    }
}
 
void update(int node, int st, int en, int li, int ri, int diff) {
    lazy_update(node, st, en);
    if(ri < st || en < li) return;
    if(li <= st && en <= ri) {
        if(st == en) tree[node] += diff;
        else {
            lazy[node*2] += diff;
            lazy[node*2+1] += diff;
        }
        return;
    }
    
    int mid = (st+en)/2;
    update(node*2, st, mid, li, ri, diff);
    update(node*2+1, mid+1, en, li, ri, diff);
}
 
ll query(int node, int st, int en, int idx) {
    lazy_update(node, st, en);
    if(st == en) return tree[node];
    
    int mid = (st+en)/2;
    if(idx <= mid) return query(node*2, st, mid, idx);
    else return query(node*2+1, mid+1, en, idx);
}
 
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    fill(initSalary, initSalary+500010, 0);
    fill(l, l+500010, 0);
    fill(r, r+500010, 0);
    fill(segToOrigin, segToOrigin+500010, 0);
    int N,M; cin >> N >> M;
    
    cin >> initSalary[1];
    
    for(int i=2; i<=N; i++) {
        int a,b; cin >> a >> b;
        initSalary[i] = a;
        child[b].push_back(i);
    }
    int idx = -1;
    // 세그먼트 위치 설정
    dfs(1, idx);
    
    // 세그먼트에서 원래로 가는 값
    for(int i=1; i<=N; i++) {
        segToOrigin[l[i]] = i;
    }
        
    int h = ceil(log2(N));
    tree.resize(1<<(h+1));
    lazy.resize(1<<(h+1));
    
    make(1,0,N-1);
    for(int i=0; i<M; i++) {
        char order; cin >> order;
        if(order == 'p') {
            int a,b; cin >> a >> b;
            // 자식이 없으면 건너뜀
            if(l[a] == r[a]) continue;
            update(1,0,N-1,l[a]+1, r[a], b);
        } else {
            int a; cin >> a;
            cout << query(1,0,N-1,l[a]) << '\n';
        }
    }
    
    return 0;
}
 
cs

문제유형

  • 세그먼트 - 부모 자식 문제
    • 트리가 편향되어있을때 O(NM)을 세그먼트에 넣어 O(NlgM)으로 만듬
    • 세그먼트에 넣도록 노드를 배열에 각각 넣음
    • l 배열 : 자기자신 인덱스, 다음값부터 자식 인덱스
    • r 배열 : 자식 마지막 인덱스
    • 업데이트 시 l+1 부터 r까지 업데이트

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

백준 11066 파일 합치기  (0) 2021.03.09
백준 10775 공항  (0) 2021.03.09
백준 6549 히스토그램에서 가장 큰 직사각형 쉬운 풀이 (C++/CPP)  (0) 2021.03.04
백준 1865 웜홀 쉬운 풀이 (C++/CPP)  (0) 2021.03.04
백준 13549 숨바꼭질 3  (0) 2021.03.03

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


아이디어

  • 시작점 * 끝점 모든 경우의 수 구할 떄
    • O(N^2) = 1e10 시간초과
  • 분할정복을 사용
    • 최소값의 양쪽의 사각형의 넓이 중 큰값을 선택
  • 세그먼트 트리로 구현
    • 세그먼트 트리 구성 : 각 노드는 가장 작은값을 가지는 인덱스를 지정
    • 구간에서 가장 작은 값의 인덱스를 찾아서
    • 그 양쪽의 값을 계산해줌

시간복잡도 계산

  • 세그먼트 트리 생성 : O(NlgN)
  • 검색 및 최대값 계산 : O(lgN)
  • 총합 : O(NlgN)

인트 계산

  • 세그먼트 값 : 최소 인덱스 : 최대 1e5, INT 가능
  • 각 히스토그램 크기 : 최대 1e9, INT 가능
  • 사각형 계산 : 최대 1e9 * 1e5 : 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
68
69
70
71
72
73
74
75
76
77
#include <iostream>
#include <vector>
#include <cmath>
 
using namespace std;
typedef long long ll;
 
int nums[100010];
vector<int> tree;
int N;
 
int make(int node, int st, int en) {
    if(st==en) return tree[node] = st;
    
    int mid = (st+en)/2;
    int li = make(node*2, st, mid);
    int ri = make(node*2+1, mid+1, en);
    
    // 값 비교후 작은 인덱스 표시
    if( nums[li] <= nums[ri]) return tree[node] = li;
    else return tree[node] = ri;
}
 
int find(int node, int st, int en, int li, int ri) {
    if(ri < st || en < li) return -1;
    if(li <= st && en <=ri) return tree[node];
    
    int mid = (st+en)/2;
    int leftIndex = find(node*2, st, mid, li, ri);
    int rightIndex = find(node*2+1, mid+1, en, li, ri);
    
    if(leftIndex == -1) return rightIndex;
    else if(rightIndex == -1) return leftIndex;
    
    
    if(nums[leftIndex] <= nums[rightIndex]) return leftIndex;
    else return rightIndex;
    
}
 
ll query(int st, int en) {
    if(st > en) return 0;
    
    // 최소값을 기준으로 전체, 좌측, 우측 더 작은 값
    // 전체
    int mi = find(1,0,N-1, st, en);
    ll rs = (ll)(en-st+1) * nums[mi];
    rs = max(rs, query(st, mi-1));
    rs = max(rs, query(mi+1, en));
    return rs;
    
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    while(1) {
        fill(nums, nums+100010, 0);
        
        cin >> N;
        if(N==0) break;
        
        tree.clear();
        int h = ceil(log2(N));
        tree.resize(1<<(h+1));
        
        for(int i=0; i<N; i++) cin >> nums[i];
        // 세그먼트 트리 생성
        make(1,0,N-1);
        
        cout << query(0,N-1) << '\n';
        
    }
    
    
    return 0;
}
 
cs

문제유형

  • 세그먼트 - 연속된 넓이
    • 트리에 규칙에 맞는 인덱스를 넣고
    • 쿼리를 통해 시작점부터 끝점까지 값을 비교

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

백준 10775 공항  (0) 2021.03.09
백준 2820 자동차 공장 쉬운 풀이 (C++/CPP)  (0) 2021.03.05
백준 1865 웜홀 쉬운 풀이 (C++/CPP)  (0) 2021.03.04
백준 13549 숨바꼭질 3  (0) 2021.03.03
백준 9205 맥주 마시면서 걸어가기  (0) 2021.03.03

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


문제 추상화

  • 음의 간선을 통해 사이클이 생기는지 확인하는 문제

아이디어

  • 밸만 포트만 사용하여 사이클이 생기는지 확인
  • 사이클 확인할경우, 출발점 지정해줄 필요 없음

시간복잡도 계산

  • 테스트캐이스 : O(TC)
  • 밸만 포드만 : O(NM)
  • 총합 : O(TC * N * M) : 5 * 500 * 2500 = 6.25e6 > 가능

인트 계산

  • N * M * T의 최대 수 가능
  • 500 * 2500 * 1e4 = 1.25e6 * e4 = e10 > 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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <tuple>
#include <vector>
 
 
using namespace std;
typedef long long ll;
typedef tuple<int, int, int> ti3;
 
const ll inf = 2e10;
ll dist[510];
vector<ti3> edge;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int TC; cin >> TC;
    while(TC--) {
        fill(dist, dist+510, 0);
        
        edge.clear();
        int N,M,W; cin >> N >> M >> W;
        for(int i=0; i<M; i++) {
            int a,b,c; cin >> a >> b >> c;
            edge.push_back({a,b,c});
            edge.push_back({b,a,c});
        }
        
        for(int i=0; i<W; i++) {
            int a,b,c; cin >> a >> b >> c;
            edge.push_back({a,b,-c});
        }
        
        // 모든 간선을 거침
        for(int i=0; i<N-1; i++) {
            for(int j=0; j<edge.size(); j++) {
                int a,b,c; tie(a,b,c) = edge[j];
                
                if(dist[b] > dist[a] + c) dist[b] = dist[a] + c;
            }
        }
        
        bool sw = false;
        for(int j=0; j<edge.size(); j++) {
            int a,b,c; tie(a,b,c) = edge[j];
            
            if(dist[b] > dist[a] + c ) {
                cout << "YES\n";
                sw = 1;
                break;
            }
        }
        
        if(sw == false) cout << "NO\n";
        
    }
    
    return 0;
}
 
cs

문제유형

  • 밸만포드 - 사이클 확인
    • 출발점 없이 사이클만 확인
    • dist 배열 시작점을 0으로 만들고 나머지 inf로 만들고 진행할 경우, 시작점 고립되어있을경우 사이클 확인 불가

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

백준 2820 자동차 공장 쉬운 풀이 (C++/CPP)  (0) 2021.03.05
백준 6549 히스토그램에서 가장 큰 직사각형 쉬운 풀이 (C++/CPP)  (0) 2021.03.04
백준 13549 숨바꼭질 3  (0) 2021.03.03
백준 9205 맥주 마시면서 걸어가기  (0) 2021.03.03
백준 2887 행성 터널 쉬운 풀이 (C++/CPP)  (0) 2021.03.03

 

 

아이디어

  • 0-1 BFS 사용해서 동생위치 찾음
    • 처음 좌표 넣을떄 2의배수 모두 추가
    • 중간에 x2배(시간이 0) 다른것보다 먼저 수행해줘야함
    • priority_queue 사용해서 수행

 

시간복잡도 계산

  • 우선순위 큐 사용 : O(NlgN) = 1e5 * 20
  • BFS : O(V+E)
    • 노드 개수 : N
    • 간선 개수 : 최대 N
    • O(N)
  • 총합 : O(NlgN + N) : O(NlgN) > 가능

인트 계산

  • 가장 빠른시간 최대 1e5 > 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
#include <iostream>
#include <queue>
 
using namespace std;
typedef pair<int, int> pi2;
 
bool chk[100010];
int main() {
    int N,K; cin >> N >> K;
    
    priority_queue<pi2, vector<pi2>, greater<pi2>> pq;
    // 시작값 큐에 넣어줌, 앞에는 시간, 뒤에는 노드
    pq.push(make_pair(0,N));
    fill(chk, chk+100010, 0);
    chk[N] = 1;
    if(N==K) {
        cout << 0 << '\n';
        return 0;
    }
    
    while(!pq.empty()) {
        int et = pq.top().first;
        int en = pq.top().second;
        pq.pop();
        
        if(en == K) {
            cout << et << '\n';
            return 0;
        }
        
        // 2배 먼저 해주기
        int en2 = en * 2;
        while(en2 <= 100000) {
            if(chk[en2]) break;
            
            chk[en2] = 1;
            pq.push(make_pair(et, en2));
            en2 = en2 * 2;
        }
        
        // 1더한것
        if(en+1 <= 100000) {
            if(chk[en+1] == false) {
                chk[en+1] = 1;
                pq.push(make_pair(et+1, en+1));
            }
            
        }
        
        
        // 1뺀것
        if(en-1 >= 0) {
            if(chk[en-1] == false) {
                chk[en-1] = 1;
                pq.push(make_pair(et+1, en-1));
            }
            
        }
    }
    return 0;
}
 
 cs

 

문제유형

  • BFS - 0/1 : 다른 노드보다 우선 수행해줘야하는 조건이 있을때 사용

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

백준 6549 히스토그램에서 가장 큰 직사각형 쉬운 풀이 (C++/CPP)  (0) 2021.03.04
백준 1865 웜홀 쉬운 풀이 (C++/CPP)  (0) 2021.03.04
백준 9205 맥주 마시면서 걸어가기  (0) 2021.03.03
백준 2887 행성 터널 쉬운 풀이 (C++/CPP)  (0) 2021.03.03
백준 10942 팰린드롬? 쉬운 풀이 (C++/CPP)  (0) 2021.03.03

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

문제 추상화

  • 출발점에서 종료점까지 가는데
  • 최대 1000의 거리까지 갈 수 있음
  • 어느 지점 들려서 가면 갈수 있는지 확인

아이디어

  • bfs로 도착지 갈수 있는지확인
    • 그럼 각 점에서 다음 점으로 갈수 있는지는 어떻게 확인?
      • 반경 1000미터를 돌면서 확인하면 되지 않을까?
        • 그러면 정점이 너무 많아짐
        • BFS : O(V+E)
          • V : 모든 정점 : 9e8 > 시간초과
      • 편의점과 펜타포트를 기록해뒀다가 계속 탐색해보자
    • 그래서 펜타포트와 값이 같아지면 종료

시간복잡도 계산

  • 테스트 케이스 O(T)
  • 간선의 개수 : O(N^2)
  • BFS : O(V+E) = O(N^2)
  • 합 : O(T * N^2) > 가능

인트 계산

  • 거리가 될수 있는 최대값 = 32767 * 2 > 인트 가능

코드

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
#include <iostream>
#include <vector>
#include <cmath>
#include <queue>
 
using namespace std;
typedef pair<int, int> pi2;
 
vector<pi2> v;
bool chk[110];
vector<int> adj[110];
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int t; cin >> t;
    while(t--) {
        int N; cin >> N;
        
        v.clear();
        // 출발값
        int sty,stx;
        cin >> sty >> stx;
        v.push_back(make_pair(sty, stx));
        
        // 편의점 위치 배열
        
        for(int i=0; i<N; i++) {
            int ey, ex;
            cin >> ey >> ex;
            v.push_back(make_pair(ey, ex));
        }
        int eny, enx;
        cin >> eny >> enx;
        v.push_back(make_pair(eny, enx));
 
        
        // 인접 리스트 초기화
        for(int i=0; i<110; i++) adj[i].clear();
 
        for(int i=0; i<=N+1; i++) {
            int ey = v[i].first;
            int ex = v[i].second;
            
            for(int j=0; j<=N+1; j++) {
                if(i==j) continue;
                int ny = v[j].first;
                int nx = v[j].second;
                if(abs(ey - ny) + abs(ex - nx) <= 1000) {
                    adj[i].push_back(j);
                }
                
                
            }
 
        }
        
        // st에서부터 bfs 시작해 en도착하면 종료
        fill(chk, chk+110, 0);
        
        queue<int> q;
        q.push(0);
        chk[0] = 1;
        
        bool sw = false;
        
        while(!q.empty()) {
            int eq = q.front(); q.pop();
            if(eq == N+1) {
                cout << "happy\n";
                sw = 1;
                break;
            }
            
            for(auto x : adj[eq]) {
                if(chk[x] == 1) continue;
                q.push(x);
                chk[x] = 1;
            }
        }
        
        if(sw == false) cout << "sad\n";
        
        
        
    }
    return 0;
}
 
cs

문제유형

  • BFS - 조건
    • 특정 거리 이하의 경우에만 이동할 수 있는 경우
    • 해당 조건에 만족하는 경우만 간선에 추가한 뒤 BFS 수행

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

백준 1865 웜홀 쉬운 풀이 (C++/CPP)  (0) 2021.03.04
백준 13549 숨바꼭질 3  (0) 2021.03.03
백준 2887 행성 터널 쉬운 풀이 (C++/CPP)  (0) 2021.03.03
백준 10942 팰린드롬? 쉬운 풀이 (C++/CPP)  (0) 2021.03.03
백준 4354 문자열 제곱 쉬운 풀이 (C++/CPP)  (0) 2021.03.03

+ Recent posts

티스토리툴바