반응형

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

 

14675번: 단절점과 단절선

프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 트리의 정점 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 트리의 정점은 1번부터 n번까지 존재한다. 다음 줄부터 N-1개의 줄에 걸쳐 간선의 정

www.acmicpc.net

<문제 풀이> 트리

트리의 모든 간선은 단절선이 될 수 있으므로 t == 2일 때는 무조건 "yes"을 출력하면 됩니다.

트리의 한 정점에 대해서 간선이 두 개 이상이면 무조건 단절점이 됩니다.

 

<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>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <deque>
 
using namespace std;
 
int n;
int indegree[100001];
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int a, b;
        cin >> a >> b;
        indegree[a]++;
        indegree[b]++;
    }
    int q; cin >> q;
    for (int i = 0; i < q; i++) {
        int t, k;
        cin >> t >> k;
        if (t == 1) {
            if (indegree[k] >= 2) {
                cout << "yes\n";
            }
            else {
                cout << "no\n";
            }
        }
        else if (t == 2) {
            cout << "yes\n";
        }
    }
    return 0;
}
 
 cs

 

반응형
저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 1516번] 게임 개발  (0) 2021.12.20
[백준 1516번] 게임 개발  (0) 2021.12.20
[백준 2661번] 좋은수열  (0) 2021.12.16
[백준 2132번] 나무 위의 벌레  (0) 2021.12.16
[백준 1167번] 트리의 지름  (0) 2021.12.16
반응형

단절선이란 무방향 그래프에서 해당 간선을 제거했을 때 그래프가 두 개 이상으로 나누어질 때 그 간선을 단절선이라고 합니다.

 

단절선은 단절점을 구하는 것과 유사합니다.

https://seokjin2.tistory.com/87

 

[알고리즘] 단절점(Articulation Points or Cut Vertices)

단절점이란 무방향 그래프에서 해당 정점을 제거했을 때 그래프가 두 개 이상으로 나누어질 때 그 정점을 단절점이라고 합니다. 먼저 간단하게 생각할 수 있는 방법은 모든 정점에 대해서 정점

seokjin2.tistory.com

정점 A에서 부모 노드를 제외한 자식 노드들이 역방향 간선(backward edge)을 통해서 정점 A에 갈 수 없고 정점 A보다 위에 있는 선조로 갈 수 없으면 정점 A는 단절점이 됩니다.

 

단절점과 다른 점은 다음 두 가지입니다.

1. 루트가 빠졌다.

2. low > visited[A] (등호가 빠졌다) 

<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
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <deque>
 
using namespace std;
 
vector<int> adj[100001];
int visited[100001];
vector<pair<int, int> > cutEdge;
 
int v, e;
int num = 1;

