Strong Root

codility - BinaryGap 정답 및 해설

뿌리튼튼 CS/Algorithm2017. 6. 6. 21: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
public int solution(int N) {
    String biStr = Integer.toBinaryString(N);
    int firstOneIndex = getNextOneIndex(biStr, 0);
 
    if (firstOneIndex < 0) {
        return 0;
    }
 
    int maxGap = 0;
 
    while (true) {
        int nextOneIndex = getNextOneIndex(biStr, firstOneIndex + 1);
 
        if (nextOneIndex < 0) {
            break;
        }
 
        int gap = nextOneIndex - firstOneIndex - 1;
 
        if (gap > maxGap) {
            maxGap = gap;
        }
 
        firstOneIndex = nextOneIndex;
    }
 
    return maxGap;
}
 
private int getNextOneIndex(String biStr, int startIndex) {
    int nextOneIndex = -1;
 
    for (int i = startIndex; i < biStr.length(); i++) {
        char c = biStr.charAt(i);
 
        if (c == '1') {
            nextOneIndex = i;
            break;
        }
    }
 
    return nextOneIndex;
}
cs


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

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

codility - CyclicRotation 정답 및 해설  (0) 2017.06.06
codility - OddOccurrencesInArray 정답 및 해설  (0) 2017.06.06
Conversions(CONVERT) 정답 코드  (0) 2015.10.09
Endians(ENDIANS) 정답 코드  (0) 2015.10.09
Mispelling(MISPELL) 정답 코드  (0) 2015.04.10

Conversions(CONVERT) 정답 코드

뿌리튼튼 CS/Algorithm2015. 10. 9. 17:03

난이도 ★☆☆☆☆


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



 

힌트

 문자열 처리에 주의할 것.




이하는 코드입니다.

 

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
#include <stdio.h>
#include <string>
#include <iostream>
 
#define KG_TO_LB 2.2046
#define LB_TO_KG 0.4536
#define L_TO_G 0.2642
#define G_TO_L 3.7854
 
#pragma warning(disable:4996)
 
using namespace std;
 
int main() {
    int N;
    scanf("%d\n", &N);
 
    for (int i = 1; i <= N; i++) {
        string input;
        getline(cin, input);
 
        int pivot = input.find(' ');
        string left (input, 0, pivot);
        string right(input, pivot + 1, string::npos);
 
        float num = atof(left.c_str());
        float resultNum;
        string resultUnit;
        if (right.compare("kg") == 0) {
            resultNum = num * KG_TO_LB;
            resultUnit = "lb";
        }
        else if (right.compare("lb") == 0) {
            resultNum = num * LB_TO_KG;
            resultUnit = "kg";
        }
        else if (right.compare("l") == 0) {
            resultNum = num * L_TO_G;
            resultUnit = "g";
        }
        else if (right.compare("g") == 0) {
            resultNum = num * G_TO_L;
            resultUnit = "l";
        }
        else {
            resultNum = 0.;
            resultUnit = "";
        }
 
        printf("%d %.4f %s\n", i, resultNum, resultUnit.c_str());
    }
 
    return 0;
}
 cs

 

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

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

codility - OddOccurrencesInArray 정답 및 해설  (0) 2017.06.06
codility - BinaryGap 정답 및 해설  (0) 2017.06.06
Endians(ENDIANS) 정답 코드  (0) 2015.10.09
Mispelling(MISPELL) 정답 코드  (0) 2015.04.10
터보모드(TURBOMODE) 정답 코드  (0) 2015.04.10

Endians(ENDIANS) 정답 코드

뿌리튼튼 CS/Algorithm2015. 10. 9. 14:56

난이도 ★☆☆☆☆


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



 

힌트

 오버플로우(overflow)에 주의할 것.




이하는 코드입니다.

 

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
#include <stdio.h>
#include <math.h>
 
#pragma warning(disable:4996)
 
unsigned long convert(const unsigned long num) {
    unsigned long first = num / pow(2., 24);
    unsigned long second = (num / pow(2., 16)) - (first * pow(2., 8));
    unsigned long third = (num / pow(2., 8)) - (second * pow(2., 8)) - (first * pow(2., 16));
    unsigned long fourth = num % (unsigned long)pow(2., 8);
 
    return first + second * pow(2., 8) + third * pow(2., 16) + fourth * pow(2., 24);
}
 
int main() {
    int C;
    scanf("%d", &C);
 
    while (C-- > 0) {
        unsigned long num;
        scanf("%lu", &num);
 
        printf("%lu\n", convert(num));
    }
 
    return 0;
}
 cs

 

 

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

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

codility - BinaryGap 정답 및 해설  (0) 2017.06.06
Conversions(CONVERT) 정답 코드  (0) 2015.10.09
Mispelling(MISPELL) 정답 코드  (0) 2015.04.10
터보모드(TURBOMODE) 정답 코드  (0) 2015.04.10
HOTSUMMER 정답 코드  (0) 2015.04.10

Mispelling(MISPELL) 정답 코드

뿌리튼튼 CS/Algorithm2015. 4. 10. 19:35

난이도 ★☆☆☆☆


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




틀리기 쉬운 입출력 예제

입력

출력 

4

80 ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZAB

1 A

3 ABC

1 ABC

1 ABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZABCDEFGHIJKLMNOPQRSTUVWXYZA

2 

3 AB

4 BC




