'알고리즘 문제풀이/백준' 카테고리의 글 목록 (17 Page)

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

6118번: 숨바꼭질

문제 재서기는 수혀니와 교외 농장에서 숨바꼭질을 하고 있다. 농장에는 헛간이 많이 널려있고 재서기는 그 중에 하나에 숨어야 한다. 헛간의 개수는 N(2 <= N <= 20,000)개이며, 1 부터 샌다고 하자. 재서기는 수혀니가 1번 헛간부터 찾을 것을 알고 있다. 모든 헛간은 M(1<= M <= 50,000)개의 양방향 길로 이어져 있고, 그 양 끝을 A_i 와 B_i(1<= A_i <= N; 1 <= B_i <= N; A_i != B_i)로 나타낸

www.acmicpc.net

<문제 풀이> 그래프, BFS

무방향 그래프의 최단거리를 BFS로 갱신하면 되는데, 1번 정점으로부터 거리가 크거나 같을 때만 next를 push 해주면 된다.

[next 정점 기준]

1번 정점으로부터 거리가 같을때는 정답 vector에 그냥 push 하고
1번 정점으로부터 거리가 멀어지면 정답 vector를 초기화시키고 push 하면 된다.

<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 <algorithm>
#include <vector>
#include <queue>
using namespace std;
 
int n, m;
int visited[20001];
vector<vector<int> > adj(20001);
vector<int> ans;
int cnt = 1;
 
void bfs() {
    queue<int> q;
    q.push(1);
    visited[1] = 1;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (auto& next : adj[cur]) {
            if (visited[next])continue;
            if (visited[cur] + 1 == cnt) {
                visited[next] = visited[cur] + 1;
                q.push(next);
                ans.push_back(next);
            }
            else if (visited[cur] + 1 > cnt) {
                ans.clear();
                visited[next] = visited[cur] + 1;
                q.push(next);
                cnt = visited[next];
                ans.push_back(next);
                
            }
        }
    }
}
 
int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    bfs();
    sort(ans.begin(), ans.end());
    cout << ans[0] << " " << visited[ans[0]] - 1 <<" "<< ans.size();
 
    return 0;
}
Colored by Color Scripter

cs

저작자표시

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

[백준 11725번] 트리의 부모 찾기 (0)	2020.03.26
[백준 1043번] 거짓말 (0)	2020.03.25
[백준 5567번] 결혼식 (0)	2020.03.22
[백준 2606번] 바이러스 (0)	2020.03.22
[백준 1260번] DFS와 BFS (0)	2020.03.22

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

5567번: 결혼식

문제 상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다. 상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 상근이의 동기의 수 n (2 ≤ n ≤ 500)이 주어진다. 둘째 줄에는 리스트의 길이 m (1 ≤ m

www.acmicpc.net

<문제 풀이> 그래프, BFS

자신의 친구와, 친구의 친구까지 초대하는 거니깐 BFS로 자신의 위치인 1번 정점에서 거리가 최대 3까지만 탐색하면 됩니다.

무방향 그래프이므로 인접 리스트를 양방향으로 갱신해줍니다.

거리를 체크하는 방법은 큐에 next를 삽입하고 visited배열로 방문 체크할 때 다음과 같이 거리에 대한 정보를 넣어주면 됩니다.

visited[next] = visited[cur] + 1;

<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

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int n, m;
int visited[501];
vector<vector<int> > adj(501);
int cnt = 0;
 
void bfs() {
    queue<int> q;
    q.push(1);
    visited[1] = 1;
    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        for (auto& next : adj[cur]) {
            if (visited[next] || visited[cur] >= 3)continue;
            q.push(next);
            visited[next] = visited[cur] + 1;
            cnt++;
        }
    }
}
 
int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    bfs();
    cout << cnt;
    
 
    return 0;
}
Colored by Color Scripter

cs

저작자표시

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