/*정점 A가 우회로를 통해서 갈 수 있는 가장 빠른 정점을 리턴*/
int dfs(int A, int parent) {
    visited[A] = num++;
    int ret = visited[A]; //처음엔 자기 자신이 최상위 노드
 
    for (auto& next : adj[A]) {
        if (next == parent) continue; //부모를 제외
        if (visited[next]) {
            ret = min(ret, visited[next]); // 우회로 갱신
            continue;
        }
 
        int low = dfs(next, A); // 자식 노드가 우회로를 통해서 갈 수 있는 가장 빠른 정점
 
        if (low > visited[A]) {//자식 노드가 정점 A와 정점 A보다 위에 있는 선조로 갈 수 없으면
            cutEdge.push_back({ min(A, next), max(A, next) }); //단절선
        }
        ret = min(ret, low); //정점 A가 갈 수 있는 선조 업데이트
 
    }
    return ret;
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> v >> e;
    for (int i = 0; i < e; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
 
    for (int i = 1; i <= v; i++) {
        if (!visited[i]) dfs(i, 0);
    }
    sort(cutEdge.begin(), cutEdge.end());
 
    cout << cutEdge.size() << '\n';
    for (auto e : cutEdge) {
        cout << e.first << " " << e.second << '\n';
    }
    return 0;
}
 
 cs

 

<백준 문제>

https://www.acmicpc.net/problem/11400

 

11400번: 단절선

첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A

www.acmicpc.net

 

반응형
저작자표시

'알고리즘' 카테고리의 다른 글

[알고리즘] lower_bound, upper_bound  (0) 2023.07.21
[알고리즘] 단절점(Articulation Points or Cut Vertices)  (0) 2021.12.19
[알고리즘] 투 포인터 알고리즘(Two Pointers Algorithm)  (0) 2020.03.05
[알고리즘] 에라토스테네스의 체 알고리즘  (0) 2020.03.04
[알고리즘] O(sqrt(N)) 소수 판정 알고리즘  (0) 2020.03.02
반응형

단절점이란 무방향 그래프에서 해당 정점을 제거했을 때 그래프가 두 개 이상으로 나누어질 때 그 정점을 단절점이라고 합니다.

 

먼저 간단하게 생각할 수 있는 방법은 모든 정점에 대해서 정점 하나를 삭제해보고 DFS를 돌려서 그래프의 개수를 세보면 됩니다. 이때 시간 복잡도는 정점의 개수를 V, 간선의 개수를 E라고 할 때 O(V * (V + E) )가 됩니다.

 

그러나 위 방식은 비효율적이고 O(V + E) 시간복잡도로 단절점을 구할 수 있는 방법이 있습니다.

 

바로 DFS spanning tree를 이용하는 방법입니다.

 

위와 같은 그래프가 있을 때 DFS spanning tree로 번호를 매겨보겠습니다.

DFS spanning tree에서 단절점을 찾는 방법은

정점 A에서 부모 노드를 제외한 자식 노드들이 역방향 간선(backward edge)을 통해서 정점 A보다 위에 있는 선조로 갈 수 없으면 정점 A는 단절점이 됩니다.

 

6번 정점을 예로 들면

정점 6에서 부모 노드 1을 제외한 자식 노드인 7이 역방향 간선을 통해서 정점 6보다 위에 있는 선조 1로 갈 수 없으니깐 정점 6은 단절점이 됩니다.

 

2번 정점을 예로 들면

정점 2에서 부모 노드 7을 제외한 자식노드인 3이 역방향 간선을 통해서 정점 2보다 위에 있는 선조 7로 갈 수 있으니 정점 2는 단절점이 아닙니다.

 

그런데 루트 노드의 경우엔 선조가 없기 때문에 예외가 발생합니다.

루트 노드일 땐 루트의 자식 노드의 개수를 계산해서 자식 노드 수가 2 이상일 때 단절점이라고 판단하면 됩니다.

 

<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
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <deque>
using namespace std;
 
int v, e;
 
vector<int> adj[10001];
int visited[10001];
bool cutVertex[10001];
int num = 1;
/*정점 A가 우회로를 통해서 갈 수 있는 가장 빠른 정점을 리턴*/
int dfs(int A, int parent, bool isRoot) {
    visited[A] = num++;
    int child = 0;
    int ret = visited[A]; //처음엔 자기 자신이 최상위 노드
    for (auto& next : adj[A]) {
        if (next == parent) continue; //부모를 제외
        if (visited[next]) {
            ret = min(ret, visited[next]); // 우회로 갱신
            continue;
        }
        child++;
        int low = dfs(next, A, false);// 자식 노드가 우회로를 통해서 갈 수 있는 가장 빠른 정점
 
        if (!isRoot && low >= visited[A]) { //자식 노드가 정점 A보다 위에 있는 선조로 갈 수 없으면
            cutVertex[A] = true; // 단절점
        }
        ret = min(ret, low); //정점 A가 갈 수 있는 선조 업데이트
    }
    if (isRoot) {
        cutVertex[A] = child >= 2 ? true : false;
    }
    return ret;
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> v >> e;
    for (int i = 0; i < e; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    for (int i = 1; i <= v; i++) {
        if (!visited[i]) {
            dfs(i, 0, true);
        }
    }
    int cnt = 0;
    for (int i = 1; i <= v; i++) {
        if (cutVertex[i]) cnt++;
    }
    cout << cnt << '\n';
    for (int i = 1; i <= v; i++) {
        if (cutVertex[i]) cout << i << ' ';
    }
 
    return 0;
}
 cs

 

<백준 문제>

https://www.acmicpc.net/problem/11266

 

11266번: 단절점

첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B

www.acmicpc.net

 

반응형
저작자표시

'알고리즘' 카테고리의 다른 글

[알고리즘] lower_bound, upper_bound  (0) 2023.07.21
[알고리즘] 단절선(bridge or cut edge)  (0) 2021.12.19
[알고리즘] 투 포인터 알고리즘(Two Pointers Algorithm)  (0) 2020.03.05
[알고리즘] 에라토스테네스의 체 알고리즘  (0) 2020.03.04
[알고리즘] O(sqrt(N)) 소수 판정 알고리즘  (0) 2020.03.02
반응형

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

 

2661번: 좋은수열

첫 번째 줄에 1, 2, 3으로만 이루어져 있는 길이가 N인 좋은 수열들 중에서 가장 작은 수를 나타내는 수열만 출력한다. 수열을 이루는 1, 2, 3들 사이에는 빈칸을 두지 않는다.

www.acmicpc.net

<문제 풀이> 백트래킹

DFS로 수열에 숫자를 하나씩 추가해 나가면 되는데, 숫자를 추가했을 때 좋은 수열이 되는 경우만 추가해야 된다.

121을 예를 들어보면

 

121에서 숫자 1을 추가하면 1211이 된다. 나쁜 수열이 되었으니 숫자를 추가할 수 없다.

121에서 숫자 2를 추가하면 1212가 된다. 나쁜 수열이 되었으니 숫자를 추가할 수 없다. 

121에서 숫자 3을 추가하면 1213이 된다. 좋은 수열이 되었으니 숫자를 추가할 수 있다.

 

[좋은 수열인지 판별하는 방법]

수열의 길이를 n이라고 하면 다음과 같이 비교할 수 있다

1자리로 이루어진 부분 수열 비교

2자리로 이루어진 부분 수열 비교

.

.

 

n/2자리로 이루어진 부분 수열 비교

 

->부분 수열이 모두 다르면 좋은 수열이다.

 

ex) 수열이 123123일 때

1자리로 이루어진 부분 수열 비교

1, 2, 3, 1, 2, 3

2자리로 이루어진 부분 수열 비교

12, 31, 23

6/2 == 3자리로 이루어진 부분 수열 비교

123, 123

 

이제 수열이 좋은 수열인지 판별하는 함수를 만들고 DFS를 진행하면 되는데, 숫자를 추가했을 때 좋은 수열인 경우만 숫자를 추가했으니깐 새로 추가한 숫자가 좋은 수열인지 판별할 때는 부분 수열 뒤에 2개만 확인하면 된다.

 

1자리 일 때

1, 2, 3, 1, 2, 3

2자리 일 때

12, 31, 23

3자리 일 때

123, 123

 

<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
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <deque>
using namespace std;
 
int n;
 
bool isGood(string s) {
    int len = s.length();
    for (int i = 1; i <= len / 2; i++) {
        string a = s.substr(len - i, i);
        string b = s.substr(len - i * 2, i);
        if (a == b) return false;
    }
    return true;
}
 
string dfs(int depth, string &cur) {
    if (depth == n) {
        return cur;
    }
    for (int i = 1; i <= 3; i++) {
        char c = i + '0';
        string next = cur + c;
        if (isGood(next)) {
           string res = dfs(depth + 1, next);
           if (!res.empty()) return res;
        }
    }
    return "";
}
 
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> n;
    string start = "1";
    cout << dfs(1, start);
    return 0;
}
 
 cs

 

