Strong Root

게임판 덮기(BOARDCOVER) 정답 코드

뿌리튼튼 CS/Algorithm2015. 2. 28. 11:19

난이도 ★★★★☆


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




힌트

 재귀로 탐색하면 편리하다.

 → ① 왼쪽 위 점을 기준으로 잡고 하면 좋다. 그렇게 되면 가능한 경우가 4가지만 나온다.

 → ② 탐색 중에 덮었으면(cover) 꼭 다시 벗겨줘야(uncover) 한다.



이하는 코드입니다.


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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
#include <stdio.h>
#include <vector>
 
#define WALL 1
#define EMPTY 0
 
#pragma warning(disable:4996)
 
using namespace std;
 
int H, W;
vector<vector<int>> board;
int coverCount;
 
void getCount(int y, int x) {
    // get left-top
    int i, j;
    bool found = false;
    for (i = y; i < H; i++) {
        if (i == y) {
            j = x;
        }
        else {
            j = 0;
        }
        for (; j < W; j++) {
            if (board[i][j] == EMPTY) {
                found = true;
                break;
            }
        }
 
        if (found) {
            break;
        }
    }
 
    // there is no EMPTY → case found
    if (!found) {
        coverCount++;
        return;
    }
 
    // last row → impossible case
    if (i > H - 2) {
        return;
    }
 
    // last column → only 」case could be possible
    if (j > W - 2) {
        // 」
        if ((board[i + 1][j - 1] == EMPTY) && (board[i + 1][j] == EMPTY)) {
            // cover
            board[i][j]++;
            board[i + 1][j - 1]++;
            board[i + 1][j]++;
 
            getCount(i, j);
 
            // uncover
            board[i][j]--;
            board[i + 1][j - 1]--;
            board[i + 1][j]--;
        }
 
        return;
    }
 
    // neither last row nor last column → all cases could be possible
    else {
        // ㄱ
        if ((board[i][j + 1] == EMPTY) && (board[i + 1][j + 1] == EMPTY)) {
            // cover
            board[i][j]++;
            board[i][j + 1]++;
            board[i + 1][j + 1]++;
 
            getCount(i, j);
 
            // uncover
            board[i][j]--;
            board[i][j + 1]--;
            board[i + 1][j + 1]--;
        }
 
        // 「
        if ((board[i][j + 1] == EMPTY) && (board[i + 1][j] == EMPTY)) {
            // cover
            board[i][j]++;
            board[i][j + 1]++;
            board[i + 1][j]++;
 
            getCount(i, j);
 
            // uncover
            board[i][j]--;
            board[i][j + 1]--;
            board[i + 1][j]--;
        }
 
        // 」
        if ((board[i + 1][j - 1] == EMPTY) && (board[i + 1][j] == EMPTY)) {
            // cover
            board[i][j]++;
            board[i + 1][j - 1]++;
            board[i + 1][j]++;
 
            getCount(i, j);
 
            // uncover
            board[i][j]--;
            board[i + 1][j - 1]--;
            board[i + 1][j]--;
        }
 
        // ㄴ
        if ((board[i + 1][j] == EMPTY) && (board[i + 1][j + 1] == EMPTY)) {
            // cover
            board[i][j]++;
            board[i + 1][j]++;
            board[i + 1][j + 1]++;
 
            getCount(i, j);
 
            // uncover
            board[i][j]--;
            board[i + 1][j]--;
            board[i + 1][j + 1]--;
        }
    }
}
 
int main() {
    int C;
    scanf("%d\n", &C);
 
    while (C-- > 0) {
        scanf("%d %d\n", &H, &W);
 
        // get board
        for (int i = 0; i < H; i++) {
            vector<int> line;
 
            for (int j = 0; j < W; j++) {
                char c;
                scanf("%c", &c);
 
                if (c == '.') {
                    line.push_back(EMPTY);
                }
                else {
                    line.push_back(WALL);
                }
            }
            board.push_back(line);
 
            // remove '\n'
            getchar();
        }
 
        // solve and print
        coverCount = 0;
        getCount(0, 0);
        printf("%d\n", coverCount);
 
        // reset
        if (C > 0) {
            board.clear();
        }
    }
 
    return 0;
}
cs

