Strong Root

짝맞추기(MEETING) 정답 코드

뿌리튼튼 CS/Algorithm2015. 2. 26. 11:01

난이도 ★☆☆☆☆


문제를 보시려면 여기를 클릭




틀리기 쉬운 입출력 예제

입력

출력 

4

1

0

0

1

-1

-1

4

1 2 3 4

5 3 1 6

3

-1 2 -3

3 -2 1

0

0

5

4




힌트

 정렬만 하면 끝나는 매우 쉬운 문제

 → 'algorithm'의 'sort()' 함수를 사용하면 매우 간단하다.



이하는 코드입니다.


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
#include <stdio.h>
#include <algorithm>
#include <vector>
 
#define ABS(a) (((a) < 0) ? ((a)*(-1)) : (a))
 
#pragma warning(disable:4996)
 
using namespace std;
 
int main() {
    int T;
    scanf("%d\n", &T);
 
    while (T-- > 0) {
        int N;
        scanf("%d", &N);
 
        // get men
        vector<int> men;
        for (int i = 0; i < N; i++) {
            int tmp;
            scanf("%d", &tmp);
            men.push_back(tmp);
        }
 
        // get women
        vector<int> women;
        for (int i = 0; i < N; i++) {
            int tmp;
            scanf("%d", &tmp);
            women.push_back(tmp);
        }
 
        // sort
        sort(men.begin(), men.end());
        sort(women.begin(), women.end());
 
        // get sum
        int sum = 0;
        for (int i = 0; i < N; i++) {
            sum += ABS(men[i] - women[i]);
        }
 
        // print
        printf("%d\n", sum);
    }
 
    return 0;
}
cs

저작자표시 비영리 동일조건

'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글

게임판 덮기(BOARDCOVER) 정답 코드  (0) 2015.02.28
콘서트(CONCERT) 정답 코드  (1) 2015.02.26
달팽이(SNAIL) 정답 코드  (0) 2015.02.24
Coin Change(COINS) 정답 코드  (0) 2015.02.23
최소, 최대 정사각형 찾기 1(MMRECT1) 정답 코드  (0) 2015.02.16

달팽이(SNAIL) 정답 코드

뿌리튼튼 CS/Algorithm2015. 2. 24. 17:08

난이도 ★★★☆☆


문제를 보시려면 여기를 클릭




틀리기 쉬운 입출력 예제

입력

출력 

4

1 1

1000 1000

1000 500

1000 600

1.0000000000

1.0000000000

0.0000000000

0.9999980550




힌트

 고등학교 수학문제이지만 계산과정에서 오버플로우가 난다.

 → 분자 분모가 각각 매우 크므로, 따로 계산하지말고 한번에 계산하여 큰값이 존재할 수 없도록 구현한다.



이하는 코드입니다.


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
#include <stdio.h>
#include <math.h>
 
#pragma warning(disable:4996)
 
// Px = (mCx * 3 ^ x) / 4 ^ m
double getProb(int m, int winCount) {
    double ret = 1.0;
 
    // x번 / x번
    for (int i = m, j = winCount; i > m - winCount; i--, j--) {
        ret = (ret * i * 0.75) / j;
    }
 
    // / (m-x)번
    ret /= pow(4.0, m - winCount);
 
    return ret;
}
 
int main() {
    int C;
    scanf("%d\n", &C);
 
    while (C-- > 0) {
        int n, m;
        scanf("%d %d", &n, &m);
 
        double ret = 0.0;
 
        for (int winCount = n - m; winCount <= m; winCount++) {
            ret += getProb(m, winCount);
        }
 
        printf("%.10f\n", ret);
    }
 
    return 0;
}
cs

저작자표시 비영리 동일조건

'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글

콘서트(CONCERT) 정답 코드  (1) 2015.02.26
짝맞추기(MEETING) 정답 코드  (0) 2015.02.26
Coin Change(COINS) 정답 코드  (0) 2015.02.23
최소, 최대 정사각형 찾기 1(MMRECT1) 정답 코드  (0) 2015.02.16
Microwaving Lunch Boxes(LUNCHBOX) 정답 코드  (0) 2015.02.12

Coin Change(COINS) 정답 코드