반응형
저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 1516번] 게임 개발  (0) 2021.12.20
[백준 14675번] 단절점과 단절선  (0) 2021.12.19
[백준 2132번] 나무 위의 벌레  (0) 2021.12.16
[백준 1167번] 트리의 지름  (0) 2021.12.16
[백준 1967번] 트리의 지름  (0) 2021.12.13
반응형

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

 

2132번: 나무 위의 벌레

첫째 줄에는 트리의 정점의 개수를 나타내는 정수 n(1 ≤ n ≤ 10,000)이 주어진다. 다음 줄에는 차례로 1번, 2번, …, n번 정점에 매달려 있는 열매의 개수가 주어진다. 다음 n-1개의 줄에는 트리의 각

www.acmicpc.net

<문제 풀이> DFS, BFS, 트리의 지름

 

각 정점에서 BFS를 돌려서 각 정점에서 시작했을 때 최대 거리를 구합니다.

최대 거리가 가장 큰 정점을 시작 정점으로 하면 됩니다.

+트리의 지름을 구하는 것과 동일합니다.

 

 

<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
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <deque>
using namespace std;
 
int n;
int vertex[10001];
vector<int> adj[10001];
int dist[10001];
int max_cnt = 0;
int start = 0;
void bfs() {
    for (int i = n; i >=1; i--) {
        fill(dist, dist + 10001, -1);
        queue<int> Q;
        Q.push(i);
        dist[i] = vertex[i];
        while (!Q.empty()) {
            int cur = Q.front(); Q.pop();
            if (dist[cur] >= max_cnt) {
                max_cnt = dist[cur];
                start = i;
            }
            for (auto& next : adj[cur]) {
                if (dist[next] != -1) continue;
                dist[next] = dist[cur] + vertex[next];
                Q.push(next);
            }
        }
    }
 
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> n;
    for (int i = 1; i <= n; i++) {
        cin >> vertex[i];
    }
    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    bfs();
    cout << max_cnt << " " << start;
    return 0;
}
 
 cs

 

