BOJ : https://www.acmicpc.net/problem/10610

github : https://github.com/junho0956/Algorithm/blob/master/10610/10610/%EC%86%8C%EC%8A%A4.cpp

 

30의 배수가 되기 위해서는 2가지의 조건이 필요합니다.

1) 마지막숫자가 0 이여야합니다. ==> 0의 존재여부를 확인해주시면 됩니다.

2) 수를 전부 더 했을 때 3의 배수 즉, 3으로 나누어떨어져야합니다.

30의 배수는 30 60 90 120 150 180 210 ,,, 이 되는데 숫자들을 자리수끼리 더해보면 결국 3으로 나누어떨어진다는 점을 알 수 있습니다. 

 

더보기
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 <iostream>
#include <string>
#include <algorithm>
using namespace std;
 
bool cmp(char& a, char& b) { return a > b; }
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    string str;
    cin >> str;
 
    long long total = 0, check = 0;
    for (int i = 0; i < str.size(); i++) {
        total += str[i] - '0';
        if (str[i] == '0') check = 1;
    }
 
    if (check && total % 3 == 0) {
        sort(str.begin(), str.end(), cmp);
        cout << str << '\n';
    }
    else cout << "-1\n";
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1931번 회의실 배정  (0) 2020.01.17
BOJ 1783번 병든 나이트  (0) 2020.01.17
BOJ 2875번 대회or인턴  (0) 2020.01.17
BOJ 11047번 동전 0  (0) 2020.01.17
BOJ 10090번 Counting Inversions  (0) 2020.01.17

BOJ : https://www.acmicpc.net/problem/2875

github : https://github.com/junho0956/Algorithm/blob/master/2875/2875/%EC%86%8C%EC%8A%A4.cpp

 

N 의 조건을 제대로 주지못해서 틀렸던 문제입니다.

N은 항상 2명씩 계산되어야합니다.

team을 우선 계산해준후에 K에 대한 계산을 해주면 됩니다.

 

더보기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
 
 
int main() {
    int N, M, K, team = 0;
 
    cin >> N >> M >> K;
 
    while (N > 1 && M) {
        team++, N -= 2, M--;
    }
 
    while (N && K) N--, K--;
    while (M && K) M--, K--;
 
    while (team && K > 0) team--, K -= 3;
    cout << team;
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 1783번 병든 나이트  (0) 2020.01.17
BOJ 10610번 30  (0) 2020.01.17
BOJ 11047번 동전 0  (0) 2020.01.17
BOJ 10090번 Counting Inversions  (0) 2020.01.17
BOJ 1517번 버블 소트  (0) 2020.01.17

BOJ : https://www.acmicpc.net/problem/11047

github : https://github.com/junho0956/Algorithm/blob/master/11047/11047/%EC%86%8C%EC%8A%A4.cpp

 

동전 0 과 같은 문제는 1, 5, 10, 50, .. 과 같은 현재 한국의 동전형태와 같이 나오기 때문에 가능한 문제일 것입니다.

만약 동전이 12원짜리가 있다거나 했을 때는 동적계획법으로 풀어야 해결할 수 있습니다.

 

더보기
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <iostream>
using namespace std;
 
int coin[10];
 
int main() {
    int N, K;
    cin >> N >> K;
    for (int i = 0; i < N; i++) {
        cin >> coin[i];
    }
 
    int cnt = 0;
    while (K) {
        if (coin[N - 1] <= K) K -= coin[N - 1], cnt++;
        else N--;
    }
 
    cout << cnt;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 10610번 30  (0) 2020.01.17
BOJ 2875번 대회or인턴  (0) 2020.01.17
BOJ 10090번 Counting Inversions  (0) 2020.01.17
BOJ 1517번 버블 소트  (0) 2020.01.17
BOJ 1992번 쿼드트리  (0) 2020.01.17

BOJ : https://www.acmicpc.net/problem/10090

github : https://github.com/junho0956/Algorithm/blob/master/10090/10090/%EC%86%8C%EC%8A%A4.cpp

 

도치수는 merge_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
51
52
53
54
55
#include <iostream>
using namespace std;
 
#define MAX 1000000
 
int arr[MAX];
int dup[MAX];
 
long long partition(int s, int m, int e) {
    int left = s, right = m + 1;
    int index = 0;
    long long result = 0;
    while (left <= m && right <= e) {
        if (arr[right] >= arr[left]) {
            dup[index++] = arr[left++];
        }
        else {
            result += m - left + 1;
            dup[index++] = arr[right++];
        }
    }
 
    while (left <= m) dup[index++] = arr[left++];
    while (right <= e) dup[index++] = arr[right++];
 
    for (int i = 0; i <= e - s; i++) {
        arr[s + i] = dup[i];
    }
 
    return result;
}
 
long long merge_sort(int s, int e) {
    long long result = 0;
    if (s < e) {
        int pivot = (s + e) / 2;
        result += merge_sort(s, pivot);
        result += merge_sort(pivot + 1, e);
        result += partition(s, pivot, e);
    }
    return result;
}
 
 
int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int N; cin >> N;
 
    for (int i = 0; i < N; i++) cin >> arr[i];
 
    long long result = merge_sort(0, N - 1);
 
    cout << result;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

'algorithm > BOJ' 카테고리의 다른 글

BOJ 2875번 대회or인턴  (0) 2020.01.17
BOJ 11047번 동전 0  (0) 2020.01.17
BOJ 1517번 버블 소트  (0) 2020.01.17
BOJ 1992번 쿼드트리  (0) 2020.01.17
BOJ 1780번 종이의 개수  (0) 2020.01.17

+ Recent posts

티스토리툴바