[백준 1043번] 거짓말 (0)	2020.03.25
[백준 6118번] 숨바꼭질 (0)	2020.03.23
[백준 2606번] 바이러스 (0)	2020.03.22
[백준 1260번] DFS와 BFS (0)	2020.03.22
[백준 11724번] 연결 요소의 개수 (0)	2020.03.21

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

2606번: 바이러스

첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.

www.acmicpc.net

<문제 풀이> 그래프 탐색, DFS, BFS

무방향 그래프로 인접 리스트를 만들고 정점 1에서 DFS를 돌려서 next를 호출할 때마다 cnt++을 해주면 됩니다.

<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

#include <iostream>
#include <vector>
using namespace std;
 
int n, m;
bool visited[101];
vector<vector<int> > adj(101);
int cnt = 0;
void dfs(int cur) {
    visited[cur] = true;
    for (auto& next : adj[cur]) {
        if (visited[next]) continue;
        dfs(next);
        cnt++;
    }
}
 
int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
 
    dfs(1);
    cout << cnt;
    
 
    return 0;
}
Colored by Color Scripter

cs

저작자표시

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

[백준 6118번] 숨바꼭질 (0)	2020.03.23
[백준 5567번] 결혼식 (0)	2020.03.22
[백준 1260번] DFS와 BFS (0)	2020.03.22
[백준 11724번] 연결 요소의 개수 (0)	2020.03.21
[백준 1655번] 가운데를 말해요 (0)	2020.03.19

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

1260번: DFS와 BFS

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

www.acmicpc.net

<문제 풀이> 그래프 탐색, DFS, BFS

정점 번호가 작은 것부터 방문이니깐 인접 리스트를 정렬 후 기본적인 DFS, BFS를 구현하면 되는 문제입니다. DFS에선 방문 체크를 할 때 현재 정점을 출력하면 되고 BFS에서는 큐에서 꺼낼 때 출력하면 됩니다.

(DFS 호출하고 BFS 호출하기 전에 visited 배열 0으로 초기화)

<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 <algorithm>
#include <vector>
#include <queue>
using namespace std;
 
bool visited[1001];
vector<vector<int> > adj(1001);
int n, m, start;
 
void dfs(int cur) {
    cout << cur << " ";
    visited[cur] = true;
    for (auto& next : adj[cur]) {
        if (visited[next])continue;
        dfs(next);
    }
}
void bfs(int cur) {
    queue<int> q;
    q.push(cur);
    visited[cur] = true;
    while (!q.empty()) {
        cur = q.front();
        cout << cur << " ";
        q.pop();
        for (auto& next : adj[cur]) {
            if (visited[next])continue;
            q.push(next);
            visited[next] = true;
        }
    }
}
int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m >> start;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= n; i++) sort(adj[i].begin(), adj[i].end());
 
    dfs(start);
 
    cout << "\n";
    fill(visited, visited + 1001, 0);
    
    bfs(start);
 
 
    return 0;
}
Colored by Color Scripter

cs

저작자표시

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

[백준 5567번] 결혼식 (0)	2020.03.22
[백준 2606번] 바이러스 (0)	2020.03.22
[백준 11724번] 연결 요소의 개수 (0)	2020.03.21
[백준 1655번] 가운데를 말해요 (0)	2020.03.19
[백준 2696번] 중앙값 구하기 (0)	2020.03.19

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

11724번: 연결 요소의 개수

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

www.acmicpc.net

<문제 풀이> 그래프 이론, DFS, BFS

무방향 그래프이므로 인접 리스트를 u -> v, v -> u 둘 다 갱신하고 기본적인 dfs를 돌리면 된다.

<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

#include <iostream>
#include <vector>
using namespace std;
 
bool visited[1001];
vector<vector<int> > adj(1001);
int n, m;
 
void dfs(int cur) {
    for (auto& next : adj[cur]) {
        if (visited[next])continue;
        visited[next] = true;
        dfs(next);
    }
}
 
int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        if (visited[i])continue;
        dfs(i);
        cnt++;
    }
    cout << cnt;
 
    return 0;
}
Colored by Color Scripter