반응형
저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 14675번] 단절점과 단절선  (0) 2021.12.19
[백준 2661번] 좋은수열  (0) 2021.12.16
[백준 1167번] 트리의 지름  (0) 2021.12.16
[백준 1967번] 트리의 지름  (0) 2021.12.13
[백준 2331번] 반복수열  (0) 2021.12.12
반응형

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

 

1167번: 트리의 지름

트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지

www.acmicpc.net

<문제 풀이> DFS

https://seokjin2.tistory.com/83

 

[백준 1967번] 트리의 지름

문제 링크:https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보..

seokjin2.tistory.com

1967번 트리의 지름 문제에서는 N제한이 10,000이기 때문에 모든 정점에 대해서 DFS or BFS를 돌려서 O(N^2)에 트리의 지름을 구할 수 있었지만
이문제는 N제한이 100,000이기 때문에 O(N^2)을 하면 시간 초과가 나게 된다.

 

이문제는 모든 정점에 대해서 DFS를 호출하지 않고 DFS를 2번 호출해서 문제를 해결할 수 있다.

 

[트리의 지름 알고리즘]

1. 임의의 정점 x에서 가장 멀리 떨어진 정점 u를 찾는다

2. 1에서 찾은 정점 u에서 가장 멀리 떨어진 정점 v를 찾는다

3. u - v가 트리의 지름이 된다.

 

<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
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <deque>
using namespace std;
 
vector<pair<int, int> > adj[100001];
bool visited[100001];
int n;
int maxDist = 0;
int start = 0;
void dfs(int u, int dist) {
    visited[u] = true;
    if (dist > maxDist) {
        start = u;
        maxDist = dist;
    }
    for (auto v : adj[u]) {
        if (visited[v.first])continue;
        dfs(v.first, dist + v.second);
    }
}
 
void solve() {
    dfs(1, 0);
    maxDist = 0;
    fill(visited, visited + 100001, 0);
    dfs(start, 0);
    cout << maxDist;
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int u; cin >> u;
        while (true) {
            int v, c;
            cin >> v;
            if (v == -1) break;
            cin >> c;
            adj[u].push_back({ v, c });
        }
    }
    solve();
 
 
    return 0;
}
 
 cs

 

반응형
저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 2661번] 좋은수열  (0) 2021.12.16
[백준 2132번] 나무 위의 벌레  (0) 2021.12.16
[백준 1967번] 트리의 지름  (0) 2021.12.13
[백준 2331번] 반복수열  (0) 2021.12.12
[백준 16920번] 확장 게임  (0) 2021.12.08
반응형

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

 

1967번: 트리의 지름

파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연

www.acmicpc.net

<문제 풀이> DFS, BFS

N <= 10,000 이기 때문에 O(N^2)으로 문제를 해결할 수 있습니다.

모든 정점에 대해서 DFS or BFS를 돌려서 거리의 최댓값을 계속 갱신하면 됩니다.

<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
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <deque>
using namespace std;
 