저작자표시 비영리 동일조건 (새창열림)

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

터보모드(TURBOMODE) 정답 코드  (0) 2015.04.10
HOTSUMMER 정답 코드  (0) 2015.04.10
콘서트(CONCERT) 정답 코드  (1) 2015.02.26
짝맞추기(MEETING) 정답 코드  (0) 2015.02.26
달팽이(SNAIL) 정답 코드  (0) 2015.02.24

콘서트(CONCERT) 정답 코드

뿌리튼튼 CS/Algorithm2015. 2. 26. 14:18

난이도 ★★★☆☆


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




틀리기 쉬운 입출력 예제

입력

출력 

3

1 5 9

5

1 5 9

6

50 1 24

1 2 2 2 4 2 3 2 1 2 3 2 1 2 3 2 3 2 1 2 3 1 2 3 2 5 3 5 3 2 2 5 6 6 7 7 5 8 7 8 7 5 7 5 6 5 6 6 6 4

0

-1

24




힌트

 동적계획법의 전형적인 문제이지만 문제 이해가 좀 어렵다.

 → 이해했다면 동적계획법의 틀(재귀함수 + 캐시)대로 구현하면 된다.



이하는 코드입니다.


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
#include <stdio.h>
#include <string.h>
 
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
 
#define FAIL -3
#define N_MAX 50
#define VM_MAX 1000
 
#pragma warning(disable:4996)
 
int N, VM;
int board[N_MAX];
int cache[N_MAX + 2][VM_MAX];
 
int getMaxVolume(int VS, int boardIndex) {
    if ((VS < 0) || (VS > VM)) {
        return FAIL;
    }
 
    int& ret = cache[boardIndex][VS];
    if (ret != -1) {
        return ret;
    }
 
    if (boardIndex == N) {
        return ret = VS;
    }
 
    return ret = (MAX(getMaxVolume(VS + board[boardIndex], boardIndex + 1), getMaxVolume(VS - board[boardIndex], boardIndex + 1)));
}
 
int main() {
    int T;
    scanf("%d\n", &T);
 
    while (T-- > 0) {
        // get N, VS, VM
        int VS;
        scanf("%d %d %d", &N, &VS, &VM);
 
        // get Vi
        for (int i = 0; i < N; i++) {
            scanf("%d", &board[i]);
        }
 
        // solve and print
        memset(cache, -1, sizeof(cache));
        int maxVolume = getMaxVolume(VS, 0);
        if (maxVolume == FAIL) {
            maxVolume = -1;
        }
        printf("%d\n", maxVolume);
    }
 
    return 0;
}
cs

저작자표시 비영리 동일조건 (새창열림)

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

HOTSUMMER 정답 코드  (0) 2015.04.10
게임판 덮기(BOARDCOVER) 정답 코드  (0) 2015.02.28
짝맞추기(MEETING) 정답 코드  (0) 2015.02.26
달팽이(SNAIL) 정답 코드  (0) 2015.02.24
Coin Change(COINS) 정답 코드  (0) 2015.02.23