cs

 

저작자표시

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

[백준 2606번] 바이러스 (0)	2020.03.22
[백준 1260번] DFS와 BFS (0)	2020.03.22
[백준 1655번] 가운데를 말해요 (0)	2020.03.19
[백준 2696번] 중앙값 구하기 (0)	2020.03.19
[백준 2014번] 소수의 곱 (0)	2020.03.13

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

1655번: 가운데를 말해요

첫째 줄에는 수빈이가 외치는 정수의 개수 N이 주어진다. N은 1보다 크거나 같고, 100,000보다 작거나 같은 자연수이다. 그 다음 N줄에 걸쳐서 수빈이가 외치는 정수가 차례대로 주어진다. 정수는 -10,000보다 크거나 같고, 10,000보다 작거나 같다.

www.acmicpc.net

<문제 풀이> 우선순위 큐

https://seokjin2.tistory.com/37

[백준 2696번] 중앙값 구하기

문제 링크: https://www.acmicpc.net/problem/2696 2696번: 중앙값 구하기 문제 어떤 수열을 읽고, 홀수번째 수를 읽을 때 마다, 지금까지 입력받은 값의 중앙값을 출력하는 프로그램을 작성하시오. 예를 들어, 수..

seokjin2.tistory.com

백준 2696번 에서는 홀수 번째 수를 읽었을 때만 중앙값을 출력해주었는데 1655번은 짝수 번째 수를 읽었을 때도 중앙값을 출력해주도록 추가해주면 됩니다.

짝수 번째 수를 읽었을 때는 최대 힙과 최소 힙 중에 사이즈가 큰 힙에 top과 이전에 구했던 중앙값 중 작은 값을 출력하면 됩니다.

왜냐하면 2696번 알고리즘을 그대로 적용하면 짝수 번째 수를 읽었을 때 중앙값을 기준으로 했을때 사이즈가 큰 힙 쪽에 원소가 더 치우쳐져 있으므로 사이즈 큰 쪽에 top을 가운데 수로 택해야 합니다.

ex) maxHip(1, 2) , mid(3), minHip(4) -> 여기서 2를 택해서 2 와 3의 최솟값을 출력

[알고리즘]

1. 최대 힙과 최소 힙을 준비한다.

2. 첫 번째 수를 중앙값으로 한다.

3. 두 번째부터 입력받은 수를 중앙값과 비교해서 작으면 최대 힙, 크면 최소 힙에 push한다.

4. 홀수 번째라면 최대 힙과 최소 힙 중에 사이즈가 작은 힙에 중앙값을 push 하고 그리고 힙 중에 사이즈가 큰 힙의 top을 중앙값으로 한다.

5. 짝수 번째라면 최대 힙과 최소 힙 중에 사이즈가 큰 힙에 top과 최근에 구했던 중앙값 중 작은 값을 출력해주면 된다.

<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 <queue>
using namespace std;
 
int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
    int m;
    cin >> m;
    int data;
    int mid;
    priority_queue<int> max_pq;
    priority_queue<int, vector<int>, greater<int> > min_pq;
    vector<int> ans;
    cin >> data;
    mid = data;
    ans.push_back(mid); //1개 일때는 그 수가 mid
    for (int i = 2; i <= m; i++) {
        cin >> data;
        if (data < mid)max_pq.push(data); //data를 mid 보다 작으면 최대힙 크면 최소힙에 넣는다
        else min_pq.push(data);
        int max_pq_size = max_pq.size();
        int min_pq_size = min_pq.size();
        if (i % 2 == 1) { //홀수 번째 수를 읽을 때 마다
            if (max_pq_size < min_pq_size) { //최대 힙과 최소 힙 중에 사이즈가 작은 힙에 mid를 push
                max_pq.push(mid);
                max_pq_size++;
            }
            else {
                min_pq.push(mid);
                min_pq_size++;
            }
 
            if (max_pq_size > min_pq_size) { // 힙 중에 사이즈가 큰 힙의 top이 mid가 됨
                mid = max_pq.top();
                max_pq.pop();
            }
            else {
                mid = min_pq.top();
                min_pq.pop();
            }
            ans.push_back(mid);
        }
        else {//짝수 번쨰 수를 읽을 때는 최대 힙과 최소 힙중에 사이즈가 큰 쪽의 top과 mid중 작은값을 출력
            if (max_pq_size > min_pq_size) ans.push_back(min(max_pq.top(), mid));
            else ans.push_back(min(min_pq.top(), mid));
        }
    }
    for (auto& e : ans) cout << e << "\n";
 
    return 0;
}
Colored by Color Scripter

