Loading [MathJax]/jax/output/CommonHTML/jax.js
반응형

https://www.acmicpc.net/problem/1132

 

1132번: 합

N개의 수가 주어진다. 이 숫자는 모두 자연수이고, 알파벳 A부터 J가 자리수를 대신해서 쓰여 있다. 이 알파벳은 모두 한 자리를 의미한다. 그리고, 각 자리수는 정확하게 알파벳 하나이다. 0으로

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 각 문자열을 입력받고, 각 알파벳에 따라 자릿수를 arr 배열에 저장하고, 첫 자리에 오는지 오지 않는지 isFirst 배열에 저장합니다.

 

2. arr 배열을 내림차순으로 정렬하고, 만약 가장 작은 자릿수의 숫자가 첫번째 수라면 0이 오면 안 되기 때문에 첫 자리에 오는 수가 없는 알파벳과 교환합니다.

 

3. arr 배열을 내림차순으로 0부터 8번 인덱스까지만 정렬합니다.

 

4. arr 배열을 0부터 9까지 for문을 이용하여 돌면서 0번 인덱스일 경우 9를 곱해주고, 1번 인덱스일 경우 8을 곱해주면서 9번 인덱스까지 ans에 더해줍니다.

 

5. ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
#include<string>
#include<cmath>
#define ll long long
 
using namespace std;
 
