반응형

www.acmicpc.net/problem/4375

 

4375번: 1

2와 5로 나누어 떨어지지 않는 정수 n(1 ≤ n ≤ 10000)가 주어졌을 때, 1로만 이루어진 n의 배수를 찾는 프로그램을 작성하시오.

www.acmicpc.net

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <iostream>
using namespace std;
long long n;
int main() {
    while (cin >> n) {    // while(!cin.eof()) 하면 틀림
        int ans = 1;
        long long div = 1;
        while (div % n != 0) {
            div = div * 10 + 1;
            div %= n;    // 여기가 핵심
                        // (x mod n) == ( (x mod n) mod n)
            ans++;
        }
        cout << ans << '\n';
    }
}
cs
반응형

'백준 > 그리디' 카테고리의 다른 글

백준 1202  (0) 2021.02.12
백준 11000  (0) 2021.02.05
백준 16953  (0) 2021.02.05
백준 2847  (0) 2021.02.05
백준 1439  (0) 2021.02.05
반응형

www.acmicpc.net/problem/1202

 

1202번: 보석 도둑

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci

www.acmicpc.net

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
#include <iostream>
#include <algorithm>
#include <queue>
#define ll long long
#define rep(i,n) for(ll i=0;i<n;i++)
#define pii pair<ll, ll>
using namespace std;
ll n, k, idx, ans;
pii arr[300001];
ll bag[300001];
priority_queue<ll> q;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    rep(i,n)
        cin >> arr[i].first >> arr[i].second;
    
    rep(i,k)
        cin >> bag[i];
 
    sort(arr, arr + n);
    sort(bag, bag + k);
 
    idx = 0;
    ans = 0;
    rep(i, k) {
        while (idx < n && arr[idx].first <= bag[i])
            q.push(arr[idx++].second);
        if (!q.empty()) {
            ans += q.top();
            q.pop();
 
        }
    }
    cout << ans;
}
cs
반응형

'백준 > 그리디' 카테고리의 다른 글

백준 4375  (0) 2021.02.12
백준 11000  (0) 2021.02.05
백준 16953  (0) 2021.02.05
백준 2847  (0) 2021.02.05
백준 1439  (0) 2021.02.05
반응형

www.acmicpc.net/problem/11000

 

11000번: 강의실 배정

첫 번째 줄에 N이 주어진다. (1 ≤ N ≤ 200,000) 이후 N개의 줄에 Si, Ti가 주어진다. (1 ≤ Si < Ti ≤ 109)

www.acmicpc.net

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 <algorithm>
#include <queue>
#define pii pair<int, int>
using namespace std;
priority_queue<int, vector<int>, greater<int> > pq;
int n;
pii arr[200001];
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 0;i < n;i++) 
        cin >> arr[i].first >> arr[i].second;
    sort(arr, arr+n);
    // 배열 -> 시작 시간 오름차순
    // pq -> 종료 시간 오름차순
    // pq의 개수 -> 강의실 개수
    pq.push(arr[0].second);
    for (int i = 1; i < n;i++) {
        if (arr[i].first >= pq.top())
            pq.pop();
        pq.push(arr[i].second);
    }
    cout << pq.size();
}
cs
반응형

'백준 > 그리디' 카테고리의 다른 글

백준 4375  (0) 2021.02.12
백준 1202  (0) 2021.02.12
백준 16953  (0) 2021.02.05
백준 2847  (0) 2021.02.05
백준 1439  (0) 2021.02.05
반응형

www.acmicpc.net/problem/16953

 

16953번: A → B

첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.

www.acmicpc.net

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
using namespace std;
int a, b, cnt, last;
int main() {
    cin >> a >> b;
    
    // 같으면 안됨 (b = -1 -> while 안들어감)
    if (a == b) 
        b = -1;
    
    // b == a 이거나 b < a 이면 벗어남
    while (b>a) {
        last = b % 10;
        // 마지막 숫자가 3, 5, 7, 9 될 수 없음
        if (last > 1 && last % 2 == 1) break;
 
        // 마지막 숫자가 1이면 1 제거
        // 마지막 숫자가 2의 배수이면 2로 나눔
        last == 1 ? b /= 10 : b /= 2;
        cnt++;
    }
    cout << (b == a ? cnt + 1 : -1);
}
 cs
반응형

'백준 > 그리디' 카테고리의 다른 글

백준 1202  (0) 2021.02.12
백준 11000  (0) 2021.02.05
백준 2847  (0) 2021.02.05
백준 1439  (0) 2021.02.05
백준 1449  (0) 2021.02.05
반응형

www.acmicpc.net/problem/2847

 

2847번: 게임을 만든 동준이

