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

+ Recent posts

티스토리툴바