뿌리튼튼 CS/Algorithm2015. 2. 23. 18:04

난이도 ★★★☆☆


문제를 보시려면 여기를 클릭




힌트

 전형적인 동적계획법 문제

 → 완전 탐색 + 캐시 사용




이하는 코드입니다.


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 <stdio.h>
#include <string.h>
#include <algorithm>
#include <vector>
 
#define C_MAX 100
#define M_MAX 5000
#define MOD_AMOUNT 1000000007
 
#pragma warning(disable:4996)
 
using namespace std;
 
vector<int> coins;
int cache[M_MAX][C_MAX];
 
int getCount(int money, int maxCoinIndex) {
    int& ret = cache[money][maxCoinIndex];
    if (ret != -1) {
        return ret;
    }
 
    // case found
    if (money == 0) {
        return ret = 1;
    }
 
    // if this is a leaf node
    if (maxCoinIndex == 0) {
        if (money % coins[maxCoinIndex] == 0) {
            return ret = 1;
        }
 
        return ret = 0;
    }
 
    // non-leaf node
    ret = 0;
    for (int pSum = 0; pSum <= money; pSum += coins[maxCoinIndex]) {
        ret = (ret + getCount(money - pSum, maxCoinIndex - 1)) % MOD_AMOUNT;
    }
 
    return ret;
}
 
int main() {
    int T;
    scanf("%d\n", &T);
 
    while (T-- > 0) {
        // get M, C
        int M, C;
        scanf("%d %d", &M, &C);
 
        // get sorted coins
        coins.clear();
        for (int i = 0; i < C; i++) {
            int coin;
            scanf("%d", &coin);
            coins.push_back(coin);
        }
        sort(coins.begin(), coins.end());
 
        // solve and print
        memset(cache, -1, sizeof(cache));
        printf("%d\n", getCount(M, C - 1));
    }
 
    return 0;
}
cs

저작자표시 비영리 동일조건

'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글

짝맞추기(MEETING) 정답 코드  (0) 2015.02.26
달팽이(SNAIL) 정답 코드  (0) 2015.02.24
최소, 최대 정사각형 찾기 1(MMRECT1) 정답 코드  (0) 2015.02.16
Microwaving Lunch Boxes(LUNCHBOX) 정답 코드  (0) 2015.02.12
회전초밥(SUSHI) 정답 코드  (0) 2015.02.10

최소, 최대 정사각형 찾기 1(MMRECT1) 정답 코드

뿌리튼튼 CS/Algorithm2015. 2. 16. 17:23

난이도 ★★★★☆


문제를 보시려면 여기를 클릭




틀리기 쉬운 입출력 예제

입력

출력 

3

4

10000 -10000

-10000 10000

10000 10000

-10000 -10000

7

2 2

2 4

5 4

5 1

1 1

1 2

2 1

8

7 19

11 15

3 11

3 15

7 11

11 11

3 19

11 19

20000 20000

1 3

8 8




힌트

 정사각형을 만드는 네 점을 잡았다면, 그 네 점은 (x1, y1), (x1, y2), (x2, y1), (x2, y2) 이런 형태이다.

 → 따라서 같은 값이 하나도 없는 좌표는 탐색할 필요가 없다. 같은 값이 최소 1개 이상 있는 것만 탐색한다.



이하는 코드입니다. (내 생에 최다의 for문 중첩. 무려 7중)


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
#include <stdio.h>
#include <vector>
#include <algorithm>
 
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
 
#pragma warning(disable:4996)
 
using namespace std;
 
typedef struct {
    int x;
    int y;
}Point;
 
bool myCompareX(const vector<Point> left, const vector<Point> right) {
    return left[0].x < right[0].x;
}
 
bool myCompareY(const Point left, const Point right) {
    return left.y < right.y;
}
 