학교에서 그래픽스 수업을 들은 동준이는 수업시간에 들은 내용을 바탕으로 스마트폰 게임을 만들었다. 게임에는 총 N개의 레벨이 있고, 각 레벨을 클리어할 때 마다 점수가 주어진다. 플레이어

www.acmicpc.net

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
#include <iostream>
using namespace std;
int n, ans, arr[101];
int main() {
    cin >> n;
    for (int i = 0;i < n;i++)
        cin >> arr[i];
    for (int i = n - 1; i > 0; i--) {
        if (arr[i - 1] >= arr[i]) {
            ans+=arr[i - 1] - (arr[i] - 1);
            arr[i - 1] = arr[i] - 1;
        }
    }
    cout << ans;
}
 cs
반응형

'백준 > 그리디' 카테고리의 다른 글

백준 11000  (0) 2021.02.05
백준 16953  (0) 2021.02.05
백준 1439  (0) 2021.02.05
백준 1449  (0) 2021.02.05
백준 2437  (0) 2021.02.05
반응형

www.acmicpc.net/problem/1439

 

1439번: 뒤집기

다솜이는 0과 1로만 이루어진 문자열 S를 가지고 있다. 다솜이는 이 문자열 S에 있는 모든 숫자를 전부 같게 만들려고 한다. 다솜이가 할 수 있는 행동은 S에서 연속된 하나 이상의 숫자를 잡고 모

www.acmicpc.net

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <iostream>
#include <algorithm>
using namespace std;
int cnt0, cnt1;
int main() {
    string str;
    cin >> str;
    char cur = str[0];
    if (cur == '0')
        cnt0++;
    else
        cnt1++;
    for (char c : str) {
        if (cur != c) {
            if (c == '0')
                cnt0++;
            else
                cnt1++;
            cur = c;
        }
    }
    cout << min(cnt0, cnt1);
}
 cs
반응형

'백준 > 그리디' 카테고리의 다른 글

백준 16953  (0) 2021.02.05
백준 2847  (0) 2021.02.05
백준 1449  (0) 2021.02.05
백준 2437  (0) 2021.02.05
백준 1715  (0) 2021.02.05
반응형

www.acmicpc.net/problem/1449

 

1449번: 수리공 항승

첫째 줄에 물이 새는 곳의 개수 N과 테이프의 길이 L이 주어진다. 둘째 줄에는 물이 새는 곳의 위치가 주어진다. N과 L은 1,000보다 작거나 같은 자연수이고, 물이 새는 곳의 위치는 1,000보다 작거나

www.acmicpc.net

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <iostream>
#include <algorithm>
using namespace std;
int n, l;
int arr[1001];
double tape[1001];
int main() {
    cin >> n >> l;
    for (int i = 0;i < n;i++)
        cin >> arr[i];
    sort(arr, arr + n);
    int tape_idx = 0;
    tape[0] = (double)(arr[0] - 0.5);
    for (int i = 1;i < n;i++) {
        if (arr[i] >= tape[tape_idx] + l) 
            tape[++tape_idx] = arr[i] - 0.5;
        
    }
    cout << tape_idx + 1;
}
cs
반응형

'백준 > 그리디' 카테고리의 다른 글

백준 2847  (0) 2021.02.05
백준 1439  (0) 2021.02.05
백준 2437  (0) 2021.02.05
백준 1715  (0) 2021.02.05
백준 1080  (0) 2021.02.05
반응형

www.acmicpc.net/problem/2437

 

2437번: 저울

하나의 양팔 저울을 이용하여 물건의 무게를 측정하려고 한다. 이 저울의 양 팔의 끝에는 물건이나 추를 올려놓는 접시가 달려 있고, 양팔의 길이는 같다. 또한, 저울의 한쪽에는 저울추들만 놓

www.acmicpc.net

 

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
// https://justicehui.github.io/koi/2018/09/21/BOJ2437/
#include <iostream>
#include <algorithm>
using namespace std;
int n;
int arr[1001];
int sum[1001];
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1;i <= n;i++) 
        cin >> arr[i];
    sort(arr, arr + n+1);
 
    for(int i = 1; i<=n; i++)
        sum[i] = sum[i-1]+arr[i];
 
    int i = 1;
    for (i = 1; i <= n; i++) {
        if (sum[i - 1] + 1 < arr[i]) 
            break;
        
    }
    cout << sum[i - 1] + 1;
}
 cs
반응형

'백준 > 그리디' 카테고리의 다른 글

백준 1439  (0) 2021.02.05
백준 1449  (0) 2021.02.05
백준 1715  (0) 2021.02.05
백준 1080  (0) 2021.02.05
백준 1946  (0) 2021.02.05

+ Recent posts

티스토리툴바