짝맞추기(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

[강좌] 초급2 - 버튼 클릭 + 리스너

뿌리튼튼 CS/Android2015. 2. 15. 14:56

<초급1 - 입문 + xml, java 파일 작성법 바로가기>



다음으로 버튼(Button)을 배워보겠습니다.


아래와 같은 화면을 구성해보겠습니다.


[그림2-1] 목표2



먼저 기존의 xml 파일을 아래와 같이 수정합니다.


[그림2-2] activity_my.xml


위와 같이 xml 내용을 입력한 후 미리보기(preview)를 보시면 [그림2-1]와 같은 모습이 보입니다. 이제 뷰는 완성되었습니다.






Java 파일을 아래와 같이 수정합니다.


[그림2-3] MyActivity.java


여기까지 작성한 후 휴대폰을 pc에 연결하고 Run을 시켜봅니다.


어플이 실행되며...는 개뿔 컴파일 에러가 뜹니다. 죄송합니다 ㅎㅎ 코드 설명을 위해 잠깐 멈추었습니다.










[그림2-3]의 빨간 박스 안의 코드를 살펴보겠습니다.







바인딩(Binding)이라고 이름까지 있는 중요한 코드입니다.


xml 상의 뷰를 Java에서 컨트롤할 수 있도록 id값을 통해 말그대로 묶어주는(bind) 역할을 합니다.







위 그림처럼, 바인딩한 Java변수에 점(.)을 찍어보면 굉장히 많은 일들을 할 수 있다는 것을 알 수 있습니다.


xml에서 할 수 있는 일(가로 세로 크기 등)을 Java의 바인딩된 변수를 통해서도 할 수 있습니다.


이 바인딩의 가장 큰 장점은 런타임에서의 동적인 처리를 가능케 한다는 것입니다.







우리는 위 목록 중에서 setOnClickListener(OnClickListener l) 함수를 사용해보겠습니다.


위처럼 타이핑 해보면 괄호 안에 빨간 줄이 그이며 뷰에 등록할 OnClickListner 객체를 쓰라고 합니다.


여기에 OnClickListener 객체를 넣는 방법은 크게 두가지가 있습니다.


① 해당 객체를 그자리에서 new로 생성해주는 방법

② 현재 Activity 클래스 자신이 OnClickListener를 구현(implement)하고 자신(this)을 인자로 넘겨주는 방법


결론부터 말하면 ②가 좋습니다만 ①부터 살펴보겠습니다 ㅎㅎ




<① 해당 객체를 그자리에서 new로 생성해주는 방법>


보통 가장 처음으로 배우는 방법입니다.



위와 같이 코드를 작성하고 'do something' 자리에 하고 싶은 일을 적으면 됩니다.




이 방법은 굉장히 간편합니다. 단, 뷰가 하나일 때만요.


버튼이 두개 이상이라면 어떨까요?



뷰의 개수만큼 OnClickListener 객체를 새로 생성해주고 있습니다.


②를 볼까요?






<② 현재 Activity 클래스 자신이 OnClickListener를 구현(implement)하고 자신(this)을 인자로 넘겨주는 방법>





이해를 위해, 구현(implements)도 상속(extends)과 비슷하다고 보시면 좋습니다.




이렇게 쓰는 순간, MyActivity 자신이 OnClickListener 객체가 되게 됩니다.


즉, MyActivity는 Activity이면서 동시에 OnClickListener인겁니다.




따라서 OnClickListener 객체를 요하는 setOnClickListener() 함수에 자기 자신(this)을 인자로 넘겨주면 되는 것입니다.




보시면, 뷰의 개수가 늘어나도 OnClickListener 객체를 새로 생성하지 않습니다. 메모리가 조금이라도 덜 들어가겠죠.


또한 하나의 onClick()함수만 사용함으로써 코드의 가독성이 훨씬 증가합니다.










다시 본론으로 돌아가서 Java 파일을 완성해보겠습니다.


[그림2-4] MyActivity.java


위와 같이 작성한 후 휴대폰을 pc에 연결하고 Run을 시켜봅니다.


어플이 실행되며 xml 미리보기에서 봤던 것과 같은 화면이 여러분의 휴대폰에서 보일 것입니다.




'첫 버튼'을 클릭했을 때 '첫 토스트'가 뜬다면 성공입니다.










본격적인 안드로이드의 세계로 오신 것을 환영합니다. 


저작자표시 비영리 동일조건 (새창열림)

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

File to Byte Array (File을 Byte배열로 변환)  (0) 2015.06.12
Android Studio에서 Library 추가시 쓸데없는 Duplicate 오류 대처법  (0) 2015.06.12
[강좌] Android SDK Search - 설치 및 SDK 소스 보기  (0) 2015.01.17
[강좌] 초급1 - 입문 + xml, java 파일 작성법  (0) 2015.01.16
Intent 활용 예시  (0) 2014.11.12

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

티스토리툴바