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

티스토리툴바