펭로그

[C++] Codeforces Round #514 (Div. 2) - C. Sequence Transformation 본문

Study/PS(Algorithm)

[C++] Codeforces Round #514 (Div. 2) - C. Sequence Transformation

노랑펭귄 2018. 10. 6. 02:18

문제링크 : http://codeforces.com/contest/1059


C. Sequence Transformation


각 숫자들을 인수분해 하면 소수들의 곱으로 이루어진다.

입력 사이즈가 100만이기 때문에 100만의 제곱근 만큼인 1000까지의 소수를 구하고 그 소수들 중에서 가장 많은 배수들을 가지고 있는 소수를 추려내고 나머지 모든 수를 1로 출력, 그 소수의 제곱수가 아닌 숫자를 그 소수로 출력, 소수의 제곱수를 출력 하는 식으로 문제를 접근했는데.. 답은 맞게 나오겠지만 메모리 공간이 분명 초과되는듯 하다.


기존엔 문제를 이렇게 풀었으나 출력해서 규칙을 보니.. 2의 배수만 신경쓰면 되는 것을 발견했다.

3을 제외하고 전부 2로 출력되었으니 말이다..


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
// Codeforces Round #514 (Div. 2)
// C. Sequence Transformation
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
 
using namespace std;
 
struct node {
    int pnum;
    vector<int> factors;
 
    node(int num) : pnum(num) {}
 
    bool operator<(const node &a) const {
        // 사이즈가 같으면 큰 숫자 우선
        if (factors.size() == a.factors.size())
            return pnum < a.pnum;
        else
            return factors.size() < a.factors.size();
    }
};
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int input;
    cin >> input;
    if (input == 1) {
        cout << 1;
        return 0;
    }
 
    // 소수 리스트
    bool isPrime[101];
    memset(isPrime, true, sizeof(isPrime));
    vector<node> prime;
    // 입력 최대 값이 1,000,000이므로 최대 제곱근(100)까지만 소수 구함
    for (int i = 2; i <= 1000 && i <= input; i++) {
        if (isPrime[i]) {
            prime.push_back({i}); // 소수 저장
            for (int j = i; j <= input; j += i) {
                isPrime[j] = false;
                prime.back().factors.push_back(j); // 소수의 배수 저장
            }
        }
    }
    sort(prime.begin(), prime.end());
    // 가장 많은 factor를 가지고 있는 소수를 제외한 나머지는 1을 출력
    int size = prime.back().factors.size();
    int print1 = input - size;
    for (int i = 0; i < print1; i++)
        cout << 1 << ' ';
 
    // 소수 factor들의 마지막 숫자의 제곱수만 취함
    int result = prime.back().pnum;
    int cnt = 0;
    int root = prime.back().factors.back();
    while (root /= 2)
        cnt++;
    // 제곱수를 제외한 나머지
    int print2 = size - cnt;
 
    for (int i = 0; i < print2; i++)
        cout << result << ' ';
 
    // 소수의 제곱 순서대로 출력
    for (int i = 1; i <= cnt; i++)
        cout << pow(result, i) << ' ';
 
    return 0;
}
cs



그래서 2의 배수를 이용한 방법으로 아래와 같이 수정하면 된다.

처음부터 시뮬레이션으로 접근했으면 쉽게 풀 수 있었던 문제였다.

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
// Codeforces Round #514 (Div. 2)
// C. Sequence Transformation
#include <iostream>
#include <cmath>
 
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    int input;
    cin >> input;
    switch (input) {
        case 1:
            cout << "1";
            return 0;
        case 2:
            cout << "1 2";
            return 0;
        case 3:
            cout << "1 1 3";
            return 0;
    }
    int tmp = input;
    int cnt = 0;
    while (tmp /= 2)
        cnt++;
 
    int result = input;
    if(result % 2)
        result++;
    result /= 2;
    for (int i = 1; i <= result; i++)
        cout << "1 ";
    for(int i = 1; i <= input - result - cnt; i++)
        cout << "2 ";
    for (int i = 1; i <= cnt; i++)
        cout << pow(2, i) << " ";
 
    return 0;
}
cs


저작자표시

'Study > PS(Algorithm)' 카테고리의 다른 글

[C++] 백준 BOJ 9095 1,2,3 더하기  (0) 2018.10.06
[C++] 백준 BOJ 2583 영역 구하기  (0) 2018.10.06
[C++] Codeforces Round #514 (Div. 2) - A. Cashier  (0) 2018.10.06
[C++] 백준 BOJ 13458 시험 감독  (0) 2018.10.05
[C++] 백준 BOJ 1991 트리 순회  (0) 2018.10.03
'Study/PS(Algorithm)' Related Articles more
Comments