반응형

문제 출처 :


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



알고리즘 분석 :


문제 해결에 필요한 사항

1. 최소 힙

2. Priority Queue STL

3. MAP STL :: http://www.crocus.co.kr/604


이 문제는 해설을 보기전에 충분한 시간을 가지고 곰곰이 생각해보는 것이 좋다.


2,3,5,7이 있다고 보자.


처음에 arr배열에 값을 넣어줌과 동시에 최소 힙에도 값을 같이 넣어준다.

(arr :: 곱할 대상, 최소 힙 :: 곱해질 대상)


이 arr 배열을 작은 값이 먼저 나오도록 오름차순으로 정렬을 한 번 해주고

(물론 안해도 괜찮지만 힙에서 좀 더 시간을 아끼기 위해.)


최소 힙에서 값을 하나씩 꺼내며 그 값과 arr[]의 값을 for문을 통해 한번씩 곱해주고 


그 결과를 다시 최소 힙에 넣어준다.


이때 map STL을 이용하여 중복되는 값이 최소 힙에 또 들어가는지 확인하고 중복 되지 않는다면 그 값을 넣어준다.


            // k개를 넘어간 것에다가 현재 최대값보다 큰 값은 필요없다.
            if (q.size() + cnt > k && max < v)
                break;


이 코드의 의미는 주석과 같이 현재 k번째 값을 알고 싶은데 q.size() + cnt = 지금까지 카운트 해온 모든 값을 의미하고


q.size() + cnt > k && max < v라는 의미는 k번째를 넘어서는 값이기도 하며 v값이 최댓값을 넘긴다면


최소 힙에서 정답과 무관한 값이 계속들어가게 될 것을 방지하기 위해 저런 코드를 심어두었다.


저 코드가 없다면 메모리 초과를 받게 된다.



소스 코드 : 


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
#include <cstdio>
#include <queue>
#include <map>
#include <vector>
#include <algorithm>
#include <functional>
 
#define MAX(a,b) (a > b ? a : b)
#define ll long long
 
using namespace std;
 
ll arr[103];
 
int main()
{
    int n, k;
    scanf("%d %d"&n, &k);
 
    // 최소 힙으로 구현된 q
    priority_queue <ll, vector<ll>, greater<int>> q;
    map<ll, int> chk;
 
    for (int i = 0; i < n; i++) {
        scanf("%lld"&arr[i]);
        q.push(arr[i]);
    }
 
    sort(arr, arr + n);
 
    ll max = 0;
    int cnt = 0;
 
    while (!q.empty())
    {
        ll front = q.top();
        q.pop();
 
        cnt++;
 
        if (cnt == k)
        {
            printf("%lld\n", front);
            break;
        }
 
        for (int i = 0; i < n; i++)
        {
            ll v = front * arr[i];
 
            // k개를 넘어간 것에다가 현재 최대값보다 큰 값은 필요없다.
            if (q.size() + cnt > k && max < v)
                break;
 
            // 중복체크(이미 큐에 존재하는 것은 넣지 않는다.)
            if (chk[v] == 0)
            {
                max = MAX(max, v);
 
                chk[v] = 1;
                q.push(v);
            }
        }
    }
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>
Crocus


반응형

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

[12851번] 숨바꼭질 2  (0) 2017.02.28
[1697번] 숨바꼭질  (0) 2017.02.28
[1655번] 가운데를 말해요  (0) 2017.02.28
[11286번] 절대값 힙  (0) 2017.02.28
[1715번] 카드 정렬하기  (0) 2017.02.28