cs

저작자표시

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

[백준 1260번] DFS와 BFS (0)	2020.03.22
[백준 11724번] 연결 요소의 개수 (0)	2020.03.21
[백준 2696번] 중앙값 구하기 (0)	2020.03.19
[백준 2014번] 소수의 곱 (0)	2020.03.13
[백준 2075번] N번째 큰 수 (0)	2020.03.11

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

2696번: 중앙값 구하기

문제 어떤 수열을 읽고, 홀수번째 수를 읽을 때 마다, 지금까지 입력받은 값의 중앙값을 출력하는 프로그램을 작성하시오. 예를 들어, 수열이 1,5,4,3,2 이면, 홀수번째 수는 1번째 수, 3번째 수, 5번째 수이고, 1번째 수를 읽었을 때 중앙값은 1, 3번째 수를 읽었을 때는 4, 5번째 수를 읽었을 때는 3이다. 입력 첫째 줄에 테스트 케이스의 개수 T(1<=T<=1,000)가 주어진다. 각 테스트 케이스의 첫째 줄에는 수열의 크기 M(1<=M<=

www.acmicpc.net

<문제 풀이> 우선순위 큐

수를 입력받을 때마다 중앙값을 찾는 방법은 매 순간 정렬해서 가운데 수를 구하는 방법도 있지만 이는 매 순간 정렬하는데 O(nlogN)이 걸립니다. 최대 힙과 최소 힙을 이용하면 매 순간 정렬하지 않고 O(logN)에 중앙값을 구할 수 있습니다.

아이디어는 중앙값을 기준으로 왼쪽엔 중앙값보다 크기가 작거나 같은 수로 이루어진 최대 힙을 두고, 오른쪽엔 중앙값 보다 크기가 크거나 같은 수로 이루어진 최소 힙을 둡니다. 그리고 홀수 번째 수를 읽을 때마다 중앙값을 힙 사이즈가 작은 쪽에 push 한 뒤, 다시 힙 사이즈가 큰 것에 top을 중앙값으로 하면 됩니다. (중앙값을 기준으로 양 옆에 수의 개수를 일치시키는 느낌)

[알고리즘]

1. 최대 힙과 최소 힙을 준비한다.

2. 첫 번째 수를 중앙값으로 한다.

3. 두 번째부터 입력받은 수를 중앙값과 비교해서 작으면 최대 힙, 크면 최소 힙에 push한다.

4. 홀수 번째라면 최대 힙과 최소 힙 중에 사이즈가 작은 힙에 중앙값을 push 하고 그리고 힙 중에 사이즈가 큰 힙의 top을 중앙값으로 한다.

<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 <queue>
using namespace std;
 
int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
 
    int test_case;
    cin >> test_case;
    while (test_case--) {
        int m;
        cin >> m;
        int data;
        int mid;
        priority_queue<int> max_pq;
        priority_queue<int, vector<int>, greater<int> > min_pq;
        vector<int> ans;
        cin >> data;
        mid = data;
        ans.push_back(mid); //1개 일때는 그 수가 mid
        for (int i = 2; i <= m; i++) {
            cin >> data;
            if (data < mid)max_pq.push(data); //data를 mid 보다 작으면 최대힙 크면 최소힙에 넣는다
            else min_pq.push(data);
            if (i % 2 == 1) { //홀수 번째 수를 읽을 때 마다
                int max_pq_size = max_pq.size();
                int min_pq_size = min_pq.size();
                if (max_pq_size < min_pq_size) { //최대 힙과 최소 힙 중에 사이즈가 작은 힙에 mid를 push
                    max_pq.push(mid);
                    max_pq_size++;
                }
                else {
                    min_pq.push(mid);
                    min_pq_size++;
                }
 
                if (max_pq_size > min_pq_size) { // 힙 중에 사이즈가 큰 힙의 top이 mid가 됨
                    mid = max_pq.top();
                    max_pq.pop();
                }
                else {
                    mid = min_pq.top();
                    min_pq.pop();
                }
                ans.push_back(mid);
            }
        }
        int size = ans.size();
        cout << size << "\n";
        for (int i = 1; i <= size; i++) {
            if (i != 1 && i % 10 == 1)cout << '\n';
            cout << ans[i-1] << " ";
        }
        cout << "\n";
    }
 
    return 0;
}
Colored by Color Scripter