힌트

 쉬운 문제이지만 풀이 방식에 따라 성능 차이가 크다. 개인적으로 내 코드에 굉장히 만족한다. 아마도 더 깔끔한 방법은 없을 것 같다.

 → %s가 NULL문자 앞까지만 출력하는 것을 이용한다.

① string[M - 1] = NULL 을 넣어준다.

② printf("%s%s", string, string + 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
#include <stdio.h>
#include <string.h>
 
#pragma warning(disable:4996)
 
int main() {
    // get N
    int N;
    scanf("%d\n", &N);
 
    for (int i = 1; i <= N; i++) {
        // get M, s
        int M;
        char s[82];
        memset(s, 0, sizeof(s));
        scanf("%d %s", &M, s);
 
        // set s[M-1] = NULL
        s[M - 1] = NULL;
 
        // print (i, s[0 ~ M-2] + s[M ~])
        printf("%d %s%s\n", i, s, s + M);
    }
 
    return 0;
}
cs

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

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

Conversions(CONVERT) 정답 코드  (0) 2015.10.09
Endians(ENDIANS) 정답 코드  (0) 2015.10.09
터보모드(TURBOMODE) 정답 코드  (0) 2015.04.10
HOTSUMMER 정답 코드  (0) 2015.04.10
게임판 덮기(BOARDCOVER) 정답 코드  (0) 2015.02.28

터보모드(TURBOMODE) 정답 코드

뿌리튼튼 CS/Algorithm2015. 4. 10. 18:52

난이도 ★☆☆☆☆




문제

N(1~1000)개의 Process 를 돌릴 수 있으며, 동시에 최대 100개의 Process 를 실행할 수 있다.

 

1~1000초 사이 동안 5개의 Process 가 실행되는 시간이 아래 그림과 같다면

 

　　　　
　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　
　　　　　　　　　　　　　　　　　　　　　　
234567891011121314151617…9969979989991000

 

Turbo mode 로 실행되는 Process의 개수를 출력하시오. (단, Turbo mode 는 Process 가 연속으로 3초 이상 실행되면 동작하며, 입력은 Process 의 시작 시간을 기준으로 오름차순으로 주어진다)

 

입력

5  → 입력할 Process 의 개수

1 3

4 6

6 8

12 16

13 15


출력

2




힌트

 Greedy로 Process를 한번씩만 탐색하면 끝난다. O(n)

 → ① Process 하나를 먼저 입력받고 시작시간과 종료시간을 저장한다.

 → ② Process를 하나씩 입력받으면서, 시작시간이 기존 Process의 종료시간보다 이르면 합치고

 → ③ 늦으면 기존 Process를 새걸로 덮어쓴다. 이때 기존 Process의 지속시간이 3초 보다 길었다면 count++ 해준다.



이하는 코드입니다.


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>
 
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
 
#pragma warning(disable:4996)
 
typedef struct {
    int start;
    int end;
} P;    // Process
 
int main() {
    int sizeOfP;
    scanf("%d\n", &sizeOfP);
 
    int count = 0;
 
    P oldP;
    scanf("%d %d", &oldP.start, &oldP.end);
    sizeOfP--;
 
    while (sizeOfP-- > 0) {
        P newP;
        scanf("%d %d", &newP.start, &newP.end);
 
        if (newP.start <= oldP.end) {
            oldP.end = MAX(oldP.end, newP.end);
        }
        else {
            if ((oldP.end - oldP.start) >= 3) {
                count++;
            }
            oldP.start = newP.start;
            oldP.end = newP.end;
        }
    }
 
    if ((oldP.end - oldP.start) >= 3) {
        count++;
    }
 
    printf("%d\n", count);
 
    return 0;
}
cs

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

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

Endians(ENDIANS) 정답 코드  (0) 2015.10.09
Mispelling(MISPELL) 정답 코드  (0) 2015.04.10
HOTSUMMER 정답 코드  (0) 2015.04.10
게임판 덮기(BOARDCOVER) 정답 코드  (0) 2015.02.28
콘서트(CONCERT) 정답 코드  (1) 2015.02.26

HOTSUMMER 정답 코드

뿌리튼튼 CS/Algorithm2015. 4. 10. 18:30

난이도 ★☆☆☆☆


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




틀리기 쉬운 입출력 예제

입력

출력 

3

0

0 0 0 0 0 0 0 0 0

9000

1000 1000 1000 1000 1000 1000 1000 1000 1000

9

1 1 1 1 1 1 1 1 2

YES

YES

NO




힌트

 A값들을 잘 더해서 W값 이하인지 비교만 하면 된다.

 출력이 대문자인 것에 주의한다.



이하는 코드입니다.


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
#include <stdio.h>
 
#pragma warning(disable:4996)
 
int main() {
    int T;
    scanf("%d\n", &T);
 
    while (T-- > 0) {
        int W;
        scanf("%d", &W);
 
        int sum = 0;
        for (int i = 0; i < 9; i++) {
            int A;
            scanf("%d", &A);
 
            sum += A;
        }
 
        if (sum <= W) {
            printf("YES\n");
        }
        else {
            printf("NO\n");
        }
    }
 
    return 0;
}
cs

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

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

Mispelling(MISPELL) 정답 코드  (0) 2015.04.10
터보모드(TURBOMODE) 정답 코드  (0) 2015.04.10
게임판 덮기(BOARDCOVER) 정답 코드  (0) 2015.02.28
콘서트(CONCERT) 정답 코드  (1) 2015.02.26
짝맞추기(MEETING) 정답 코드  (0) 2015.02.26

게임판 덮기(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

티스토리툴바