Strong Root

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

사각형 그리기(DRAWRECT) 정답 코드

뿌리튼튼 CS/Algorithm2015. 2. 8. 10:25

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


이하는 코드입니다.


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
#include <stdio.h>
 
#pragma warning(disable:4996)
 
typedef struct {
    int value;
    int count;
} Cache;
 
int main() {
    int T;
    scanf("%d\n", &T);
 
    for (int i = 0; i < T; i++) {
        // init cache
        Cache xCache[2], yCache[2];
        for (int j = 0; j < 2; j++) {
            xCache[j].value = yCache[j].value = xCache[j].count = yCache[j].count = 0;
        }
 
        for (int j = 0; j < 3; j++) {
            int x, y;
            scanf("%d %d", &x, &y);
 
            /* x */
            // if empty
            if (xCache[0].count == 0) {
                xCache[0].value = x;
                xCache[0].count++;
            }
 
            // if full
            else if (xCache[0].value == x) {
                xCache[0].count++;
            }
            else if (xCache[1].value == x) {
                xCache[1].count++;
            }
 
            // if half empty
            else {
                xCache[1].value = x;
                xCache[1].count++;
            }
 
            /* y */
            // if empty
            if (yCache[0].count == 0) {
                yCache[0].value = y;
                yCache[0].count++;
            }
 
            // if full
            else if (yCache[0].value == y) {
                yCache[0].count++;
            }
            else if (yCache[1].value == y) {
                yCache[1].count++;
            }
 
            // if half empty
            else {
                yCache[1].value = y;
                yCache[1].count++;
            }
        }
 
        // print x
        for (int j = 0; j < 2; j++) {
            if (xCache[j].count == 1) {
                printf("%d ", xCache[j].value);
                break;
            }
        }
 
        // print y
        for (int j = 0; j < 2; j++) {
            if (yCache[j].count == 1) {
                printf("%d\n", yCache[j].value);
                break;
            }
        }
    }
 
    return 0;
}
cs

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

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

소풍(PICNIC) 정답 코드  (0) 2015.02.09
0-1수열(ZEROONE) 정답 코드  (0) 2015.02.09
최대 연속 부분합 찾기(MAXSUM) 입력 출력 및 정답 코드  (0) 2015.02.05
출전 순서 정하기(MATCHORDER) 정답 코드  (0) 2015.02.04
승률올리기(RATIO) 정답 코드  (0) 2015.01.28

최대 연속 부분합 찾기(MAXSUM) 입력 출력 및 정답 코드

뿌리튼튼 CS/Algorithm2015. 2. 5. 13:56

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



틀리기 쉬운 입출력 예제

입력

출력 

7

4

1 2 3 4

3

-1 0 1

8

1 2 3 2 1 2 3 2

6

4 50 2 -10 2 4

4

-5 2 3 -2

4

-1 -2 -3 -4

6

2 3 -4 -1 -1 6

10

1

16

56

5

0

6



이하는 코드입니다.


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
#include <stdio.h>
 
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
 
#pragma warning(disable:4996)
 
int main() {
    int T;
    scanf("%d\n", &T);
 
    for (int i = 0; i < T; i++) {
        int N;
        scanf("%d", &N);
 
        int inputNum;
        int maxPartialSum = 0;
        int partialSum = 0;
        for (int j = 0; j < N; j++) {
            scanf("%d", &inputNum);
            partialSum += inputNum;
            if (partialSum < 0) {
                partialSum = 0;
                continue;
            }
            maxPartialSum = MAX(maxPartialSum, partialSum);
        }
 
        printf("%d\n", maxPartialSum);
    }
 
    return 0;
}
cs

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

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

0-1수열(ZEROONE) 정답 코드  (0) 2015.02.09
사각형 그리기(DRAWRECT) 정답 코드  (0) 2015.02.08
출전 순서 정하기(MATCHORDER) 정답 코드  (0) 2015.02.04
승률올리기(RATIO) 정답 코드  (0) 2015.01.28
록 페스티벌(FESTIVAL) 정답 코드  (0) 2015.01.28

출전 순서 정하기(MATCHORDER) 정답 코드

뿌리튼튼 CS/Algorithm2015. 2. 4. 13:53

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


이하는 코드입니다.


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 <stdio.h>
#include <queue>
 
#pragma warning(disable:4996)
 
using namespace std;
 
struct MaxCompare {
    bool operator() (const int left, const int right) {
        return left < right;
    }
};
 
int main() {
    int C;
    scanf("%d\n", &C);
 
    for (int i = 0; i < C; i++) {
        int N;
        scanf("%d", &N);
 
        priority_queue<int, vector<int>, MaxCompare> maxHeap_enemy;
        for (int j = 0; j < N; j++) {
            int *enemyRating = new int;
            scanf("%d", enemyRating);
            maxHeap_enemy.push(*enemyRating);
        }
 
        priority_queue<int, vector<int>, MaxCompare> maxHeap_korea;
        for (int j = 0; j < N; j++) {
            int *koreanRating = new int;
            scanf("%d", koreanRating);
            maxHeap_korea.push(*koreanRating);
        }
 
        int winCount = 0;
        while (true) {
            if (maxHeap_enemy.size() < 1) {
                break;
            }
 
            // cannot defeat
            if (maxHeap_enemy.top() > maxHeap_korea.top()) {
                maxHeap_enemy.pop();
                continue;
            }
 
            // can defeat
            winCount++;
            maxHeap_enemy.pop();
            maxHeap_korea.pop();
        }
 
        printf("%d\n", winCount);
    }
 
    return 0;
}
cs

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

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

사각형 그리기(DRAWRECT) 정답 코드  (0) 2015.02.08
최대 연속 부분합 찾기(MAXSUM) 입력 출력 및 정답 코드  (0) 2015.02.05
승률올리기(RATIO) 정답 코드  (0) 2015.01.28
록 페스티벌(FESTIVAL) 정답 코드  (0) 2015.01.28
Hello World!(HELLOWORLD) 정답 코드  (0) 2015.01.27

승률올리기(RATIO) 정답 코드

뿌리튼튼 CS/Algorithm2015. 1. 28. 16:49

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


이하는 코드입니다.


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 <stdio.h>
 
#pragma warning(disable:4996)
 
long long N, M;
 
int getWinNum() {
    int goal = (M * 100) / N + 1;    // 엄청 중요한 문장. 이 문장 때문에 2시간을 허비함.
    if (goal > 99) {
        return -1;
    }
 
    double ret =  (double)(goal * N - 100 * M) / (100 - goal);
    int flooredRet = (int)ret;
    if ((ret - flooredRet) > 0.0) {
        return flooredRet + 1;
    }
    return flooredRet;
}
 
int main() {
    int C;
    scanf("%d\n", &C);
 
    for (int i = 0; i < C; i++) {
        int tmpN, tmpM;
        scanf("%d %d", &tmpN, &tmpM);
        N = tmpN;
        M = tmpM;
        printf("%d\n", getWinNum());
    }
 
    return 0;
}
cs

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

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

최대 연속 부분합 찾기(MAXSUM) 입력 출력 및 정답 코드  (0) 2015.02.05
출전 순서 정하기(MATCHORDER) 정답 코드  (0) 2015.02.04
록 페스티벌(FESTIVAL) 정답 코드  (0) 2015.01.28
Hello World!(HELLOWORLD) 정답 코드  (0) 2015.01.27
외발뛰기(JUMPGAME) 정답 코드  (0) 2015.01.27

티스토리툴바