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


아이디어

  • 브루트포스 : 모든 노드 순회하면서 얼리어답터 O,X 인경우 모두 확인해줌
    • 시간복잡도 : O(2^N) > 시간초과
  • 자식의 얼리어답터 최소값을 부모가 활용가능 > tree dp 사용
  • DP[node][0] : 얼리어답터 아닐떄 필요한 최소 얼리어답터 수
  • DP[node][1] : 얼리어답터일때 필요한 최소 얼리어답터 수
  • 부모노드가 얼리어답터 아닐떄 자식노드는 얼리어답터일떄의 합
  • 부모노드가 얼리어답터일떄 자식노드는 얼리어답터이거나 아닐때 더 작은값의 합
  • 점화식 :
    • DP[node][0] = sum(DP[자식노드][1]
    • DP[node][1] = sum(min(DP[자식노드][0], DP[자식노드][1]))

시간복잡도 계산

  • O(노드개수 * 2) = 2e6 > 가능

자료구조

  • 인접 리스트 : vector adj[1000010]
  • 단방향 리스트 : vector tree[1000010]
    • tree dp 사용할 떄는 단방향 리스트 만들어줘야함
  • int dp[1000010][2]
    • DP 최대값 : 1e6 > 가능

코드(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
#include <iostream>
#include <vector>
 
using namespace std;
 
vector<int> adj[1000010];
vector<int> tree[1000010];
int dp[1000010][2];
int N;
 
void make_tree(int cur, int pre) {
    for(int x : adj[cur]) {
        if(x==pre) continue;
        tree[cur].push_back(x);
        make_tree(x, cur);
    }
}
 
int get_dp(int node, int early) {
    if(dp[node][early] != -1) return dp[node][early];
    
    int ans=0;
    for(int x : tree[node]) {
        if(early == 0) ans += get_dp(x,1);
        else ans += min(get_dp(x,1), get_dp(x,0));
    }
    
    return dp[node][early] = ans + early;
    
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    // tree dp는 root에서부터 top-down으로 이루어짐
    // 그래서 -1로 초기화
    fill(&dp[0][0], &dp[1000009][2], -1);
    
    cin >> N;
    for(int i=0; i<N-1; i++) {
        int a,b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    // 단방향 그래프로 바꿔줌
    make_tree(1, -1);
    
    // root 노드에서 얼리 어답터 최소 수를 구하기
    cout << min(get_dp(1,0), get_dp(1,1)) << '\n';
    return 0;
}
 
cs

문제유형

  • DP - Tree DP
    • 자식노드의 값을 재활용 할 수 있을 때 Tree DP 사용 가능
    • 기존의 DP와 다른점은, 간선으로 연결된 노드에 DP를 적용

비슷한 문제

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

백준 1693 트리 색칠하기  (0) 2021.04.23
백준 3687 성냥개비  (0) 2021.04.22
백준 1707 이분 그래프  (0) 2021.04.22
백준 9466 텀 프로젝트  (0) 2021.04.22
백준 2580 스도쿠  (0) 2021.04.20

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

아이디어

  • 부모트리 아래 모든 비용 : 자식 트리를 기준 아래 모든비용 + 부모트리 색
  • 자식노드의 값을 재활용 가능 > Tree DP
    • Tree DP는 인접리스트를 단방향 리스트로 만들어줘야함
  • DP[N][K] : N번 노드가 K색을 칠할떄 최소비용
  • 점화식 : DP[N][K] = min(DP[N-1][0] ~ DP[N-1)[K-1], DP[N-1][K+1] ~DP[N-1][KK]) + 다른 자식노드 + 부모노드 색
    • 부모노드 DP값 = 자식노드 해당 색깔 제외한 최소값의 합 + 부모노드색
  • 색을 N색 모두 하면 메모리초과 발생
    • 모든 색을 사용하지 않아도됨
    • 계산에 따라서 lgN색까지만 구하면됨, 넉넉하게 20개 구해보자

시간복잡도 계산

  • 모든 노드 * lgN개의 색
  • O(N*lgN) > 가능

자료구조

  • 인접 리스트 : vector adj[100010]
  • 단방향 리스트 : vector tree[100010]
  • dp값 : int dp[100010][21]

코드(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 <vector>
 
using namespace std;
 
const int inf = 1e8+10;
vector<int> adj[100010];
vector<int> tree[100010];
int dp[100010][30];
 
void make_tree(int cur, int pre) {
    for(int x : adj[cur]) {
        // 이전노드에서 넘어 온경우 건너뜀
        if(x == pre) continue;
        tree[cur].push_back(x);
        make_tree(x, cur);
    }
}
 
int get_dp(int node, int color) {
    if(dp[node][color] != -1) return dp[node][color];
    
    int ans=0;
    // 자식노드 dp 값 모두 더한다음 부모노드 색 더해서 리턴'
    // 이떄 자식노드는 같은 색깔 아니어야함
    for(int x : tree[node]) {
        int minv = inf;
        for(int k=1; k<=20; k++) {
            if(color == k) continue;
            minv = min(minv, get_dp(x, k));
        }
        ans += minv;
    }
    
    return dp[node][color] = ans + color;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    // dp를 가장 아래노드부터 구하는게 어려움
    // 그래서 top-down 방식으로 root 노드에서부터 구하자
    // 그럼 -1로 초기화해서 처리 된것인지 아닌지 구분해야함
    fill(&dp[0][0], &dp[100009][30], -1);
    
    int N; cin >> N;
    for(int i=0; i<N-1; i++) {
        int a,b; cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    
    // 단방향 리스트 만들기
    make_tree(1,-1);
    
    int minv = inf;
    
    for(int i=1; i<=20; i++) {
        // 1번노드의 1~20색깔을 가질때 최소값 구하기
        minv = min(minv, get_dp(1, i));
    }
    
    cout << minv << '\n';
    return 0;
}
 
cs

문제유형

  • DP - Tree DP
    • 자식노드의 값을 재활용 할 수 있을 때 Tree DP 사용 가능
    • 기존의 DP와 다른점은, 간선으로 연결된 노드에 DP를 적용

비슷한 문제

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

백준 2533 사회망 서비스(SNS)  (0) 2021.04.23
백준 3687 성냥개비  (0) 2021.04.22
백준 1707 이분 그래프  (0) 2021.04.22
백준 9466 텀 프로젝트  (0) 2021.04.22
백준 2580 스도쿠  (0) 2021.04.20

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


아이디어

  • 가장 큰수일떄 : 자리수가 길어야하고, 같은자리수라면 큰수가 먼저
    • 성냥개비 가장 작게사용 : 1(2), 7(3)
    • 그리디 방법 사용 > 처음에 홀수이면 7, 짝수이면 2 붙임
  • 가장 작은수 : 자리수가 작아야하고, 같은자리수라면 작은수 먼저
    • 가장 작은 자리수 구하는 방법
      • 주어진 성냥개비로 작은 자리수부터 가능한지 확인
      • 앞에 어떤자리수 들어가면 7XXX
      • 뒤에 남은 성냥개비수로 가능한지 확인하면됨
      • 이전값을 재활용할수 있음 > DP 사용
      • DP[K][N] : 성냥개비 N개로 K자리수를 만들수 있는지
    • 앞에 작은수부터 넣어서 남은 성냥개비로 가능한지 확인
      • 이때 DP로 남은 성냥개비로 숫자 만들수 있는지 확인

시간복잡도 계산

  • 큰수 확인
    • 테스트케이스 : T
    • 성냥개비 N번 반복 : N
    • 합 : O(NT)
  • 작은수 확인
    • 테스트케이스 : T
    • DP값 계산
      • N개 성냥개비로
      • K자리수가능한지 확인(K최대 50, 성냥개비 최대 100개일떄 1로만 만드는경우)
      • O(NK)
    • 작은수부터 넣기
      • N개 성냥개비
      • 모든 숫자 확인 : 10
      • O(10N)
  • 총합 : O(NT + T(NK+10N)) = O(TN^2) = 100^3 = 1e6 > 가능

자료구조

  • 총합 : O(NT + T(NK+10N)) = O(TN^2) = 100^3 = 1e6 > 가능

코드(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
#include <iostream>
#include <string>
 
using namespace std;
 
int nums[10] = {6,2,5,5,4,5,6,3,7,5};
bool dp[60][110];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    // DP 먼저 구하기
    fill(&dp[0][0], &dp[59][110], 0);
    dp[0][0] = 1;
    for(int j=1; j<=50; j++) {
        for(int i=0; i<=100; i++) {
            for(int k=0; k<10; k++) {
                // 가지고 있는 성냥개비가 부족할떄
                if(i-nums[k]<0) continue;
                if(dp[j-1][i-nums[k]]) dp[j][i] = 1;
            }
        }
    }
    
    int T; cin >> T;
    while(T--) {
        
        string maxv;
        string minv;
        int N; cin >> N;
        
        // 최대값 먼저 구하기
        int maxN = N;
        while(maxN >0) {
            if(maxN % 2 == 1) {
                maxv += "7";
                maxN -= 3;
            } else {
                maxv += "1";
                maxN -= 2;
            }
        }
        
        
        // 최소값 구하기
        // 최소자리부터 구하자
        int len;
        for(int k=1; k<=50; k++) {
            if(dp[k][N]) {
                len = k;
                break;
            }
        }
        // 첫자리는 0이 불가하므로 1부터 계산
        for(int i=1; i<=9; i++) {
            if(N-nums[i] >=0) {
                if(dp[len-1][N-nums[i]]) {
                    minv += '0'+i;
                    N -= nums[i];
                    len--;
                    break;
                }
            }
        }
        // 다음 자리
        while(N>0) {
            for(int i=0; i<=9; i++) {
                if(N-nums[i] >=0) {
                    if(dp[len-1][N-nums[i]]) {
                        minv += '0'+i;
                        N -= nums[i];
                        len--;
                        break;
                    }
                }
            }
        }
        cout << minv << ' ' << maxv << '\n';
        
        
    }
    
    return 0;
}
 
cs

문제유형

  • DP - 최소값
    • 주어진 개수로 최소값을 만들어야할때 조건
    • 2가지 조건 만족해야함 : 자리수 최저, 앞의 숫자일수록 작은수
    • 주어진 개수로 가능한 자리수를 DP로 만들어준뒤, 낮은수 부터 추가하면서 남은 개수로 남은 자리수를 만들수 있는지 확인하면서 추가

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

백준 2533 사회망 서비스(SNS)  (0) 2021.04.23
백준 1693 트리 색칠하기  (0) 2021.04.23
백준 1707 이분 그래프  (0) 2021.04.22
백준 9466 텀 프로젝트  (0) 2021.04.22
백준 2580 스도쿠  (0) 2021.04.20

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


아이디어

  • 스도쿠 빈칸에 백트래킹으로 1부터 9까지 모두 넣어서 가능한지 확인
  • 이때 빈칸의 위치를 받아서 해당 빈칸만 백트래킹 해줌
  • 이때 가로, 세로, 주변 9칸에 숫자 들어갔는지 확인하는 배열 미리 사용해 빠르게 확인

시간복잡도 계산

  • 스도쿠 모든칸 : N일때( N=10)
    • O(10^N^2)
    • 시간 초과나겠지만, 가지치기가 될 수 있을거라고 예상하고 진행

자료구조

  • 스도쿠 맵 : int map[10][10]
  • 가로에 들어간 숫자 chk : bool row_chk[10][10];
  • 세로에 들어간 숫자 chk : bool col_chk[10][10];
  • 주변 9칸에 들어간 숫자 chk : bool rec_chk[5][5][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
62
63
64
65
66
67
68
69
70
71
72
#include <iostream>
#include <vector>
 
using namespace std;
typedef pair<int, int> pi2;
 
int map[10][10];
bool row_chk[10][10];
bool col_chk[10][10];
bool rec_chk[5][5][10];
vector<pi2> v;
 
void dfs(int num) {
    if(num == v.size()) {
        for(int j=0; j<9; j++) {
            for(int i=0; i<9; i++) {
                cout << map[j][i] << ' ';
            }
            cout << '\n';
        }
        exit(0);
    }
    
    int ey = v[num].first;
    int ex = v[num].second;
    
    for(int i=1; i<=9; i++) {
        if(row_chk[ey][i]) continue;
        if(col_chk[ex][i]) continue;
        if(rec_chk[ey/3][ex/3][i]) continue;
        
        row_chk[ey][i] = 1;
        col_chk[ex][i] = 1;
        rec_chk[ey/3][ex/3][i] = 1;
        map[ey][ex] = i;
        
        dfs(num+1);
        
        row_chk[ey][i] = 0;
        col_chk[ex][i] = 0;
        rec_chk[ey/3][ex/3][i] = 0;
        map[ey][ex] = 0;
        
        
    }
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
 
    fill(&row_chk[0][0], &row_chk[9][10], 0);
    fill(&col_chk[0][0], &col_chk[9][10], 0);
    fill(&rec_chk[0][0][0], &rec_chk[4][4][10], 0);
    
    for(int j=0; j<9; j++) {
        for(int i=0; i<9; i++) {
            cin >> map[j][i];
            if(map[j][i] == 0) v.push_back(make_pair(j,i));
            else {
                // 빈칸 아닐경우 이미 들어가있는 수 체크
                row_chk[j][map[j][i]] = 1;
                col_chk[i][map[j][i]] = 1;
                rec_chk[j/3][i/3][map[j][i]] = 1;
            }
        }
    }
    
    dfs(0);
    
    return 0;
}
 
cs

문제유형

  • 백트래킹 - 원래값으로 바꿔주는것
    • 무조건 다음 depth로 나가는 것은 상관없는데,
    • if 문써서 체크한다음 다음 dfs로 나갈 경우
    • 모든 경우 통과되지 않으면 이전 depth로 돌아오게됨
    • 이때 0으로 초기화되지 않은 값이 영향을 미치게됨

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

백준 1707 이분 그래프  (0) 2021.04.22
백준 9466 텀 프로젝트  (0) 2021.04.22
백준 2458 키 순서  (0) 2021.04.20
백준 18233 민준이와 마산 그리고 건우  (0) 2021.04.20
백준 1238 파티  (0) 2021.04.20

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


아이디어

  • 각 노드의 순서를 구하기
  • 만약 구체적인 순서를 묻지 않았다면 topo
    • topo는 구체적인 수치는 알 수 없음
  • floyd해서, 각 원소가 앞에있는지 위에있는지 확인
    • 이때, 확인되지 않은 원소가 있을경우, 모르는것

시간복잡도 계산

  • 플로이드 : O(N^3), 125e6 > 1e8 > 가능

자료구조

  • 앞인지 뒤인지 확인 배열 : int map[510][510]
    • -1 : 아직 모르는 상태
    • 0 : 작음, map[a][b] =0 = a가 b보다 작음
    • 1 : 큼, map[a][b] = 1 = a가 b보다 큼

코드(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
#include <iostream>
 
using namespace std;
 
int map[510][510];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N,M; cin>> N >> M;
    fill(&map[0][0], &map[509][510], -1);
    
    for(int i=0; i<M; i++) {
        int a,b; cin >> a >> b;
        map[a][b] = 0;
        map[b][a] = 1;
    }
    
    for(int i=1; i<=N; i++) map[i][i] = 1;
    
    // floyd 수행
    for(int k=1; k<=N; k++) {
        for(int j=1; j<=N; j++) {
            for(int i=1; i<=N; i++) {
                if(map[j][i] == -1) {
                    // j가 k보다 크고, k가 i보다 크면, j는 i 보다 큼
                    if(map[j][k] ==1 && map[k][i] == 1) map[j][i] = 1;
                    // j가 k보다 작고, k가 i보다 작으면, j는 i 보다 작음
                    if(map[j][k] ==0 && map[k][i] == 0) map[j][i] = 0;
                    
                }
            }
        }
    }
    
    int cnt=0;
    for(int j=1; j<=N; j++) {
        int ecnt = 0;
        for(int i=1; i<=N; i++) {
            if(map[j][i] == -1) break;
            ecnt++;
        }
        if(ecnt == N) cnt++;
    }
    
    cout << cnt << '\n';
    
    return 0;
}
 
cs

문제유형

  • 플로이드 - 몇번째 순서인지 구하는 문제
    • topological sort는 전체 순서는 맞지만, 내가 몇번째 순서인지 정확히 알수는 없음
      • 예시 : 1번 노드가 2번쨰 순서도 정답이고 3번째 순서도 정답임
    • floyd로 모든 케이스 비교해서 구할 수 있음
      • map[j][k] = 1 && map[k][i] ==1 >> map[j][i] =1

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

백준 9466 텀 프로젝트  (0) 2021.04.22
백준 2580 스도쿠  (0) 2021.04.20
백준 18233 민준이와 마산 그리고 건우  (0) 2021.04.20
백준 1238 파티  (0) 2021.04.20
백준 7453 합이 0인 네 정수  (0) 2021.03.19

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


아이디어

  • 다익스트라를 두번써서 한번 거치고 가는것과 바로 가는것을 비교
  • 출발지에서 다익스트라 수행
  • 건우 위치에서 다익스트라 수행
  • 출발지 -> 마산 == 출발지 -> 건우 + 건우 -> 마산 을 확인

시간복잡도 계산

  • 다익스트라 : O(ElgE)
    • E : 1e4
    • 가능

자료구조

  • 인접리스트 vector<pair<int, int>> adj[5010]
    • 이떄 양방향임을 조심
  • 다익스트라 거리 배열 : int dist[5010]
    • chleorjfl : 1e4 * 5e3= 5e7 > 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
73
#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
typedef pair<int, int> pi2;
 
vector<pi2> adj[5010];
const int inf = 1e8+10;
int dist[5010];
int dist2[5010];
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int V,E,P; cin >> V >> E >> P;
    for(int i=0; i<E; 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));
    }
    
    fill(dist, dist+5010, inf);
    fill(dist2, dist2+5010, inf);
    priority_queue<pi2, vector<pi2>, greater<pi2>> pq;
    
    // 1번에서 출발
    dist[1] = 0;
    pq.push(make_pair(dist[1],1));
    while(!pq.empty()) {
        auto eq = pq.top(); pq.pop();
        int ec = eq.first;
        int ei = eq.second;
        
        if(dist[ei] != ec) continue;
        
        for(auto x : adj[ei]) {
            int nc = x.first;
            int ni = x.second;
            if(dist[ni] > nc + ec) {
                dist[ni] = ec + nc;
                pq.push(make_pair(dist[ni], ni));
            }
        }
    }
    
    dist2[P] = 0;
    pq.push(make_pair(dist2[P],P));
    while(!pq.empty()) {
        auto eq = pq.top(); pq.pop();
        int ec = eq.first;
        int ei = eq.second;
        
        if(dist2[ei] != ec) continue;
        
        for(auto x : adj[ei]) {
            int nc = x.first;
            int ni = x.second;
            if(dist2[ni] > nc + ec) {
                dist2[ni] = ec + nc;
                pq.push(make_pair(dist2[ni], ni));
            }
        }
    }
    
    if(dist[V] == dist[P] + dist2[V]) cout << "SAVE HIM\n";
    else cout << "GOOD BYE\n";
    
    
    
    return 0;
}
 
cs

문제유형

  • 한점 거쳐서 갈경우 최소거리인지 확인
    • E가 V에 비해 상대적으로 작으면(E<V^2), 다익스트라 두번쓰고
    • E가 V에 비해 상대적으로 크면(E > V^2), 플로이드 사용
    • 거쳐간 경우의 거리랑 최소값이 같은지 확인

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

백준 2580 스도쿠  (0) 2021.04.20
백준 2458 키 순서  (0) 2021.04.20
백준 1238 파티  (0) 2021.04.20
백준 7453 합이 0인 네 정수  (0) 2021.03.19
백준 2581 소수  (0) 2021.03.18

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


아이디어

  • X마을에서 각자 돌아가는 것은 다익스트라로 가능
  • 그럼 각자 마을에 X 모이는것도 다익스트라로 가능할까?
    • 경로를 반대로 저장해 놓으면 가능
  • X에 갈때의 경로와 돌아올때 사용할 경로를 각각 저장
    • X에 갈떄 경로는 다익스트라를 거꾸로 사용하기 위해 경로를 반대로 저장

시간복잡도 계산

  • 다익스트라 : O(ElgE)
    • E : M
    • O(MlgM) > 가능

자료구조

  • 경로 인접리스트 : vector<pair<int, int>> adj[1010]
    • 비용과 함꼐 입력
      • 다익스트라 비용 리스트 : int dist[1010]
    • 경로의 최대값이 별도로 나와있진 않지만, 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
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
typedef pair<int, int> pi2;
 
const int inf = 1e8+10;
int dist[1010];
int dist_rev[1010];
vector<pi2> adj[1010];
vector<pi2> adj_rev[1010];
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    fill(dist, dist+1010, inf);
    fill(dist_rev, dist_rev+1010, inf);
    
    int N,M,X; cin >> N >> M >> X;
    for(int i=0; i<M; i++) {
        int a,b,c; cin >> a >> b >> c;
        adj[a].push_back(make_pair(c,b));
        adj_rev[b].push_back(make_pair(c,a));
    }
    
    // 가는것 먼저
    priority_queue<pi2, vector<pi2>, greater<pi2>> pq;
    
    // 도착지를 먼저 넣어 거꾸로 수행
    dist_rev[X] = 0;
    pq.push(make_pair(dist_rev[X], X));
    
    while(!pq.empty()) {
        auto eq = pq.top(); pq.pop();
        int ec = eq.first;
        int ei = eq.second;
        if(dist_rev[ei] != ec) continue;
        
        for(auto x : adj_rev[ei]) {
            int nc = x.first;
            int ni = x.second;
            if(dist_rev[ni] > ec + nc) {
                dist_rev[ni] = ec + nc;
                pq.push(make_pair(dist_rev[ni], ni));
            }
        }
    }
    
    // 돌아오는것
    dist[X] = 0;
    pq.push(make_pair(dist[X], X));
    while(!pq.empty()) {
        auto eq = pq.top(); pq.pop();
        int ec = eq.first;
        int ei = eq.second;
        if(dist[ei] != ec) continue;
        
        for(auto x : adj[ei]) {
            int nc = x.first;
            int ni = x.second;
            if(dist[ni] > ec + nc) {
                dist[ni] = ec + nc;
                pq.push(make_pair(dist[ni], ni));
            }
        }
    }
    
    
    // 최대시간구하기
    int maxv = 0;
    for(int i=1; i<=N; i++) {
        maxv = max(maxv, dist[i] + dist_rev[i]);
    }
    
    cout << maxv << '\n';
    
    return 0;
}
 
 
cs

문제유형

  • 거꾸로 다익스트라
    • 한점까지 가는데 각각의 비용을 구하
    • 그래프 경로 입력부터 뒤집어서 입력

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

백준 2458 키 순서  (0) 2021.04.20
백준 18233 민준이와 마산 그리고 건우  (0) 2021.04.20
백준 7453 합이 0인 네 정수  (0) 2021.03.19
백준 2581 소수  (0) 2021.03.18
백준 12865 평범한 배낭  (0) 2021.03.18

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


아이디어

  • 접근 1. 배열 4개를 모든 경우의수로 더할경우
    • O(N^4) : 4000^4 > 시간초과
  • 접근 2. 두개씩 더해서 이진탐색 사용 가능할까?
    • 두개씩 더한다음
    • 한개만 정렬을 해줌
    • 그다음 각각 더해서 0이되는 수를 찾기
    • 0이 되는 여러개가 있을 수 있잖아 > 마지막에 같으면 여러개 구하기
    • 시간복잡도
      • 두개씩 곱함 : N^2 * 2
      • 한개 정렬 : N^2 * lgN^2
      • 모든 수에대해 더해서 0이되는 수를 이진탐색으로 찾기 : N^2 * lgN^2
      • 더해서 0이 되는거 여러개 있을경우, 계속 더해주기 : N
      • 총합 : O(N^2 * 2 + N^2 * lgN^2 + N*2 * lgN^2 * N) = O(N^3 * lgN^2) = 64e9 * 20 > 시간초과
  • 접근 3. 두개씩 더해서 투포인터 사용
    • 두개씩 더한 다음 모두 정렬
    • 각각의 배열에서 하나는 왼쪽(st)부터, 하나는 오른쪽(en)부터 시작해서 더해서 0이되는값 찾기
      • 더해서 0이 될경우, 각각 값이 같은 수 구해서 곱하기
      • 이떄, 더해서 0이될경우, 포인터 넘어가므로 O(N) 사용할 필요없음
    • 더해서 0보다 작을경우 st++, 클경우 en--

시간복잡도 계산

  • 두개 더한다음 정렬 : N^2 * 2 + N^2*lgN^2 * 2
  • 투포인터 수행 : N^2 * 2
  • 총합 : O(N^22 + N^2lgN^22 + N^22) = O(N^2*lgN^2)

자료구조

  • A,B,C,D 배열
    • 최대값 : 2^28 > INT 가능
  • 두개씩 더해준 값 : AB, CD
    • 최대값 : 2^29 > INT 가능
  • 합이 0이되는 쌍의 개수
    • 4000^4 > 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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
#include <iostream>
#include <algorithm>
 
using namespace std;
typedef long long ll;
 
int A[4010];
int B[4010];
int C[4010];
int D[4010];
int AB[16000010];
int CD[16000010];
 
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int n; cin >> n;
    for(int i=0; i<n; i++) {
        cin >> A[i] >> B[i] >> C[i] >> D[i];
    }
    
    // 두개씩 더하기
    int k=0;
    for(int j=0; j<n; j++) {
        for(int i=0; i<n; i++) {
            AB[k] = A[j] + B[i];
            CD[k] = C[j] + D[i];
            k++;
        }
    }
    
    // 정렬
    sort(AB, AB+k);
    sort(CD, CD+k);
    
    ll cnt=0;
 
    int st = 0;
    int en = k-1;
    
    while(st <k && en >=0) {
        int sumv =AB[st] + CD[en];
        if(sumv == 0) {
            // 두개가 같은게 여러개 있을 수 있음
            // 같은 값을 곱해서 더해주기
            int originSt = st;
            int sameSt = 0;
            while(AB[st] + CD[en] == 0) {
                sameSt++;
                st++;
                if(st==k) break;
            }
           
            int sameEn = 0;
            while(AB[originSt] + CD[en] == 0) {
                sameEn++;
                en--;
                if(en<0) break;
            }
            cnt += sameSt * sameEn;
        } else if(sumv < 0) {
            st++;
        } else {
            en--;
        }
    }
    
    cout << cnt << '\n';
    return 0;
}
 
cs

문제유형

  • Two pointer - 두 배열의 pointer
    • 두배열의 합이나 곱으로 모든 경우의 수를 따져야할때
    • 양쪽에서 st, en놓고 올라가고 줄어드는 방법
    • 이때 조심해야할것 : 배열이 같은 값이 중복될 수 있음
    • 이떄 중복되는것 계산해줘야함

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

백준 18233 민준이와 마산 그리고 건우  (0) 2021.04.20
백준 1238 파티  (0) 2021.04.20
백준 2581 소수  (0) 2021.03.18
백준 12865 평범한 배낭  (0) 2021.03.18
백준 8983 사냥꾼  (0) 2021.03.18

+ Recent posts

티스토리툴바