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


아이디어

  • BFS를 사용해서 지훈이와 불을 각각 하나씩 이동해주자
  • 이떄 지훈이가 밖으로 넘어가면 종료

시간복잡도 계산

  • BFS(V+E)
    • V : O(RC)
    • E : O(RC*4)
    • 총합 : O(RC)

자료구조

  • map[1000][1000]
  • BFS queue<pair<int, int>>
    • 좌표 최대 1000
  • 시간 t : 최대 1000

코드(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
#include <iostream>
#include <queue>
 
using namespace std;
typedef pair<int, int> pi2;
 
char map[1010][1010];
int dy[] = {0,1,0,-1};
int dx[] = {1,0,-1,0};
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    queue<pi2> jihoon;
    queue<pi2> fire;
    
    int R,C; cin >> R >> C;
    for(int j=0; j<R; j++) {
        for(int i=0; i<C; i++) {
            cin >> map[j][i];
            if(map[j][i] == 'J') jihoon.push(make_pair(j,i));
            else if(map[j][i] == 'F') fire.push(make_pair(j,i));
        }
    }
    
    int t=0;
    while(1) {
        t++;
        // 지훈 먼저 이동
        int jsize = jihoon.size();
        if(jsize == 0) break;
        
        while(jsize--) {
            auto ej = jihoon.front(); jihoon.pop();
            int ey = ej.first;
            int ex = ej.second;
            
            // 만약 현재 위치가 불이라면 이동불가
            if(map[ey][ex] == 'F') continue;
            
            for(int k=0; k<4; k++) {
                int ny = ey + dy[k];
                int nx = ex + dx[k];
                // 탈출하면 종료
                if(!(ny>=0 && ny < R && nx >=0 && nx < C)) {
                    cout << t << '\n';
                    return 0;
                }
                
                // .일떄만 이동
                if(map[ny][nx] == '.' ) {
                    map[ny][nx] = 'J';
                    jihoon.push(make_pair(ny, nx));
                }
            }
            
        }
        
        // 불 이동
        int fsize = fire.size();
        while(fsize--) {
            auto ef = fire.front(); fire.pop();
            int ey = ef.first;
            int ex = ef.second;
            
            for(int k=0; k<4; k++) {
                int ny = ey + dy[k];
                int nx = ex + dx[k];
 
                if(ny>=0 && ny < R && nx >=0 && nx < C) {
                    if(map[ny][nx] == 'J' || map[ny][nx] == '.') {
                        map[ny][nx] = 'F';
                        fire.push(make_pair(ny, nx));
                    }
                }
            }
        }
        
        
        
    }
    
    cout << "IMPOSSIBLE";
    
    return 0;
}
 
cs

문제유형

  • BFS - 경찰과 도둑
    • 경찰은 쫓고, 도둑은 탈출
    • bfs로 맵을 인자로하면 메모리 차지가 너무크므로, 경찰, 도둑 좌표를 인자로

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

백준 15649 N과 M (1)  (0) 2021.03.15
백준 2579 계단 오르기  (0) 2021.03.14
백준 4485 녹색 옷 입은 애가 젤다지?  (0) 2021.03.14
백준 1926 그림  (0) 2021.03.14
백준 1038 감소하는 수  (0) 2021.03.14

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


아이디어

  • 최소비용으로 목적지에 도착해야함 >> 다익스트라
  • 다익스트라 알고리즘 내에서 간선을 통해서 이동한 값이 더 작을경우 갱신

시간복잡도 계산

  • 다익스트라 알고리즘 : O(ElgE)
    • 여기서 E : N^2 * 4
    • O(N^2 * lg N^2)

자료구조

  • 현재 거리값 dist : 최대값 N^2 * 10 = 2e5
  • 전체 지도 map : 최대값 10

코드(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
#include <iostream>
#include <queue>
#include <tuple>
 
using namespace std;
typedef tuple<int, int, int> ti3;
 
int dist[150][150];
int map[150][150];
const int inf = 3e5;
int dy[] = {0,1,0,-1};
int dx[] = {1,0,-1,0};
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int t=0;
    while(1) {
        
        fill(&dist[0][0], &dist[149][150], inf);
        
        int N; cin >> N;
        if(N==0) break;
        
        for(int j=0; j<N; j++) {
            for(int i=0; i<N; i++) {
                cin >> map[j][i];
            }
        }
        
        priority_queue<ti3, vector<ti3>, greater<ti3>> pq;
        
        // 출발점
        dist[0][0] = map[0][0];
        pq.push({dist[0][0], 0, 0});
        
        while(!pq.empty()) {
            int ec, ey, ex;
            tie(ec,ey,ex) = pq.top(); pq.pop();
            
            if(dist[ey][ex] != ec) continue;
            
            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 < N) {
                    if(dist[ny][nx] > dist[ey][ex] + map[ny][nx]) {
                        dist[ny][nx] = dist[ey][ex] + map[ny][nx];
                        pq.push({dist[ny][nx], ny, nx});
                    }
                }
            }
        }
        
        t++;
        cout << "Problem " << t << ": " << dist[N-1][N-1] << '\n';
    }
    
    
    return 0;
}
cs

문제유형

  • 2차원 다익스트라
    • 목적지 도착하는데 최소 비용 문제
    • 현재 비용 표시되는 배열 추가해서, 현재보다 작으면 업데이트

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