cs

저작자표시

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

[백준 11724번] 연결 요소의 개수 (0)	2020.03.21
[백준 1655번] 가운데를 말해요 (0)	2020.03.19
[백준 2014번] 소수의 곱 (0)	2020.03.13
[백준 2075번] N번째 큰 수 (0)	2020.03.11
[백준 1715번] 카드 정렬하기 (0)	2020.03.11

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

2014번: 소수의 곱

첫째 줄에 K(1 ≤ K ≤ 100), N(1 ≤ N ≤ 100,000)이 주어진다. 다음 줄에는 K개의 소수가 오름차순으로 주어진다. 같은 소수가 여러 번 주어지는 경우는 없으며, 주어지는 소수는 모두 541보다 작거나 같은 자연수이다.

www.acmicpc.net

<문제 풀이> 우선순위 큐

각 소수에 대해서 K개의 소수를 계속 곱해 나가면 모든 소수의 곱을 구할 수 있는데, 여기서 중복 없이 구해서 최소 힙에 넣고 N 번째로 작은 수를 구하면 됩니다.

모든 소수의 곱을 구할 때 중복을 제거하는 방법은 가장 마지막에 곱해졌던 소수보다 작거나 같은 소수까지만 곱해주면 됩니다.

예를 들어

마지막에 곱해진 소수 2, 3, 5가 있을 때 각 소수에 K개의 소수인 2, 3, 5를 곱했을 때 2 * 3, 2 * 5, 3 * 5는 모두 중복입니다. 마지막에 곱해지는 수보다 큰 수를 곱하는 것은 어차피 뒤에서 한 번 더 곱해지기 때문에 더 곱해줄 필요가 없습니다.
2 x 2 | 3 x 2 | 5 x 2
2 x 3 | 3 x 3 | 5 x 3

2 x 5 | 3 x 5 | 5 x 5

<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

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
 
#define MAX (long long)2 << 31
int main(void) {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int k, n;
    cin >> k >> n;
    priority_queue<long long, vector<long long>, greater<long long> > pq;
    vector<int> plist;
    for (int i = 0; i < k; i++) {
        int p;
        cin >> p;
        plist.push_back(p);
        pq.push(p);
    }
    int cnt = 0;
    long long cur = 0;
    while (n--) {
        cur = pq.top();
        pq.pop();
        for (auto& p : plist) {
            if ((long long)p * cur >= MAX)break;
            pq.push(p * cur);
            if (cur % p == 0) break; //중복 제거
        }
    }
    cout<<cur;
 
}
Colored by Color Scripter

cs

 

저작자표시

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

[백준 1655번] 가운데를 말해요 (0)	2020.03.19
[백준 2696번] 중앙값 구하기 (0)	2020.03.19
[백준 2075번] N번째 큰 수 (0)	2020.03.11
[백준 1715번] 카드 정렬하기 (0)	2020.03.11
[백준 1002번] 터렛 (0)	2020.03.11

슥지니의 코딩노트