int N;
pair<ll,int> arr[26];
bool isFirst[26];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < 26; i++) {
        arr[i].second = i;
    }
 
    for (int i = 0; i < N; i++) {
        string str;
        cin >> str;
        isFirst[str[0] - 'A'] = true;
 
        for (int j = 0; j < str.size(); j++) {
            arr[str[j] - 'A'].first += pow(10, str.size() - j - 1);
        }
    }
 
    sort(arr, arr + 26, greater<>());
 
    if (isFirst[arr[9].second]) {
        for (int i = 8; i >= 0; i--) {
            if (isFirst[arr[i].second] == false) {
                swap(arr[9], arr[i]);
                break;
            }
        }
    }
 
    sort(arr, arr + 9, greater<>());
 
    ll ans = 0;
    int cnt = 9;
 
    for (int i = 0; i < 10; i++) {
        ans += arr[i].first * cnt--;
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 14881번 - 물통 문제 (C++)  (0) 2023.10.25
[ 백준 ] 20917번 - 사회적 거리 두기 (C++)  (0) 2023.10.24
[ 백준 ] 4395번 - Steps (C++)  (0) 2023.10.22
[ 백준 ] 17433번 - 신비로운 수 (C++)  (0) 2023.10.21
[ 백준 ] 1684번 - 같은 나머지 (C++)  (0) 2023.10.20
반응형

https://www.acmicpc.net/problem/25498

 

25498번: 핸들 뭘로 하지

효규가 얻을 수 있는 문자열은 사전순으로 "aa", "aaa", "aaaa", "aaaa"이므로 "aaaa"를 핸들로 정한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 문자열과 그래프를 입력받고, arr[500001]과 vector<int> list[500001]에 저장합니다.

 

2. node struct를 만들어 현재 노드의 번호, 인덱스 그리고 부모의 문자를 저장합니다.

 

3. queue<node> q를 만들어 bfs를 돌면서 해당 인덱스에서 가장 큰 문자를 ans에 더해주면서 문자열을 완성합니다.

 

4. ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
#include<queue>
#include<string>
 
using namespace std;
 
struct node {
    int cur, idx;
    char parent;
};
 
int N;
char arr[500001];
vector<int> list[500001];
int visited[500001];
string ans;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> arr;
 
    for (int i = 0; i < N - 1; i++) {
        int u, v;
        cin >> u >> v;
        list[u].push_back(v);
        list[v].push_back(u);
    }
 
    queue<node> q;
    q.push({ 1, 1, '0'});
    visited[1] = 1;
    ans += '0';
 
    while (!q.empty()) {
        const int cur = q.front().cur;
        const int idx = q.front().idx;
        const char pa = q.front().parent;
        q.pop();
 
        if (pa != ans[idx - 1]) continue;
        if (idx >= ans.size()) ans += arr[cur - 1];
        else if (ans[idx] < arr[cur - 1]) {
            ans[idx] = arr[cur - 1];
        }
 
        for (auto& next : list[cur]) {
            if (visited[next] != 1) {
                visited[next] = 1;
                q.push({ next,idx + 1, arr[cur - 1]});
            }
        }
    }
 
    ans.erase(ans.begin());
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 5069번 - 미로에 갇힌 상근 (C++)  (0) 2023.10.15
[ 백준 ] 1737번 - Pibonacci (C++)  (0) 2023.10.14
[ 백준 ] 19942번 - 다이어트 (C++)  (0) 2023.10.12
[ 백준 ] 21276번 - 계보 복원가 호석 (C++)  (0) 2023.10.11
[ 백준 ] 17085번 - 십자가 2개 놓기 (C++)  (0) 2023.10.10
반응형

https://www.acmicpc.net/problem/1461

 

1461번: 도서관

세준이는 도서관에서 일한다. 도서관의 개방시간이 끝나서 세준이는 사람들이 마구 놓은 책을 다시 가져다 놓아야 한다. 세준이는 현재 0에 있고, 사람들이 마구 놓은 책도 전부 0에 있다. 각 책

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. vector<int> L, R을 선언하고, 좌표가 음수라면 L에 push, 좌표가 양수라면 R에 push합니다.

 

2. L은 내림차순으로 정렬하고, R은 오름차순으로 정렬합니다.

 

3. L과 R의 끝 좌표부터 책을 옮기고 책의 원래 좌표 * 2 를 ans에 더해줍니다.

 

4. L과 R의 끝 좌표중 더 큰 값을 ans에서 빼주고, ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
int N, M;
vector<int> L, R;
int ans;
int Max;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> M;
 
    for (int i = 0; i < N; i++) {
        int n;
        cin >> n;
        if (n < 0) {
            L.push_back(n);
        }
        else {
            R.push_back(n);
        }
    }
 
    sort(R.begin(), R.end());
    sort(L.begin(), L.end(), greater<>());
 
    for (int i = R.size() - 1; i >= 0; i -= M) {
        ans += R[i] * 2;
    }
 
    for (int i = L.size() - 1; i >= 0; i -= M) {
        ans += -L[i] * 2;
    }
 
    if (!R.empty()) Max = max(Max, *R.rbegin());
    if (!L.empty()) Max = max(Max, -(*L.rbegin()));
 
    cout << ans - Max;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 2186번 - 문자판 (C++)  (1) 2023.10.05
[ 백준 ] 2661번 - 좋은수열 (C++)  (1) 2023.10.04
[ 백준 ] 1354번 - 무한 수열 2 (C++)  (0) 2023.10.02
[ 백준 ] 2174번 - 로봇 시뮬레이션 (C++)  (0) 2023.10.01
[ 백준 ] 14719번 - 빗물 (C++)  (0) 2023.09.30
반응형

https://www.acmicpc.net/problem/1339

 

1339번: 단어 수학

첫째 줄에 단어의 개수 N(1 ≤ N ≤ 10)이 주어진다. 둘째 줄부터 N개의 줄에 단어가 한 줄에 하나씩 주어진다. 단어는 알파벳 대문자로만 이루어져있다. 모든 단어에 포함되어 있는 알파벳은 최대

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 각 문자의 자릿수 값을 저장할 box 배열을 선언합니다.

 

2. 각 단어가 입력될 때마다 각 자릿수의 문자에 10의 n승을 곱해 더해줍니다.

 

3. box 배열을 내림차순으로 정렬하고, box[ 0 ] ~ box[ 9 ] 까지의 값에 9 ~ 0의 값을 곱해 더해준 값을 출력합니다.

 

[ 소스코드 ]

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<iostream>
#include<string>
#include<cmath>
#include<algorithm>
 
using namespace std;
 
int N;
int box[26];
int ans;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        string str;
        cin >> str;
 
        for (int j = 0; j < str.size(); j++) {
            box[str[j] - 'A'] += pow(10, str.size() - j - 1);
        }
    }
 
    sort(box, box + 26, greater<>());
 
    int seq = 0;
 
    for (int i = 9; i >= 0; i--) {
        ans += box[seq] * i;
        seq++;
    }
 
    cout << ans;
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 1486번 - 등산 (C++)  (0) 2023.09.03
[ 백준 ] 7299번 - Food Cubes (C++)  (0) 2023.09.02
[ 백준 ] 6067번 - Guarding the Farm (C++)  (0) 2023.08.31
[ 백준 ] 2610번 - 회의준비 (C++)  (0) 2023.08.30
[ 백준 ] 28421번 - 곱하기와 쿼리 (C++)  (0) 2023.08.29
반응형