int n;
vector<pair<int, int> > adj[10001];
int dist[10001];
int res = 0;
void bfs() {
    for (int s = 1; s <= n; s++) {
        fill(dist, dist + 10001, -1);
        queue<int> Q;
        Q.push(s);
        dist[s] = 0;
        while (!Q.empty()) {
            int u = Q.front(); Q.pop();
            res = max(res, dist[u]);
            for (auto& v : adj[u]) {
                if (dist[v.first] != -1) continue;
                dist[v.first] = dist[u] + v.second;
                Q.push(v.first);
            }
        }
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> n;
    for (int i = 0; i < n - 1; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        adj[u].push_back({ v, c });
        adj[v].push_back({ u ,c });
    }
    bfs();
    cout << res;
    return 0;
}
 
 cs
반응형
저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 2132번] 나무 위의 벌레  (0) 2021.12.16
[백준 1167번] 트리의 지름  (0) 2021.12.16
[백준 2331번] 반복수열  (0) 2021.12.12
[백준 16920번] 확장 게임  (0) 2021.12.08
[백준 11967번] 불켜기  (0) 2021.12.04
반응형

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

 

2331번: 반복수열

첫째 줄에 반복되는 부분을 제외했을 때, 수열에 남게 되는 수들의 개수를 출력한다.

www.acmicpc.net

<문제 풀이> DFS

이문제는 dfs로 수열을 계속 구하다가 반복 횟수가 2 이상이면 종료하고 반복 횟수가 1인 수열의 개수를 세면 되는 간단한 문제입니다.

 

그런데 문제는 배열의 범위를 설정하는 것입니다.

 

문제에서 A <=9999이고 P <=5라고 했으니깐

처음 시작되는 수의 자릿수의 최대는 4자리입니다.

 

A = x1x2x3x4라고 하면

x1^5 <= 9^5 = 59049

x2^5 <= 9^5 = 59049

x3^5 <= 9^5 = 59049

x4^5 <= 9^5 = 59049

 

따라서 

x1^5 + x2^5 + x3^5 +x4^5 <= 236196 

 

위를 통해서 A로 만들 수 있는 다음 수는 아무리 커도 6자리를 넘지 못합니다.

 

그러면 만약에 6자리가 모두 9로 이루어졌다고 가정하고 다시 계산해보겠습니다.

 

A = x1x2x3x4x5x6라고 하면

x1^5 <= 9^5 = 59049

x2^5 <= 9^5 = 59049

x3^5 <= 9^5 = 59049

x4^5 <= 9^5 = 59049

x5^5 <= 9^5 = 59049

x6^5 <= 9^5 = 59049

 

따라서

x1^5 + x2^5 + x3^5 +x4^5  + x5^5 + x6^5 <= 354294

 

위를 통해서 6자리로 최대 6자리까지만 만들 수 있으니깐, 수의 최대 자릿수는 6자리를 넘지 못한다는 걸 알 수 있습니다.

 

 

 

 

 

<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
#include <iostream>
#include <string>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>
#include <utility>
#include <climits>
#include <deque>
using namespace std;
 
int arr[1000000];
 
int a, p;
 
int pow(int x, int n) {
    int temp = x;
    for (int i = 0; i < n - 1; i++) {
        x *= temp;
    }
    return x;
}
 
void dfs(int a) {
    int res = 0;
    while (a) {
        int r = a % 10;
        res += pow(r, p);
        a = a / 10;
    }
    if (arr[res] < 2) {
        arr[res]++;
        dfs(res);
    }
}
 
int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
 
    cin >> a >> p;
    arr[a]++;
    dfs(a);
    int cnt = 0;
    for (int i = 1; i <= 1000000; i++) {
        if (arr[i] == 1)cnt++;
    }
    cout << cnt;
 
    return 0;
}
 
 cs

 

반응형
저작자표시

'알고리즘 문제풀이 > 백준' 카테고리의 다른 글

[백준 1167번] 트리의 지름  (0) 2021.12.16
[백준 1967번] 트리의 지름  (0) 2021.12.13
[백준 16920번] 확장 게임  (0) 2021.12.08
[백준 11967번] 불켜기  (0) 2021.12.04
[백준 3197번] 백조의 호수  (0) 2021.12.02

+ Recent posts

티스토리툴바