int main() {
    int T;
    scanf("%d\n", &T);
    
    while (T-- > 0) {
        int N;
        scanf("%d", &N);
 
        // get points
        vector<vector<Point>> points;
        for (int i = 0; i < N; i++) {
            Point *point = new Point;
 
            scanf("%d %d", &point->x, &point->y);
 
            bool found = false;
            for (int j = 0; j < points.size(); j++) {
                if ((points[j].size() > 0) && (points[j][0].x == point->x)) {
                    points[j].push_back(*point);
                    found = true;
                    break;
                }
            }
            
            if (!found) {
                vector<Point> *arr = new vector<Point>;
                arr->push_back(*point);
                points.push_back(*arr);
            }
        }
 
        // trim
        for (int i = 0; i < points.size(); i++) {
            if (points[i].size() < 2) {
                points.erase(points.begin() + i);
            }
        }
 
        // sort
        for (int i = 0; i < points.size(); i++) {
            sort(points[i].begin(), points[i].end(), myCompareY);
        }
        sort(points.begin(), points.end(), myCompareX);
 
        /* find min, max */
        int minLength = 20001, maxLength = 0;
 
        for (int i = 0; i < points.size() - 1; i++) {
            // get x
            for (int j = 0; j < points[i].size() - 1; j++) {
                // (x, y1)
                int y1 = points[i][j].y;
                for (int k = j + 1; k < points[i].size(); k++) {
                    // (x, y2)
                    int y2 = points[i][k].y;
                    int length = y2 - y1;
                    int nextX = points[i][0].x + length;
 
                    // find nextX
                    for (int l = i + 1; l < points.size(); l++) {
                        // nextX found
                        if (points[l][0].x == nextX) {
                            for (int m = 0; m < points[l].size() - 1; m++) {
                                // y1 found
                                if (points[l][m].y == y1) {
                                    for (int n = m + 1; n < points[l].size(); n++) {
                                        // Finally, y2 found
                                        if (points[l][n].y == y2) {
                                            minLength = MIN(minLength, length);
                                            maxLength = MAX(maxLength, length);
                                            break;
                                        }
 
                                        // y2 not found
                                        if (points[l][n].y > y2) {
                                            break;
                                        }
                                    }
                                    break;
                                }
 
                                // y1 not found
                                if (points[l][m].y > y1) {
                                    break;
                                }
                            }
                            break;
                        }
 
                        // nextX not found
                        if (points[l][0].x > nextX) {
                            break;
                        }
                    }
                }
            }
        }
 
        // print
        printf("%d %d\n", minLength, maxLength);
    }
 
    return 0;
}
cs

저작자표시 비영리 동일조건

'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글

달팽이(SNAIL) 정답 코드  (0) 2015.02.24
Coin Change(COINS) 정답 코드  (0) 2015.02.23
Microwaving Lunch Boxes(LUNCHBOX) 정답 코드  (0) 2015.02.12
회전초밥(SUSHI) 정답 코드  (0) 2015.02.10
소풍(PICNIC) 정답 코드  (0) 2015.02.09

Microwaving Lunch Boxes(LUNCHBOX) 정답 코드

뿌리튼튼 CS/Algorithm2015. 2. 12. 10:38

난이도 ★☆☆☆☆


문제를 보시려면 여기를 클릭



힌트

 오래 먹는 사람을 먼저 먹인다. 만약 먹는 시간이 같은 사람이 있다면 데우는 시간이 짧은 사람을 먼저 먹인다.

 → E를 내림차순으로 정렬, 동점자에 한해서 M을 오름차순으로 정렬



이하는 코드입니다.


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
#include <stdio.h>
#include <queue>
 
#define MAX_N 10000
#define MAX(a ,b) (((a) > (b)) ? (a) : (b))
 
#pragma warning(disable:4996)
 
using namespace std;
 
typedef struct {
    int M;
    int E;
} LunchBox;
 
LunchBox lunchBoxes[MAX_N];
 
struct MaxCompare {
    bool operator() (const int index1, const int index2) {
        const LunchBox left = lunchBoxes[index1];
        const LunchBox right = lunchBoxes[index2];
 
        if (left.E == right.E) {
            return left.M > right.M;
        }
 
        return left.E < right.E;
    }
};
 
