algospot : https://algospot.com/judge/problem/read/PASS486

github : https://github.com/junho0956/Algorithm/blob/master/algospot%20PASS486/algospot%20PASS486/%EC%86%8C%EC%8A%A4.cpp

 

** 시간제한 5000ms, 메모리제한 128MB **

 

이 문제를 푸는데에는 3가지 방법이 있습니다.

 

첫번째 방법

모든 수를 각각 약수를 다 구한다.

임의의 수 N 이 있을 때 1부터 sqrt(N)까지의 모든 수를 N에 mod 해보는 방법입니다.

이에 대해 각 수 당 시간복잡도는 sqrt(N)이 필요하고, 

첫번째 방법을 이용해서 구현을 해보지는 않았는데 수의 범위가 최대 1000만이니

1000만*sqrt(N) 은 주어진 시간이 5초라서.. 사실 통과할것 같기는 합니다.

하지만 보통 이렇게 큰 시간을 허용해주지 않으니 다음 방법을 확인해보겠습니다.

 

두번째 방법

소수 알고리즘인 에라토스테네스의 체를 이용해서

각 수의 최소약수를 미리 구해놓으면 소인수분해를 빠르게 할 수 있고,

소인수분해를 이용해서 약수의 갯수를 빠르게 알 수 있습니다.

저는 이 방법을 통해서 800ms 로 해결했습니다.

종만북을 통해서 에라토스테네스의 체로 소인수분해를 할 수 있는 방법을 처음알았는데

감탄하고 갑니다..

 

세번째 방법은 완전히 소인수분해 하지 않고도 약수의 수를 셀 수 있는 방법인데,

두번째 방법보다 더욱 빠르다고 합니다.

아직 이해를 못해서 좀더 공부하고 차후 수정하겠습니다.

 

아래는 두번째 방법으로

에라토스테네스의체 -> 소인수분해 -> 약수의 갯수 찾는 순서로 구현되어 있습니다.

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
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
using namespace std;
const int MAXNUM = 1e7 + 1;
 
int minFactor[MAXNUM];
int numFactor[MAXNUM];
 