백준 2579 계단 오르기  (0) 2021.03.14
백준 4179 불!  (0) 2021.03.14
백준 1926 그림  (0) 2021.03.14
백준 1038 감소하는 수  (0) 2021.03.14
백준 9019 DSLR  (0) 2021.03.13

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


아이디어

  • BFS 사용해서 연결된 노드 구하기(Flood Fill)
    • 전체 노드 순회하면서 체크 안되어있는 노드 발견할경우 BFS 수행
      • 이떄마다 전체 그림 카운트 수 증가
      • 그리고 그림 가장 넓은값 구하기

시간복잡도 계산

  • BFS : O(V+E)
    • V : 모든 노드수 : O(NM)
    • E : 노드에서 간선수 4방향 : O(4NM)
    • N과 M 최대값이라고 가정시
    • 총합 : O(5N^2)
      • O(5*N^2) = 5 * 25e4 : 125e4 = 1.25e6

자료구조

  • 그림 개수 cnt : 최대 N^2 = 25e4 : INT 가능
  • 그림 최대 크기 maxv : 최대 N^2 = 25e4 : INT 가능
  • BFS에서 사용하는 큐 queue<pair<int, 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
67
68
69
70
71
72
#include <iostream>
#include <queue>
 
using namespace std;
 
int map[510][510];
bool chk[510][510];
int dy[] = {0,1,0,-1};
int dx[] = {1,0,-1,0};
int N,M;
 
int bfs(int y, int x) {
    int cnt=0; // 그림 크기
    
    queue<pair<int, int>> q;
    q.push(make_pair(y, x));
    chk[y][x] =1;
    
    while(!q.empty()) {
        auto eq = q.front(); q.pop();
        int ey = eq.first;
        int ex = eq.second;
        cnt++; // 그림 크기 증가
        
        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(map[ny][nx] == 1 && chk[ny][nx] == 0) {
                    chk[ny][nx] = 1;
                    q.push(make_pair(ny, nx));
                }
            }
        }
    }
    
    return cnt;
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    fill(&chk[0][0], &chk[509][510], 0);
    
    cin >> N >> M;
    for(int j=0; j<N; j++) {
        for(int i=0; i<M; i++) {
            cin >> map[j][i];
        }
    }
    
    int cnt=0;
    int maxv= 0;
    
    // 체크되어있지 않은 경우 bfs 수행
    for(int j=0; j<N; j++) {
        for(int i=0; i<M; i++) {
            if(map[j][i] == 1 && chk[j][i] == false) {
                maxv = max(maxv, bfs(j,i));
                cnt++;
            }
        }
    }
    
    cout << cnt << '\n';
    cout << maxv << '\n';
    
    
    return 0;
}
 
cs

문제유형

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

비슷한 문제

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

백준 4179 불!  (0) 2021.03.14
백준 4485 녹색 옷 입은 애가 젤다지?  (0) 2021.03.14
백준 1038 감소하는 수  (0) 2021.03.14
백준 9019 DSLR  (0) 2021.03.13
백준 1747 소수&팰린드롬  (0) 2021.03.13

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


아이디어

  • N번째까지 순회하면서 숫자를 확인
  • 순회할때 조건
    • 1자리수는 통과
    • 자리수 올라갈떄, 10 곱한뒤에, 가장 마지막 수보다 작은것들만 추가
    • 그럼 이전에 감소한 수를 재사용해야함 > 큐를 사용해서 이전에 계산한 값 넣어주기
  • 일의 자리 일때 조심!

시간복잡도 계산

  • N까지 순회 : O(N)
  • 마지막 일의자리 10개 순회 : O(10)

자료구조

  • queue <long long>
    • 최대 숫자 될수 있는수 10자리 > long long 사용
    • 감소하는 수이기 때문에 숫자가 총 10개

코드(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>
#include <queue>
 
using namespace std;
typedef long long ll;
 
int main() {
    int N; cin >> N;
    
    // 1의 자리 미리 출력
    // 큐에 넣은 후 출력하려고하면 복잡해짐
    if(N <=9) {
        cout << N << '\n';
        return 0;
    }
    
    queue<ll> q;
    for(int i=0; i<=9; i++) q.push(i);
    
    int cnt=9;
    
    while(!q.empty()) {
        ll eq = q.front(); q.pop();
        
        // 일의자리 구해서 작은수까지 순회
        int lastNum = eq%10;
        for(int i=0; i<lastNum; i++) {
            
            ll ev = eq*10 + i;
            q.push(ev);
            cnt++;
            if(cnt==N) {
                cout << ev << '\n';
                return 0;
            }
        }
    }
    
    cout << -1 << '\n';
    
    return 0;
}
 
cs

문제유형

  • 브루트포스 - 큐
    • 특정 순번의 값을 확인해야할때
    • 이전에 사용한 값을 재활용 할수 있을 때
    • 큐에 넣고, 뽑으면서 다음 값을 구함

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

백준 4485 녹색 옷 입은 애가 젤다지?  (0) 2021.03.14
백준 1926 그림  (0) 2021.03.14
백준 9019 DSLR  (0) 2021.03.13
백준 1747 소수&팰린드롬  (0) 2021.03.13
백준 2638 치즈  (0) 2021.03.13

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

+ Recent posts

티스토리툴바