int main() {
    int T;
    scanf("%d\n", &T);
 
    while (T-- > 0) {
        int N;
        scanf("%d", &N);
 
        // get M
        int totalMTime = 0;
        for (int i = 0; i < N; i++) {
            scanf("%d", &lunchBoxes[i].M);
            totalMTime += lunchBoxes[i].M;
        }
 
        // get E and make heap
        priority_queue<int, vector<int>, MaxCompare> maxHeap;
        for (int i = 0; i < N; i++) {
            scanf("%d", &lunchBoxes[i].E);
            int *heapNode = new int;
            *heapNode = i;
            maxHeap.push(*heapNode);
        }
 
        //
        int time = 0;
        int tmpMTime = 0;
        int heapSize = maxHeap.size();
        for (int i = 0; i < heapSize; i++) {
            LunchBox top = lunchBoxes[maxHeap.top()];
 
            tmpMTime += top.M;
            time = MAX(time, top.E + tmpMTime);
 
            maxHeap.pop();
        }
 
        printf("%d\n", time);
    }
 
    return 0;
}
cs

저작자표시 비영리 동일조건

'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글

Coin Change(COINS) 정답 코드  (0) 2015.02.23
최소, 최대 정사각형 찾기 1(MMRECT1) 정답 코드  (0) 2015.02.16
회전초밥(SUSHI) 정답 코드  (0) 2015.02.10
소풍(PICNIC) 정답 코드  (0) 2015.02.09
0-1수열(ZEROONE) 정답 코드  (0) 2015.02.09

회전초밥(SUSHI) 정답 코드

뿌리튼튼 CS/Algorithm2015. 2. 10. 16:39

난이도 ★★★★★


문제를 보시려면 여기를 클릭



힌트

 동적계획법으로 완전탐색만 하면 답은 나오지만, 입력이 클 때 Recursive call이 너무 많아져서 메모리가 나가버린다.

 → 가능할 때까지 탐욕(Greedy), 불가능할 때부터는 동적계획법(Dynamic Programming)으로 완전 탐색



이하는 코드입니다.


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
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
 
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
 
#pragma warning(disable:4996)
 
typedef struct {
    int price;
    int pref;
} Sushi;
 
int n;
Sushi sushi[20];
int* cache;
 
int getMaxPref(int budget) {
    int& ret = cache[budget];
    if (ret != -1) {
        return ret;
    }
 
    int maxPref = 0;
    for (int i = 0; i < n; i++) {
        if (sushi[i].price <= budget) {
            int partialMaxPref = sushi[i].pref + getMaxPref(budget - sushi[i].price);
            maxPref = MAX(maxPref, partialMaxPref);
        }
    }
 
    return ret = maxPref;
}
 
int getGcd(int a, int b) {
    if (b == 0) {
        return a;
    }
 
    getGcd(b, a % b);
}
 
int getLcm(int a, int b) {
    return (a * b) / getGcd(a, b);
}
 
int main() {
    int c;
    scanf("%d\n", &c);
 
    while (c-- > 0) {
        int m;
        scanf("%d %d", &n, &m);
        m /= 100;
 
        // get input and get best sushi
        int bestSushiIndex = -1;
        float bestSushiRate = 0.0;
        for (int i = 0; i < n; i++) {
            scanf("%d %d", &sushi[i].price, &sushi[i].pref);
            sushi[i].price /= 100;
            
            float rate = (float)sushi[i].pref / sushi[i].price;
            if (rate > bestSushiRate) {
                bestSushiIndex = i;
                bestSushiRate = rate;
            }
        }
 
        // get lcm
        int lcm = sushi[0].price;
        for (int i = 1; i < n; i++) {
            lcm = getLcm(lcm, sushi[i].price);
        }
 
        // if m is enough to be divided lcm, do greedy
        int maxPref = 0;
        if (lcm < m) {
            int amount = m / lcm;
            amount *= (lcm / sushi[bestSushiIndex].price);
 
            maxPref = sushi[bestSushiIndex].pref * amount;
            m = m - sushi[bestSushiIndex].price * amount;
        }
 
        // do dynamic programming
        cache = (int*)malloc(sizeof(int) * (m + 1));
        for (int i = 0; i <= m; i++) {
            cache[i] = -1;
        }
        cache[0] = 0;
 
        maxPref += getMaxPref(m);
        free(cache);
 
        printf("%d\n", maxPref);
    }
    
    return 0;
}
cs

저작자표시 비영리 동일조건

'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글