https://www.acmicpc.net/problem/19940

 

19940번: 피자 오븐

각각의 테스트 케이스마다 5개의 정수를 한 줄에 공백으로 구분해서 출력한다. 이 정수는 입력으로 주어진 시간을 만들기 위해서 ADDH, ADDT, MINT, ADDO, MINO 버튼을 누르는 횟수를 출력한 것이다. 최

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 1분에서 65분까지의 최소 누르는 횟수를 저장합니다.

 

2. N을 60으로 나눈 값을 ADDH에 더해주고, N을 60으로 나눈 나머지 값을 이용하여 최소 누르는 횟수를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
 
using namespace std;
 
int T, N;
int visited[66];
 
struct node {
    int cur;
    int ans[5] = { 0 };
};
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> T;
 
    for (int t = 0; t < T; t++) {
        cin >> N;
        int temp = N / 60;
        N %= 60;
 
        queue<node> q;
        
        fill(visited, visited + 66, 0);
 
        q.push({ 0,{temp} });
        visited[0] = 1;
 
        while (!q.empty()) {
            const int cur = q.front().cur;
            int ans[5] = { 0 };
            for (int i = 0; i < 5; i++) {
                ans[i] = q.front().ans[i];
            }
            q.pop();
 
            if (cur == N) {
                for (int i = 0; i < 5; i++) {
                    cout << ans[i] << ' ';
                }
                cout << '\n';
                break;
            }
 
            if (cur - 1 >= 0 && visited[max(0, cur - 1)] == 0) {
                visited[cur - 1] = 1;
                q.push({ cur - 1, {ans[0],ans[1],ans[2],ans[3],ans[4] + 1} });
            }
 
            if (cur + 1 <= 65 && visited[cur + 1] == 0) {
                visited[cur + 1] = 1;
                q.push({ cur + 1, {ans[0],ans[1],ans[2],ans[3] + 1,ans[4]} });
            }
 
            if (cur - 10 >= 0 && visited[cur - 10] == 0) {
                visited[cur - 10] = 1;
                q.push({ cur - 10, {ans[0],ans[1],ans[2] + 1,ans[3],ans[4]} });
            }
 
            if (cur + 10 <= 65 && visited[cur + 10] == 0) {
                visited[cur + 10] = 1;
                q.push({ cur + 10, {ans[0],ans[1] + 1,ans[2],ans[3],ans[4]} });
            }
 
            if (cur + 60 <= 65 && visited[cur + 60] == 0) {
                visited[cur + 60] = 1;
                q.push({ cur + 60, {ans[0] + 1,ans[1],ans[2],ans[3],ans[4]} });
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 15967번 - 에바쿰 (C++)  (0) 2023.08.02
[ 백준 ] 16978번 - 수열과 쿼리 22 (C++)  (0) 2023.08.01
[ 백준 ] 14852번 - 타일 채우기 3 (C++)  (0) 2023.07.30
[ 백준 ] 16954번 - 움직이는 미로 탈출 (C++)  (0) 2023.07.29
[ 백준 ] 16509번 - 장군 (C++)  (0) 2023.07.28
반응형

https://www.acmicpc.net/problem/2513

 

2513번: 통학버스

첫째 줄에는 세 개의 양의 정수 N, K, S가 빈칸을 사이에 두고 순서대로 주어진다. 첫 번째 정수 N은 아파트 단지의 수이며 2 ≤ N ≤ 30,000이다. 두 번째 정수 K는 1 ≤ K ≤ 2,000이며, 통학버스의 정원

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 좌표와 사람 수의 쌍을 입력받고, 좌표가 S보다 작다면  arr1에, S보다 크다면 arr2에 저장합니다.

 

2. arr1은 좌표를 기준으로 오름차순으로 정렬하고, arr2는 좌표를 기준으로 내림차순으로 정렬합니다.

 

3. 학교를 기준으로 가장 먼 지역부터 버스를 운행해서 해당 좌표에 사람이 K보다 많거나 같다면 왕복 거리를 ans에 더해주고, 나은 사람들을 버스에 태웁니다.

 

4. 3과 마찬가지로 K보다 많거나 같은 사람들을 먼저 처리하고, 버스에 타고 있는 사람 + 현재 좌표에 남은 사람의 수가 K보다 크다면 왕복 거리를 ans에 더해주고, bus의 사람 수를 bus = bus + cnt - K로 저장해 줍니다.

 

5. 3과 4를 반복하고, 마지막에 ans를 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<algorithm>
#include<vector>
 
using namespace std;
 
int N, K, S;
vector<pair<int, int>> arr1;
vector<pair<int, int>> arr2;
 
int main()
{
    scanf("%d %d %d", &N, &K, &S);
 
    for (int i = 0; i < N; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
 
        if (a < S) {
            arr1.push_back({ a,b });
        }
        else {
            arr2.push_back({ a,b });
        }
    }
 
    sort(arr1.begin(), arr1.end());
    sort(arr2.begin(), arr2.end(), greater<>());
 
    int ans = 0;
 
    int bus = 0;
 
    for (auto& next : arr1) {
        const int pos = next.first;
        int cnt = next.second;
 
        if (cnt >= K) {
            ans += (S - pos) * 2 * (int)(cnt / K);
            cnt %= K;
        }
        
        if (cnt > 0) {
            if (bus == 0) {
                ans += (S - pos) * 2;
                bus = cnt;
            }
            else {
                if (bus + cnt > K) {
                    ans += (S - pos) * 2;
                    bus = bus + cnt - K;
                }
                else {
                    bus += cnt;
                }
            }
        }
    }
 
    bus = 0;
 
    for (auto& next : arr2) {
        const int pos = next.first;
        int cnt = next.second;
 
        if (cnt >= K) {
            ans += (pos - S) * 2 * (int)(cnt / K);
            cnt %= K;
        }
 
        if (cnt > 0) {
            if (bus == 0) {
                ans += (pos - S) * 2;
                bus = cnt;
            }
            else {
                if (bus + cnt > K) {
                    ans += (pos - S) * 2;
                    bus = bus + cnt - K;
                }
                else {
                    bus += cnt;
                }
            }
        }
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 25545번 - MMST (C++)  (0) 2023.04.29
[ 백준 ] 10836번 - 여왕벌 (C++)  (0) 2023.04.28
[ 백준 ] 9370번 - 미확인 도착지 (C++)  (0) 2023.04.26
[ 백준 ] 2671번 - 잠수함식별 (C++)  (0) 2023.04.25
[ 백준 ] 17218번 - 비밀번호 만들기 (C++)  (0) 2023.04.24
반응형

https://www.acmicpc.net/problem/11000

 

11000번: 강의실 배정

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

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. priority_queue를 만들고, 시간을 기준으로 오름차순으로 정렬하되 시간이 같으면 끝나는 시간이 앞으로 오도록 우선순위를 정합니다.

 

2. pq에서 값을 하나씩 꺼내면서 temp에 시작하는 시간이면 1을 더하고, 끝나는 시간이면 1을 빼줍니다.

 

3. temp의 값 중 가장 큰 값을 ans에 저장합니다.

 

4. ans를 출력합니다.

 

[ 소스코드 ]

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<iostream>
#include<queue>
 
using namespace std;
 
int N;
 
struct Class {
    char cur;
    int time;
};
 
struct cmp {
    bool operator()(Class right, Class left) {
        if (right.time == left.time) {
            if (left.cur == 'e') {
                return true;
            }
            else {
                return false;
            }
        }
        else {
            return left.time < right.time;
        }
    }
};
 
int main()
{
    priority_queue<Class, vector<Class>, cmp> pq;
 
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        int S, T;
        scanf("%d %d", &S, &T);
 
        pq.push({ 's', S});
        pq.push({ 'e', T});
    }
 
    int ans = 0;
    int temp = 0;
 
    while (!pq.empty()) {
        const char cur = pq.top().cur;
        pq.pop();
 
        if (cur == 's') temp++;
        else temp--;
 
        ans = max(ans, temp);
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 17218번 - 비밀번호 만들기 (C++)  (0) 2023.04.24
[ 백준 ] 6987번 - 월드컵 (C++)  (0) 2023.04.23
[ 백준 ] 20311번 - 화학 실험 (C++)  (0) 2023.04.21
[ 백준 ] 11562번 - 백양로 브레이크 (C++)  (0) 2023.04.20
[ 백준 ] 2032번 - 신기한 소수 (C++)  (0) 2023.04.19
반응형

https://www.acmicpc.net/problem/20311

 

20311번: 화학 실험

화학 실험을 하던 윤이는 일렬로 나열해 놓은 N개의 시험관에서 재밌는 특징을 발견했다. 그 특징은 모든 이웃한 시험관 쌍에 대해, 두 시험관에 들어 있는 시약의 색깔이 서로 다르다는 점이

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 시험관의 개수를 입력받고, priority_queue에 내림차순으로 정렬합니다.

 

2. 만약 수가 가장 많은 시험관의 개수가 (N + 1) / 2개보다 많다면 -1을 출력합니다.

 

3. pq에서 값을 하나씩 뽑아 arr 배열에 시험관의 색깔 번호를 넣습니다.

 

4. 0 ~ (N + 1) / 2 - 1까지 arr 배열의 값을 ans의 0부터 2씩 인덱스를 증가시켜 가면서 넣습니다.

 

5. (N + 1) / 2 ~ N - 1까지 arr배열의 값을 ans의 1부터 2씩 인덱스를 증가시켜 가면서 넣습니다.

 

6. ans 배열을 출력합니다.

 

[ 소스코드 ]

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>
#include<vector>
#include<queue>
 
using namespace std;
 
int N, K;
vector<int> arr;
int ans[300000];
 
int main()
{
    priority_queue<pair<int, int>>pq;
    scanf("%d %d", &N, &K);
 
    for (int i = 1; i <= K; i++) {
        int c;
        scanf("%d", &c);
 
        pq.push({ c,i });
    }
 
    if (pq.top().first > (N + 1) / 2) {
        printf("-1");
        return 0;
    }
 
    while (!pq.empty()) {
        const int cnt = pq.top().first;
        const int num = pq.top().second;
        pq.pop();
 
        for (int i = 0; i < cnt; i++) {
            arr.push_back(num);
        }
    }
    
    int num = 0;
 
    for (int i = 0; i < (N + 1) / 2; i++) {
        ans[num] = arr[i];
        num += 2;
    }
 
    num = 1;
 
    for (int i = (N+1)/2; i < N; i++) {
        ans[num] = arr[i];
        num += 2;
    }
 
    for (int i = 0; i < N; i++) {
        printf("%d ", ans[i]);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 6987번 - 월드컵 (C++)  (0) 2023.04.23
[ 백준 ] 11000번 - 강의실 배정 (C++)  (0) 2023.04.22
[ 백준 ] 11562번 - 백양로 브레이크 (C++)  (0) 2023.04.20
[ 백준 ] 2032번 - 신기한 소수 (C++)  (0) 2023.04.19
[ 백준 ] 2602번 - 돌다리 건너기 (C++)  (0) 2023.04.18
반응형

https://www.acmicpc.net/problem/1781

 

1781번: 컵라면

상욱 조교는 동호에게 N개의 문제를 주고서, 각각의 문제를 풀었을 때 컵라면을 몇 개 줄 것인지 제시 하였다. 하지만 동호의 찌를듯한 자신감에 소심한 상욱 조교는 각각의 문제에 대해 데드라

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 데드라인과 컵라면 개수를 입력받고 arr 배열에 저장합니다.

 

2. arr배열을 데드라인을 기준으로 오름차순으로 정렬합니다.

 

3. 1부터 N까지 for문을 통해 돌면서 priority_queue에 넣어주고, arr[ i ]의 데드라인보다 pq.size()가 크면 pq.pop()을 해줍니다.

 

4. pq에 있는 모든 값을 더하고, 출력합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<queue>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int N;
int ans;
 
int main()
{
    priority_queue<int, vector<int>, greater<int>> pq;
    vector<pair<int, int>> arr;
    
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
 
        arr.push_back({ a,b });
    }
 
    sort(arr.begin(), arr.end());
 
    for (int i = 0; i < N; i++) {
        pq.push(arr[i].second);
        
        if (arr[i].first < pq.size()) {
            pq.pop();
        }
    }
 
    while (!pq.empty()) {
        ans += pq.top();
        pq.pop();
    }
 
    printf("%d", ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 14921번 - 용액 합성하기 (C++)  (0) 2023.03.29
[ 백준 ] 11265번 - 끝나지 않는 파티 (C++)  (0) 2023.03.28
[ 백준 ] 15989번 - 1, 2, 3 더하기 4 (C++)  (0) 2023.03.26
[ 백준 ] 23286번 - 허들 넘기 (C++)  (0) 2023.03.25
[ 백준 ] 15422번 - Bumped! (C++)  (0) 2023.03.24
반응형

https://www.acmicpc.net/problem/7570

 

7570번: 줄 세우기

입력은 2 개의 줄로 이루어져 있다. 첫 줄에는 어린이 수를 나타내는 정수가 주어진다. 둘째 줄에는 처음에 줄서있는 어린이들의 번호가 차례대로 주어진다. 주어진 번호들 사이에는 공백이 하

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 어린이가 항상 맨 뒤나 맨 앞으로 가야 하므로 일반적인 증가하는 부분 수열이 아닌 연속으로 증가하는 최장 부분 수열을 찾아야 합니다. ex) 2, 4, 7 (x)     3, 4, 5 (o)

 

2. 겹치는 수가 없기 때문에 cnt 배열을 통해 각각의 수가 몇번 째 증가하는 수인지를 저장합니다.

 

3. cnt[ i ] = cnt[ arr[ i ] - 1 ]+1의 점화식을 활용하여 값을 저장해 줍니다.

 

4. ans = max(ans, cnt[ i ])를 통해 최장 연속 증가 부분 수열의 길이를 저장합니다.

 

5. N - ans를 출력합니다.

 

[ 소스코드 ]

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>
 
using namespace std;
 
int N;
int arr[1000000];
int cnt[1000001];
int ans;
 
int main()
{
    scanf("%d", &N);
 
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }
    
    for (int i = 0; i < N; i++) {
        cnt[arr[i]] = cnt[arr[i] - 1] + 1;
        ans = max(ans, cnt[arr[i]]);
    }
 
    printf("%d", N - ans);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

'백준' 카테고리의 다른 글

[ 백준 ] 14621번 - 나만 안되는 연애 (C++)  (0) 2023.02.16
[ 백준 ] 1937번 - 욕심쟁이 판다 (C++)  (0) 2023.02.15
[ 백준 ] 11085번 - 군사 이동 (C++)  (0) 2023.02.13
[ 백준 ] 2565번 - 전깃줄 (C++)  (0) 2023.02.12
[ 백준 ] 17836번 - 공주님을 구해라! (C++)  (0) 2023.02.11

+ Recent posts

티스토리툴바