void Factor() {
    for (int i = 0; i < MAXNUM; i++) minFactor[i] = i;
    for (int i = 2; i <= sqrt(MAXNUM); i++) {
        if (minFactor[i] == i) {
            for (int k = i * i; k < MAXNUM; k += i) {
                if (minFactor[k] == k) minFactor[k] = i;
            }
        }
    }
 
    for (int i = 2; i < MAXNUM; i++) {
        int n = i;
        int ans = 1;
        int cnt = 0;
        int num = minFactor[i];
        while (n > 1) {
            if (minFactor[n] == num) cnt++;
            else {
                ans *= (cnt + 1);
                cnt = 1;
                num = minFactor[n];
            }
            n /= minFactor[n];
        }
        ans *= (cnt + 1);
        numFactor[i] = ans;
    }
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    Factor();
 
    int T; cin >> T;
    while (T--) {
        int n, lo, hi;
        cin >> n >> lo >> hi;
        int answer = 0;
        for (int i = lo; i <= hi; i++) {
            if (numFactor[i] == n) answer++;
        }
        cout << answer << "\n";
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > algospot' 카테고리의 다른 글

algospot FOSSIL  (0) 2020.02.26
algospot RATIO  (0) 2020.02.25
algospot LOAN  (0) 2020.02.24
algospot ROOTS  (0) 2020.02.24
algospot FESTIVAL  (0) 2019.10.27

algospot : https://algospot.com/judge/problem/read/FOSSIL

github : https://github.com/junho0956/Algorithm/blob/master/algospot%20FOSSIL/algospot%20FOSSIL/%EC%86%8C%EC%8A%A4.cpp

 

 

algospot FOSSIL 문제입니다. 

삼분탐색을 통해서 해결한 문제이고 기하문제를 처음풀어보는거라서

개념다잡는데 시간이 좀 걸렸습니다.

 

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
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
using namespace std;
 
struct point {
    double x, y;
};
typedef vector<pair<point, point> > vp;
 
void decompose(vp & upper, vp& lower, vector<point>& a) {
    int n = a.size();
    for (int i = 0; i < n; i++) {
        if (a[i].x < a[(i + 1) % n].x) {
            lower.push_back({ a[i], a[(i + 1) % n] });
        }
        else {
            upper.push_back({ a[i], a[(i + 1) % n] });
        }
    }
}
 
double minX(vector<point>& a) {
    double ans = 1e9;
    for (int i = 0; i < a.size(); i++) {
        ans = min(ans, a[i].x);
    }
    return ans;
}
 
double maxX(vector<point>& a) {
    double ans = -1;
    for (int i = 0; i < a.size(); i++) {
        ans = max(ans, a[i].x);
    }
    return ans;
}
 
bool between(pair<point,point>& line, double x) {
    return (line.first.x <= x && x <= line.second.x) || (line.second.x <= x && x <= line.first.x);
}
 
double calY(point& a, point& b, double x) {
    // 직선의 방정식
    // y = m(x-x1)+y1
    return (b.y - a.y) / (b.x - a.x) * (x - a.x) + a.y;
}
 
// 주어진 x좌표에 대해서 껍질들의 y좌표를 확인하여 그 차액(길이)를 리턴한다.
double len(vp& upper, vp& lower, double x) {
    double minY, maxY;
    minY = 1e9, maxY = -1;
    // 위껍질의 선분들을 확인하여 주어진 x와 겹치는 y의 최솟값을 찾는다
    for (int i = 0; i < upper.size(); i++) {
        // 위껍질의 선분이 현재 x점의 수직선과 마주치는지 확인한다
        if (between(upper[i], x)) {
            // 만약 마주친다면(겹쳐진다면) 직선의 방정식 공식을 이용하여 x에 대한 y점을 가져온다.
            minY = min(minY, calY(upper[i].first, upper[i].second, x));
        }
    }
 
    // 아래껍질의 선분들을 확인하여 주어진 x와 겹치는 y의 최댓값을 찾는다
    for (int i = 0; i < lower.size(); i++) {
        // 위껍질의 선분이 현재 x점의 수직선과 마주치는지 확인한다
        if (between(lower[i], x)) {
            // 만약 마주친다면(겹쳐진다면) 직선의 방정식 공식을 이용하여 x에 대한 y점을 가져온다.
            maxY = max(maxY, calY(lower[i].first, lower[i].second, x));
        }
    }
 
    // 길이를 반환한다
    return minY - maxY;
}
 
double solve(vp& upper, vp& lower, vector<point>& a, vector<point>& b) {
    double lo = max(minX(a), minX(b));
    double hi = min(maxX(a), maxX(b));
    // 겹치지 않는 경우
    if (hi < lo) return 0;
 
    for (int i = 0; i < 100; i++) {
        double lp = (2 * lo + hi) / 3;
        double rp = (lo + 2 * hi) / 3;
        if (len(upper, lower, lp) < len(upper, lower, rp))
            lo = lp;
        else
            hi = rp;
    }
 
    // 경우에 따라 교집합의 길이가 아닌 부분이 반환될 수 있으니 (음수) 조건을 주어서 반환한다
    return max(0.0, len(upper, lower, hi));
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    int T; cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
 
        vector<point> poly1, poly2;
 
        for (int i = 0; i < n; i++) {
            point a;
            cin >> a.x >> a.y;
            poly1.push_back(a);
        }
        for (int i = 0; i < m; i++) {
            point a;
            cin >> a.x >> a.y;
            poly2.push_back(a);
        }
 
        // 아래, 위 껍질을 구분해준다
        // 껍질의 구분으로 받게 될 값들은 "선분" 이 기준이 된다
        vp upper, lower;
 
        decompose(upper, lower, poly1);
        decompose(upper, lower, poly2);
 
        // 껍질을 구분했으면 삼분탐색을 통해 문제를 해결한다
        cout << fixed;
        cout.precision(10);
        cout << solve(upper, lower, poly1, poly2) << "\n";
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > algospot' 카테고리의 다른 글

algospot PASS486  (0) 2020.02.27
algospot RATIO  (0) 2020.02.25
algospot LOAN  (0) 2020.02.24
algospot ROOTS  (0) 2020.02.24
algospot FESTIVAL  (0) 2019.10.27

algospot : https://algospot.com/judge/problem/read/RATIO

github : https://github.com/junho0956/Algorithm/blob/master/algospot%20RATIO/algospot%20RATIO/%EC%86%8C%EC%8A%A4.cpp

 

algospot RATIO 문제입니다.

(백준에서 같은 문제를 찾으라면 https://www.acmicpc.net/problem/1072)

이분탐색을 이용하여 쉽게 해결할 수 있었습니다.

 

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 <vector>
#include <queue>
#include <stack>
#include <algorithm>
#include <set>
#include <cmath>
#include <limits>
using namespace std;
 
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
 
    /*
    싸비는 윈도우XP 운영체제에 포함되어 있는 스파이더 카드게임을 매우 좋아한다. 
    처음에는 지는 경우가 있었는데, 점점 연습을 함에 따라 필승법을 발견하였고 매번 승리를 하게 되었다.
    스파이더 게임을 하면 플레이어에 대한 정보가 다음과 같이 주어지는데
    싸비는 이것을 보다 표시되고 있는 승률을 1%이상 올리기 위해선 최소한 몇 번의 연승이 필요한지 의구심이 들었다.
 
    플레이 횟수 : N
    승리 횟수 : M(Z %)
 
    여기서 Z%의 경우 소수점을 제외한 부분의 승률이다.
    즉, 승률이 88.68% 일 경우 Z = 88% 이다.
 
    N, M이 주어졌을 때, Z를 올리기 위한 최소한의 연승횟수가 필요한지 구하는 프로그램을 작성하라.
    여기서 답이 되는 연승횟수는 2,000,000,000 이하라고 가정한다.
    */
 
    /*
    입력의 첫번째 줄에는 테스트 케이스의 개수 T가 입력되고,
    다음 줄 부터 한줄에 하나씩 T개의 테스트 케이스가 입력된다.
    테스트케이스는 두 개의 숫자로 이루어진다.
    처음에 들어오는 숫자는 스파이더를 플레이를 한 횟수N(1<=N<=1,000,000,000)를 의미하며
    나중에 들어온 숫자는 승리한 횟수M(0<=M<=N)를 의미한다.
    */
 
    int T; cin >> T;
    while (T--) {
        long long n, m;
        cin >> n >> m;
        long long standRate = (m * 100) / n;
        if (standRate >= 99) {
            cout << "-1\n";
            continue;
        }
        standRate++;
        // 연승횟수는 20억 이하
        long long left, right;
        left = 0, right = 2e9 + 1;
        for (int i = 0; i < 100; i++) {
            long long mid = (left + right) / 2;
            long long rate = ((m+mid) * 100) / (n + mid);
            if (rate >= standRate)
                right = mid;
            else
                left = mid;
        }
        cout << right << "\n";
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > algospot' 카테고리의 다른 글

algospot PASS486  (0) 2020.02.27
algospot FOSSIL  (0) 2020.02.26
algospot LOAN  (0) 2020.02.24
algospot ROOTS  (0) 2020.02.24
algospot FESTIVAL  (0) 2019.10.27

algospot : https://algospot.com/judge/problem/read/LOAN

github : https://github.com/junho0956/Algorithm/blob/master/algospot%20LOAN/algospot%20LOAN/%EC%86%8C%EC%8A%A4.cpp

 

algospot LOAN 문제입니다.

이분법을 이용하였으며, 초기 이분법 값을 잡아주는 방법과 대출 잔금을 계산하는 방법을 알고 계신다면

해결할 수 있습니다.

 

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
/*
집을 떠나 혼자 살게 된 재훈이는 회사 근처의 전세집을 알아보고 있습니다.
전세금은 N원인데, 재훈이는 이것을 연이율 P%로 대출받을 수 있습니다.
재훈이는 M개월 동안 매달 일정액 C원씩을 갚으려고 합니다.
 
대출의 잔금은 대출 기간 동안 다음과 같이 변화합니다.
 
ᆞ대출의 잔금은 대출 금액 N원에서 시작합니다.
ᆞ한 달이 지날 때마다 대출 잔금이 월 이자 (P/12)% 만큼 불어납니다.
ᆞ이자가 추가된 다음 월 상환액 C를 대출 잔금에서 제합니다.
M개월 걸려 모든 대출 금액을 갚기 위해서는 한 달에 최소 얼마씩을 갚아야 할까요?
*/
 
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
// 매달 C원씩 갚았을 때 남게 되는 대출 잔금을 반환합니다.
 
double balance(double money, int month, double rates, double C) {
    for (int i = 0; i < month; i++) {
        money *= (1 + (rates / 12 / 100));
        money -= C;
    }
    return money;
}
 
// 한달에 갚아야 하는 최소 금액을 반환합니다
double payment(double money, int month, double rates) {
    double lo = 0;
    double hi = money * (1 + (rates / 12 / 100));
 
    for (int i = 0; i < 100; i++) {
        double mid = (lo + hi) / 2;
        if (balance(money, month, rates, mid) <= 0) {
            hi = mid;
        }
        else {
            lo = mid;
        }
    }
 
    return hi;
}
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
 
    /*
    입력의 첫 줄에는 테스트 케이스의 수 T(<= 50)가 주어집니다.
    각 테스트 케이스는 3개의 수 N, M, P(1 <= N <= 100,000,000, 1 <= M <= 120, 0 < P <= 50)으로 주어집니다.
    N과 P는 실수이며, M은 정수입니다.
    */
 
    int T; cin >> T;
    while (T--) {
        // N : 대출금액
        // M : M개월
        // P : 연이율
        double N, P;
        int M;
        cin >> N >> M >> P;
 
        /*
        각 테스트 케이스마다 한 줄에 한 달마다 상환할 금액 C를 출력합니다.
        10-7 이하의 절대/상대 오차가 있는 답은 정답으로 인정됩니다.
        */
        cout << fixed;
        cout.precision(10);
        cout << payment(N, M, P) << endl;
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > algospot' 카테고리의 다른 글

algospot PASS486  (0) 2020.02.27
algospot FOSSIL  (0) 2020.02.26
algospot RATIO  (0) 2020.02.25
algospot ROOTS  (0) 2020.02.24
algospot FESTIVAL  (0) 2019.10.27

+ Recent posts

티스토리툴바