반응형

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
반응형

www.acmicpc.net/problem/1715

 

1715번: 카드 정렬하기

정렬된 두 묶음의 숫자 카드가 있다고 하자. 각 묶음의 카드의 수를 A, B라 하면 보통 두 묶음을 합쳐서 하나로 만드는 데에는 A+B 번의 비교를 해야 한다. 이를테면, 20장의 숫자 카드 묶음과 30장

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
#include <iostream>
#include <queue>
using namespace std;
priority_queue<int, vector<int>, greater<int> > q;
int n, x, ans;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    while (n--) {
        cin >> x;
        q.push(x);
    }
    while (q.size()!=1) {
        int a = q.top();
        q.pop();
        int b = q.top();
        q.pop();
        int c = a + b;
        ans += c;
        q.push(c);
    }
    cout << ans;
}
 cs
반응형

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

백준 1449  (0) 2021.02.05
백준 2437  (0) 2021.02.05
백준 1080  (0) 2021.02.05
백준 1946  (0) 2021.02.05
백준 2812  (0) 2021.02.04
반응형

www.acmicpc.net/problem/1080

 

1080번: 행렬

첫째 줄에 행렬의 크기 N M이 주어진다. N과 M은 50보다 작거나 같은 자연수이다. 둘째 줄부터 N개의 줄에는 행렬 A가 주어지고, 그 다음줄부터 N개의 줄에는 행렬 B가 주어진다.

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
// https://mizzo-dev.tistory.com/entry/baekjoon1080
#include <iostream>
#define rep(i,n) for(int i=0;i<n;i++)
using namespace std;
int n, m;
char arr1[51][51], arr2[51][51];
bool chk[51][51];
int cnt;
void convert(int x, int y) {
    if (x + 2 >= n) return;                // 세로 범위 벗어남
    if (y + 2 >= m) return;                // 가로 범위 벗어남
    for (int i = x; i < x + 3; i++) {
        for (int j = y; j < y + 3; j++) // 0, 1 토글
            chk[i][j] = !chk[i][j];
    }
    cnt++;
}
void func(){
    for (int i = 0;i < n; i++) {
        for (int j = 0;j < m;j++) {
            if (chk[i][j])                // A, B 다르면 -> chk[i][j] == 1
                convert(i, j);
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> n >> m;
    rep(i, n) {
        rep(j, m)
            cin >> arr1[i][j];
    }
    rep(i, n) {
        rep(j, m) {
            cin >> arr2[i][j];
            if (arr1[i][j] != arr2[i][j])    // A, B 다르면 1
                chk[i][j] = 1;
        }
    }
    func();
    rep(i, n) {
        rep(j, m) {
            if (chk[i][j]) {
                cout << -1;
                return 0;
            }
        }
    }
    cout << cnt;
}
cs
반응형

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

백준 2437  (0) 2021.02.05
백준 1715  (0) 2021.02.05
백준 1946  (0) 2021.02.05
백준 2812  (0) 2021.02.04
백준 13305  (0) 2021.01.27
반응형

www.acmicpc.net/problem/1946

 

1946번: 신입 사원

첫째 줄에는 테스트 케이스의 개수 T(1 ≤ T ≤ 20)가 주어진다. 각 테스트 케이스의 첫째 줄에 지원자의 숫자 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개 줄에는 각각의 지원자의 서류심사 성

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
#include <iostream>
#include <algorithm>
#define rep(i,n) for(int i=0;i<n;i++)
#define pii pair<int, int>
using namespace std;
int t, n, ans;
pii arr[100001];
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> t;
    while (t--) {
        ans = 0;
        cin >> n;
        rep(i, n)
            cin >> arr[i].first >> arr[i].second;
 
        sort(arr, arr + n);                // 서류 순위 정렬
        ans++;
        int rank = arr[0].second;        // 면접 순위 최솟값
        for(int i = 1; i<n; i++) {
            if (arr[i].second < rank) {    // 내 앞사람보다 면접 순위 높으면
                rank = arr[i].second;    // 면접 순위 최솟값 갱신
                ans++;                    // 뽑힌 사람 수 증가
            }
        }
        cout << ans << '\n';
    }
}
cs
반응형

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

백준 1715  (0) 2021.02.05
백준 1080  (0) 2021.02.05
백준 2812  (0) 2021.02.04
백준 13305  (0) 2021.01.27
백준 11509  (0) 2021.01.26
반응형

www.acmicpc.net/problem/15686

 

15686번: 치킨 배달

크기가 N×N인 도시가 있다. 도시는 1×1크기의 칸으로 나누어져 있다. 도시의 각 칸은 빈 칸, 치킨집, 집 중 하나이다. 도시의 칸은 (r, c)와 같은 형태로 나타내고, r행 c열 또는 위에서부터 r번째 칸

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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <algorithm>
#define rep(i,n) for(int i=1;i<=n;i++)
using namespace std;
int n, m, arr[51][51];
int cnt = 0, ans = 987654321;
/*
    도시의 치킨 거리 = 모든 집의 치킨 거리의 합
    치킨 거리 = 현재 집에서 가장 가까운 치킨집과의 거리
    m개 남기고 나머지 다 폐업
*/
int chk() {
    int ret = 0;
    rep(i, n) {
        rep(j, n) {
            if (arr[i][j] == 1) {                                        // 현재 위치가 가정집이면
                int tmp = 987654321;
                rep(a, n) {
                    rep(b, n) {
                        if (arr[a][b] == 2)                                // 모든 치킨집과의 거리 계산
                            tmp = min(tmp, abs(i - a) + abs(j - b));    // 최솟값 저장
                        
                    }
                }
                ret += tmp;                                    // 도시의 치킨 거리 += 현재 집의 치킨 거리
            }
        }
    }
    return ret;
}
void dfs(int x, int y, int now) {
    if (now == m) {                    // m개만 남았으면 거리 체크
        ans = min(ans, chk());
        return;
    }
 
    for (int i = x; i <= n; i++) {
        y = 1;
        for (int j = y; j <= n; j++) {
            if (arr[i][j] == 2) {    // 치킨집 찾으면 0으로 변경
                arr[i][j] = 0;        // 폐업
                dfs(i, j, now - 1);    // 개수 1개 줄이고 계속 탐색
                arr[i][j] = 2;        // 다음 탐색을 위해 복구
            }
        }
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> m;
    rep(i, n) {
        rep(j, n) {
            cin >> arr[i][j];
            if (arr[i][j] == 2)
                cnt++;
        }
    }
    dfs(1, 1, cnt);
    cout << ans;
}
cs
반응형

'백준 > 삼성기출' 카테고리의 다른 글

백준 14501  (0) 2021.02.15
백준 14500  (0) 2021.02.13
백준 14502  (0) 2021.02.03
백준 15684  (0) 2021.02.03
백준 14889  (0) 2021.01.29
반응형

www.acmicpc.net/problem/2812

 

2812번: 크게 만들기

N자리 숫자가 주어졌을 때, 여기서 숫자 K개를 지워서 얻을 수 있는 가장 큰 수를 구하는 프로그램을 작성하시오.

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
#include <iostream>
#include <deque>
using namespace std;
int n, k, idx;
string str;
deque<char> d;
// 내 앞에 나보다 더 큰게 있으면 그거 삭제
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n >> k;
    cin >> str;
    
    idx = 0;
    while (idx < str.length()) {
        while (k>0 && !d.empty() && d.back() < str[idx]) {
            d.pop_back();
            k--;
        }
        d.push_back(str[idx++]);
 
    }
    // while에서 k가 0까지 감소하지 않는 경우 때문에
    // 출력할 때 남은 k만큼 빼서 출력
    while (k--)
        d.pop_back();
    for (char c : d)
        cout << c;
}
cs
반응형

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

백준 1715  (0) 2021.02.05
백준 1080  (0) 2021.02.05
백준 1946  (0) 2021.02.05
백준 13305  (0) 2021.01.27
백준 11509  (0) 2021.01.26

+ Recent posts

티스토리툴바