최소, 최대 정사각형 찾기 1(MMRECT1) 정답 코드  (0) 2015.02.16
Microwaving Lunch Boxes(LUNCHBOX) 정답 코드  (0) 2015.02.12
소풍(PICNIC) 정답 코드  (0) 2015.02.09
0-1수열(ZEROONE) 정답 코드  (0) 2015.02.09
사각형 그리기(DRAWRECT) 정답 코드  (0) 2015.02.08

소풍(PICNIC) 정답 코드

뿌리튼튼 CS/Algorithm2015. 2. 9. 14:22

난이도 ★★★★☆


문제를 보시려면 여기를 클릭


이하는 코드입니다.


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
#include <stdio.h>
#include <string.h>
 
#pragma warning(disable:4996)
 
int n, m;
int edges[11][11];
 
int checkBoard[11];
int count;
 
void getPossibleCount() {
    /* pick p1 */
    int p1 = -1;
    for (int i = 0; i < n; i++) {
        if (checkBoard[i] == -1) {
            p1 = i;
            checkBoard[p1]++;
            break;
        }
    }
 
    // Finally, possible case was just found. count++
    if (p1 == -1) {
        count++;
        return;
    }
 
    /* pick p2 */
    for (int i = 0; i < n; i++) {
        if ((edges[p1][i] == 1) && (checkBoard[i] == -1)) {
            checkBoard[i]++;
            getPossibleCount();
            checkBoard[i]--;
        }
    }
 
    checkBoard[p1]--;
}
 
int main() {
    int C;
    scanf("%d", &C);
 
    for (int i = 0; i < C; i++) {
        scanf("%d %d", &n, &m);
 
        // get edges
        memset(edges, -1, sizeof(edges));
        for (int j = 0; j < m; j++) {
            int p1, p2;
            scanf("%d %d", &p1, &p2);
 
            edges[p1][p2] = edges[p2][p1] = 1;
        }
 
        // 
        memset(checkBoard, -1, sizeof(checkBoard));
        count = 0;
        getPossibleCount();
        printf("%d\n", count);
    }
 
    return 0;
}
cs

저작자표시 비영리 동일조건

'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글

Microwaving Lunch Boxes(LUNCHBOX) 정답 코드  (0) 2015.02.12
회전초밥(SUSHI) 정답 코드  (0) 2015.02.10
0-1수열(ZEROONE) 정답 코드  (0) 2015.02.09
사각형 그리기(DRAWRECT) 정답 코드  (0) 2015.02.08
최대 연속 부분합 찾기(MAXSUM) 입력 출력 및 정답 코드  (0) 2015.02.05

0-1수열(ZEROONE) 정답 코드

뿌리튼튼 CS/Algorithm2015. 2. 9. 10:39

난이도 ★★☆☆☆


문제를 보시려면 여기를 클릭


이하는 코드입니다.


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
#include <stdio.h>
 
#pragma warning(disable:4996)
 
int cache[1000001];
 
int main() {
    cache[0] = 0;
 
    char before;
    scanf("%c", &before);
 
    for (int i = 1; 1; i++) {
        char c;
        scanf("%c", &c);
        if (c == '\n') {
            break;
        }
 
        if (c != before) {
            cache[i] = cache[i - 1] + 1;
            before = c;
        }
        else {
            cache[i] = cache[i - 1];
        }
    }
 
    int N;
    scanf("%d", &N);
    while (N-- > 0) {
        int i, j;
        scanf("%d %d", &i, &j);
 
        // print
        if (cache[i] == cache[j]) {
            printf("Yes\n");
        }
        else {
            printf("No\n");
        }
    }
 
    return 0;
}
cs

저작자표시 비영리 동일조건

'뿌리튼튼 CS > Algorithm' 카테고리의 다른 글

회전초밥(SUSHI) 정답 코드  (0) 2015.02.10
소풍(PICNIC) 정답 코드  (0) 2015.02.09
사각형 그리기(DRAWRECT) 정답 코드  (0) 2015.02.08
최대 연속 부분합 찾기(MAXSUM) 입력 출력 및 정답 코드  (0) 2015.02.05
출전 순서 정하기(MATCHORDER) 정답 코드  (0) 2015.02.04

티스토리툴바