반응형

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

 

14459번: 소가 길을 건너간 이유 11

우리는 존의 고민을 해결해 줄 방법을 찾았지만, 그걸 알려 주러 가다가 길을 잃었다. 존의 농장에 가긴 했지만, 2N개의 목초지는 없고 웬 N×N 격자가 있는 것이다. 알고 보니 우리는 동명이인의

www.acmicpc.net

 

 

[ 문제풀이 ]

 

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/175

 

[ 알고리즘 ] 최장 증가 부분 수열(Longest Increasing Subsequence)

1. 최장 증가 부분 수열(Longest Increasing Subsequence)이란? 어떠한 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열을 '부분 수열'이라고 하며, 이 수열이 오름차순을 유지하면 '증

rudalsd.tistory.com

 

1. a 배열을 만들어 왼쪽 소들의 종 번호의 인덱스를 저장하고, b 배열을 만들어 오른쪽 소들의 종 번호의 인덱스를 저장합니다.

 

2. 이중 for문을 이용하여 절댓값의 차이가 4 이하인 쌍을 vector<pair<int,int>>에 저장합니다.

 

3. 이 때 first의 값을 기준으로 오름차순, second의 값을 기준으로 내림차순으로 정렬합니다.

 

4. lower_bound를 이용하여 LIS를 만들어 주고, LIS의 길이를 출력해 줍니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int N;
int a[100001];
int b[100001];
vector<pair<int, int>> arr;
 
bool cmp(pair<int, int> left, pair<int, int> right) 
{
    if (left.first == right.first) return left.second > right.second;
    return left.first < right.first;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 1; i <= N; i++) {
        int n;
        cin >> n;
        a[n] = i;
    }
 
    for (int i = 1; i <= N; i++) {
        int n;
        cin >> n;
        b[n] = i;
    }
 
    for (int i = 1; i <= N; i++) {
        for (int j = max(1, i - 4); j <= min(N, i + 4); j++) {
            arr.push_back({ a[i], b[j] });
        }
    }
 
    sort(arr.begin(), arr.end(), cmp);
 
    vector<int>lis;
 
    for (auto& next : arr) {
        if (lis.empty()) {
            lis.push_back(next.second);
        }
        else {
            auto it = lower_bound(lis.begin(), lis.end(), next.second);
            if (it == lis.end()) {
                lis.push_back(next.second);
            }
            else {
                *it = next.second;
            }
        }
    }
 
    cout << lis.size();
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 5012번 - 불만 정렬 (C++)  (0) 2023.08.05
[ 백준 ] 17408번 - 수열과 쿼리 24 (C++)  (0) 2023.08.04
[ 백준 ] 15967번 - 에바쿰 (C++)  (0) 2023.08.02
[ 백준 ] 16978번 - 수열과 쿼리 22 (C++)  (0) 2023.08.01
[ 백준 ] 19940번 - 피자 오븐 (C++)  (0) 2023.07.31
반응형

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

 

15967번: 에바쿰

재성이가 재혁이를 때린 날수 N과 재성이가 변덕을 부린 날의 개수 Q1, 재혁이가 얼마나 맞았는지 궁금한 구간의 개수 Q2가 주어진다. (1 ≤ N ≤ 1,000,000, 0 ≤ Q1, Q2 ≤ 10,000) 그 다음줄엔 재혁이가 i

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/256

 

[ 자료구조 ] 느리게 갱신되는 세그먼트 트리 (Lazy Propagation)

https://rudalsd.tistory.com/51 [ 자료구조 ] 세그먼트 트리 (Segment Tree) 1. 세그먼트 트리 (Segment Tree) 먼저, 세그먼트 트리가 무엇인지 알아봅시다! 세그먼트 트리는 구간 합을 저장하기 위한 트리입니다.

rudalsd.tistory.com

 

1. 느리게 갱신되는 세그먼트 트리를 이용하여 세그먼트 트리를 업데이트해줍니다.

 

2. 구간 합을 쿼리에 맞게 출력해 줍니다.

 

[ 소스코드 ]

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
#include<iostream>
#define ll long long
 
using namespace std;
 
ll segTree[2100000];
int lazy[2100000];
int N, Q1, Q2;
int arr[1000001];
 
void updateLazy(int node, int s, int e)
{
    if (lazy[node]) {
        segTree[node] += 1LL * lazy[node] * (1LL * e - s + 1);
        if (s != e) {
            lazy[node * 2] += lazy[node];
            lazy[node * 2 + 1] += lazy[node];
        }
        lazy[node] = 0;
    }
}
 
void makeTree(int node, int s, int e)
{
    if (s == e) {
        segTree[node] = arr[s];
        return;
    }
 
    int m = (s + e) / 2;
    makeTree(node * 2, s, m);
    makeTree(node * 2 + 1, m + 1, e);
 
    segTree[node] = segTree[node * 2] + segTree[node * 2 + 1];
}
 
void updateTree(int node, int s, int e, int sidx, int eidx, int diff)
{
    updateLazy(node, s, e);
 
    if (s > eidx || e < sidx) return;
    if (sidx <= s && e <= eidx) {
        segTree[node] += 1LL * diff * (1LL * e - s + 1);
        if (s != e) {
            lazy[node * 2] += diff;
            lazy[node * 2 + 1] += diff;
        }
        return;
    }
    
    int m = (s + e) / 2;
    updateTree(node * 2, s, m, sidx, eidx, diff);
    updateTree(node * 2 + 1, m + 1, e, sidx, eidx, diff);
 
    segTree[node] = segTree[node * 2] + segTree[node * 2 + 1];
}
 
ll getTree(int node, int s, int e, int sidx, int eidx)
{
    updateLazy(node, s, e);
 
    if (s > eidx || e < sidx) return 0;
    if (sidx <= s && e <= eidx) return segTree[node];
 
    int m = (s + e) / 2;
    ll left = getTree(node * 2, s, m, sidx, eidx);
    ll right = getTree(node * 2 + 1, m + 1, e, sidx, eidx);
 
    return left + right;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> Q1 >> Q2;
 
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
    }
 
    makeTree(1, 1, N);
 
    for (int i = 0; i < Q1 + Q2; i++) {
        int cmd;
        cin >> cmd;
 
        if (cmd == 1) {
            int n, m;
            cin >> n >> m;
            cout << getTree(1, 1, N, n, m) << '\n';
        }
        else {
            int s, e, l;
            cin >> s >> e >> l;
            updateTree(1, 1, N, s, e, l);
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 17408번 - 수열과 쿼리 24 (C++)  (0) 2023.08.04
[ 백준 ] 14459번 - 소가 길을 건너간 이유 11 (C++)  (0) 2023.08.03
[ 백준 ] 16978번 - 수열과 쿼리 22 (C++)  (0) 2023.08.01
[ 백준 ] 19940번 - 피자 오븐 (C++)  (0) 2023.07.31
[ 백준 ] 14852번 - 타일 채우기 3 (C++)  (0) 2023.07.30
반응형

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

 

16978번: 수열과 쿼리 22

길이가 N인 수열 A1, A2, ..., AN이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오. 1 i v: Ai = v로 변경한다. 2 k i j: k번째 1번 쿼리까지 적용되었을 때, Ai, Ai+1, ..., Aj의 합을 출력한다.

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/364

 

[ 자료구조 ] 비재귀 세그먼트 트리 (Segment Tree)

1. 비재귀 세그먼트 트리 (Segment Tree) 재귀 세그먼트 트리에서는 항상 루트노드부터 시작했었습니다. 하지만 비재귀 세그먼트 트리에서는 반대로 리프노드부터 시작합니다. 2. 비재귀 세그먼트

rudalsd.tistory.com

 

1. arr배열에 수열을 입력받고, 비재귀세그먼트 트리를 이용하여 구간합을 구해줍니다.

 

2. cmd가 1인 쿼리와 2인 쿼리를 각각 저장하고, cmd가 2인 쿼리를 k를 기준으로 오름차순으로 정렬합니다.

 

3. 현재 상태에서 cmd가 1인 k번 쿼리까지 진행해 준 후, cmd가 2인 쿼리를 진행하고, 순서에 맞게 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
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
#include<iostream>
#include<vector>
#include<algorithm>
#define ll long long
 
using namespace std;
 
struct query2 {
    int k, i, j;
    int seq;
};
 
struct cmp {
    bool operator()(query2 left, query2 right) {
        return left.k < right.k;
    }
};
 
int N, M;
ll segTree[200000];
vector<pair<int, int>> query;
vector<query2> queryArr;
ll ans[100000];
int arr[100001];
 
void updateTree(int idx, int n)
{
    while (idx) {
        segTree[idx] += n;
        idx >>= 1;
    }
}
 
ll getTree(int l, int r)
{
    ll ret = 0;
 
    while (l <= r) {
        if (l & 1) {
            ret += segTree[l];
            l++;
        }
        if (~r & 1) {
            ret += segTree[r];
            r--;
        }
        l >>= 1;
        r >>= 1;
    }
 
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    for (int i = 0; i < N; i++) {
        int n;
        cin >> n;
        arr[i] = n;
        updateTree(N + i, n);
    }
 
    cin >> M;
    int cnt = 0;
 
    for (int i = 0; i < M; i++) {
        int cmd;
        cin >> cmd;
 
        if (cmd == 1) {
            int i, v;
            cin >> i >> v;
            query.push_back({ i,v });
        }
        else {
            int k, i, j;
            cin >> k >> i >> j;
            queryArr.push_back({ k,i,j,cnt++ });
        }
    }
 
    sort(queryArr.begin(), queryArr.end(), cmp());
 
    int cur = 0;
 
    for (auto& next : queryArr) {
        int k = next.k;
        for (int i = cur; i < k; i++) {
            int a = query[i].first;
            int b = query[i].second;
            updateTree(a + N - 1, b - arr[a-1]);
            arr[a - 1] = b;
        }
        cur = k;
 
        ans[next.seq] = getTree(N + next.i - 1, N + next.j - 1);
    }
 
    for (int i = 0; i < cnt; i++) {
        cout << ans[i] << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 14459번 - 소가 길을 건너간 이유 11 (C++)  (0) 2023.08.03
[ 백준 ] 15967번 - 에바쿰 (C++)  (0) 2023.08.02
[ 백준 ] 19940번 - 피자 오븐 (C++)  (0) 2023.07.31
[ 백준 ] 14852번 - 타일 채우기 3 (C++)  (0) 2023.07.30
[ 백준 ] 16954번 - 움직이는 미로 탈출 (C++)  (0) 2023.07.29
반응형

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

 

16934번: 게임 닉네임

첫째 줄에 가입한 유저의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 유저의 닉네임이 가입한 순서대로 한 줄에 하나씩 주어진다. 닉네임은 알파벳 소문자로만 이루어져 있고,

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/417

 

[ 자료구조 ] 트라이(Trie)

1. 트라이(Trie) 트라이(Trie)는 다양한 문자열의 집합을 하나의 트리로 표현하는 자료구조입니다. 2. 트라이(Trie) 동작 원리 먼저 그림을 통해 살펴보도록 하겠습니다. 다음 그림은 문자열 {"jade", "ja

rudalsd.tistory.com

 

1. trie를 구현하고, 단어를 입력받을 때마다 해당 문자열을 print를 통해 새로운 문자가 나오거나 문자열의 끝이 오면 해당 문자열을 출력합니다.

 

2. trie에 해당 문자열을 insert 합니다.

 

[ 소스코드 ]

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
#include<iostream>
 
using namespace std;
 
int N;
 
struct Trie {
    Trie* arr[26];
    int end;
 
    Trie() {
        for (int i = 0; i < 26; i++) {
            arr[i] = NULL;
        }
 
        end = 0;
    }
 
    ~Trie() {
        for (int i = 0; i < 26; i++) {
            if (arr[i]) delete arr[i];
        }
    }
 
    void insert(const char* ch) {
        char temp = *ch - 'a';
        if (!*ch) {
            end++;
            return;
        }
 
        if (arr[temp] == NULL) arr[temp] = new Trie;
        arr[temp]->insert(ch + 1);
    }
 
    void print(const char* ch) {
        char temp = *ch - 'a';
        if (!*ch) {
            if (end) {
                cout << end + 1;
            }
            cout << '\n';
            return;
        }
 
        cout << *ch;
 
        if (arr[temp] == NULL) {
            cout << '\n';
            return;
        }
 
        arr[temp]->print(ch + 1);
    }
};
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    Trie* root = new Trie;
 
    for (int i = 0; i < N; i++) {
        char ch[11];
        cin >> ch;
 
        root->print(ch);
        root->insert(ch);
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 15558번 - 점프 게임 (C++)  (0) 2023.07.27
[ 백준 ] 1245번 - 농장 관리 (C++)  (0) 2023.07.26
[ 백준 ] 7432번 - 디스크 트리 (C++)  (0) 2023.07.24
[ 백준 ] 16929번 - Two Dots (C++)  (0) 2023.07.23
[ 백준 ] 2800번 - 괄호 제거(C++)  (0) 2023.07.22
반응형

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

 

7432번: 디스크 트리

갑자기 맥북이 상근이의 손에서 떨어졌고, 화면이 켜지지 않았다. AS센터에 문의해보니 수리비가 97만원이 나왔고, 상근이는 큰 혼란에 빠졌다. 돈도 중요하지만, 상근이는 그 속에 들어있는 파

www.acmicpc.net

 

 

[ 문제풀이 ]

이 문제를 풀기 전에 다음 글을 먼저 읽고 오시는 것을 추천드립니다.

https://rudalsd.tistory.com/417

 

[ 자료구조 ] 트라이(Trie)

1. 트라이(Trie) 트라이(Trie)는 다양한 문자열의 집합을 하나의 트리로 표현하는 자료구조입니다. 2. 트라이(Trie) 동작 원리 먼저 그림을 통해 살펴보도록 하겠습니다. 다음 그림은 문자열 {"jade", "ja

rudalsd.tistory.com

 

1. trie를 구현하고, 단어를 입력받을 때마다 해당 문자열을 trie에 insert 합니다.

 

2. root부터 오름차순으로 폴더이름을 출력합니다.

 

[ 소스코드 ]

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<vector>
#include<map>
#include<string>
 
using namespace std;
 
int N;
 
struct Trie {
    map<string, Trie *> m;
 
    void insert(vector<string> vect, int level) {
        if ((int)vect.size() > level) {
            if (!m.count(vect[level])) {
                m[vect[level]] = new Trie;
            }
 
            m[vect[level]]->insert(vect, level + 1);
        }
    }
 
    void print(int level) {
        if (m.empty()) return;
        for (auto& next : m) {
            for (int i = 0; i < level; i++) {
                cout << ' ';
            }
            cout << next.first << '\n';
            next.second->print(level + 1);
        }
    }
};
 
vector <string> split(string str) {
    vector <string> ret;
    
    int s = 0;
    int e = 0;
 
    while (1) {
        e = str.find('\\', s);
        if (e == -1) {
            ret.push_back(str.substr(s, str.size() - s));
            break;
        }
        else {
            ret.push_back(str.substr(s, e - s));
            s = e + 1;
        }
    }
 
    return ret;
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    Trie* root = new Trie;
 
    for (int i = 0; i < N; i++) {
        string str;
        cin >> str;
        
        vector<string> vect = split(str);
 
        root->insert(vect, 0);
    }
 
    root->print(0);
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1245번 - 농장 관리 (C++)  (0) 2023.07.26
[ 백준 ] 16934번 - 게임 닉네임 (C++)  (0) 2023.07.25
[ 백준 ] 16929번 - Two Dots (C++)  (0) 2023.07.23
[ 백준 ] 2800번 - 괄호 제거(C++)  (0) 2023.07.22
[ 백준 ] 1990번 - 소수인팰린드롬(C++)  (0) 2023.07.21
반응형

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

 

2800번: 괄호 제거

첫째 줄에 음이 아닌 정수로 이루어진 수식이 주어진다. 이 수식은 괄호가 올바르게 쳐져있다. 숫자, '+', '*', '-', '/', '(', ')'로만 이루어져 있다. 수식의 길이는 최대 200이고, 괄호 쌍은 적어도 1개

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 수식을 입력받아 각 괄호에 번호를 붙입니다.

 

2. 조합을 이용하여 각 괄호들을 제거해주고, set 자료구조에 저장하여 중복을 제거해줍니다.

 

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
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
#include<iostream>
#include<string>
#include<stack>
#include<set>
 
using namespace std;
 
string str;
int arr[200];
set<string> ans;
int visited[11];
int cnt;
 
void dfs(int limit, int level, int num)
{
    if (level == limit) {
        string temp = "";
        for (int i = 0; i < str.size(); i++) {
            if (visited[arr[i]] != 1) {
                temp += str[i];
            }
        }
 
        ans.insert(temp);
        return;
    }
 
    for (int i = num; i <= cnt; i++) {
        visited[i] = 1;
        dfs(limit, level + 1, i + 1);
        visited[i] = 0;
    }
}
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> str;
    stack<int> s;
 
    for (int i = 0; i < str.size(); i++) {
        if (str[i] == '(') {
            cnt++;
            arr[i] = cnt;
            s.push(cnt);
        }
        else if (str[i] == ')') {
            arr[i] = s.top();
            s.pop();
        }
    }
 
    for (int i = 1; i <= cnt; i++) {
        dfs(i, 0, 1);
    }
 
    for (auto& next : ans) {
        cout << next << '\n';
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 7432번 - 디스크 트리 (C++)  (0) 2023.07.24
[ 백준 ] 16929번 - Two Dots (C++)  (0) 2023.07.23
[ 백준 ] 1990번 - 소수인팰린드롬(C++)  (0) 2023.07.21
[ 백준 ] 23326번 - 홍익 투어리스트 (C++)  (0) 2023.07.20
[ 백준 ] 21939번 - 문제 추천 시스템 Version 1 (C++)  (0) 2023.07.19
반응형

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

 

23326번: 홍익 투어리스트

도현이는 홍익 투어리스트가 되어 홍익대학교를 견학하려고 한다. 홍익대학교는 $N$개의 구역이 원형으로 배치된 모습이다. $1$번 구역에서 시계 방향으로 각각 $2$번, ... , $N$번 구역이 존재하고,

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. set 자료구조를 활용하여 명소의 위치를 저장합니다. 

 

2. arr배열을 만들어 해당 좌표가 명소인지 아닌지 체크합니다.

 

3. 1번 명령이 주어지면 명소인지 아닌지 arr배열로 체크하고, 명소라면 arr[ i ]를 0으로 바꾸고, set에서 erase 합니다. 반대의 경우 arr[ i ]를 1로 바꾸고, set에 insert 합니다.

 

4. 2번 명령이 주어지면 x %= N 후 현재 좌표에 x를 더해주고, 이후 좌표가 N보다 크다면 N을 빼줍니다.

 

5. 3번 명령이 주어지면 set이 비어있다면 -1을 출력하고, 그렇지 않다면 현재 좌표를 기준으로 lower_bound를 해주고, 그 값에 현재 좌표를 뺀 값을 출력합니다.

 

6. 5번에서 lower_bound의 결과가 set.end()라면 N - cur + lower_bound(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
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
#include<iostream>
#include<set>
 
using namespace std;
 
int N, Q;
int cur = 1;
int arr[500001];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> Q;
    set<int> s;
 
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
        if (arr[i] == 1) {
            s.insert(i);
        }
    }
 
    for (int i = 0; i < Q; i++) {
        int cmd;
        cin >> cmd;
 
        if (cmd == 1) {
            int i;
            cin >> i;
            if (arr[i] == 0) {
                arr[i] = 1;
                s.insert(i);
            }
            else {
                arr[i] = 0;
                s.erase(i);
            }
        }
        else if (cmd == 2) {
            int x;
            cin >> x;
            if (x > N) {
                x %= N;
            }
            cur += x;
            if (cur > N) {
                cur -= N;
            }
 
        }
        else {
            if (s.empty()) {
                cout << -1 << '\n';;
            }
            else {
                if (s.lower_bound(cur) == s.end()) {
                    cout << N - cur + (*s.lower_bound(0)) << '\n';;
                }
                else {
                    cout << (*s.lower_bound(cur)) - cur << '\n';;
                }
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 2800번 - 괄호 제거(C++)  (0) 2023.07.22
[ 백준 ] 1990번 - 소수인팰린드롬(C++)  (0) 2023.07.21
[ 백준 ] 21939번 - 문제 추천 시스템 Version 1 (C++)  (0) 2023.07.19
[ 백준 ] 15243번 - Tiling (C++)  (0) 2023.07.18
[ 백준 ] 4811번 - 알약 (C++)  (0) 2023.07.17
반응형

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

 

21939번: 문제 추천 시스템 Version 1

tony9402는 최근 깃헙에 코딩테스트 대비 문제를 직접 뽑아서 "문제 번호, 난이도"로 정리해놨다. 깃헙을 이용하여 공부하시는 분들을 위해 새로운 기능을 추가해보려고 한다. 만들려고 하는 명령

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. set 자료구조를 활용하여 문제의 난이도와 번호를 insert 합니다.

 

2. 문제 번호에 따라 난이도를 알 수 있도록 level 배열을 만들어 저장합니다.

 

3. 가장 어려운 난이도의 문제는 set 자료구조의 제일 마지막에 있고, 가장 쉬운 난이도의 문제는 set 자료구조의 제일 앞에 있으므로 명령문에 따라 출력해 줍니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<set>
#include<string>
 
using namespace std;
 
int N, M;
int level[100001];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    set<pair<int,int>> s;
 
    for (int i = 0; i < N; i++) {
        int P, L;
        cin >> P >> L;
 
        level[P] = L;
        s.insert({ L,P });
    }
    
    cin >> M;
 
    for (int i = 0; i < M; i++) {
        string cmd;
        cin >> cmd;
 
        if (cmd == "add") {
            int P, L;
            cin >> P >> L;
 
            level[P] = L;
            s.insert({ L,P });
        }
        else if (cmd == "recommend") {
            int x;
            cin >> x;
 
            if (x == 1) {
                cout << (*s.rbegin()).second << '\n';
            }
            else {
                cout << (*s.begin()).second << '\n';
            }
        }
        else {
            int P;
            cin >> P;
 
            s.erase({ level[P],P });
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1990번 - 소수인팰린드롬(C++)  (0) 2023.07.21
[ 백준 ] 23326번 - 홍익 투어리스트 (C++)  (0) 2023.07.20
[ 백준 ] 15243번 - Tiling (C++)  (0) 2023.07.18
[ 백준 ] 4811번 - 알약 (C++)  (0) 2023.07.17
[ 백준 ] 22856번 - 트리 순회 (C++)  (0) 2023.07.16
반응형

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

 

2295번: 세 수의 합

우리가 x번째 수, y번째 수, z번째 수를 더해서 k번째 수를 만들었다라고 하자. 위의 예제에서 2+3+5=10의 경우는 x, y, z, k가 차례로 1, 2, 3, 4가 되며, 최적해의 경우는 2, 3, 4, 5가 된다. k번째 수가 최

www.acmicpc.net

 

 

[ 문제풀이 ]

 

1. 수들을 입력받아 arr 배열에 저장하고, arr 배열에서 두 수를 뽑아 더한 값을 sum 배열에 저장합니다. 

 

2. arr 배열과 sum 배열을 오름차순으로 정렬합니다.

 

3. 이중 for문을 이용하여 i = N - 1부터 0까지, j는 0부터 N까지 탐색하면서 arr[ i ] - arr[ j ]가 sum 배열에 존재하는지 lower_bound를 활용하여 찾아줍니다.

 

4. sum 배열에 존재한다면 해당 수가 최댓값이므로 arr[ i ]를 출력해 줍니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
 
int N;
int arr[1000];
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N;
 
    vector<int> sum;
 
    for (int i = 0; i < N; i++) {
        cin >> arr[i];
    }
 
    for (int i = 0; i < N; i++) {
        for (int j = i; j < N; j++) {
            sum.push_back(arr[i] + arr[j]);
        }
    }
 
    sort(arr, arr + N);
    sort(sum.begin(), sum.end());
 
    int ans = 0;
 
    for (int i = N - 1; i >= 0; i--) {
        for (int j = 0; j < N; j++) {
            if (*lower_bound(sum.begin(), sum.end(), arr[i] - arr[j]) == arr[i]-arr[j]) {
                cout << arr[i];
                return 0;
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 22856번 - 트리 순회 (C++)  (0) 2023.07.16
[ 백준 ] 7453번 - 합이 0인 네 정수 (C++)  (0) 2023.07.15
[ 백준 ] 1477번 - 휴게소 세우기 (C++)  (0) 2023.07.13
[ 백준 ] 2110번 - 공유기 설치 (C++)  (0) 2023.07.12
[ 백준 ] 10866번 - 덱 (C++)  (0) 2023.07.11
반응형

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

 

10866번: 덱

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 10,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지

www.acmicpc.net

 

 

 

[ 문제풀이 ]

 

1. deque 자료구조를 이용하여 입력받는 수와 동일한 메서드를 이용하여 조건에 맞는 동작을 수행합니다.

 

[ 소스코드 ]

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
#include<iostream>
#include<deque>
#include<string>
 
using namespace std;
 
int N;
deque<int> deq;
 
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;
        int num;
 
        cin >> str;
 
        if (str == "push_front") {
            cin >> num;
            deq.push_front(num);
        }
        else if (str == "push_back") {
            cin >> num;
            deq.push_back(num);
        }
        else if (str == "pop_front") {
            if (!deq.empty()) {
                cout << deq.front() << '\n';
                deq.pop_front();
            }
            else {
                cout << -1 << '\n';
            }
        }
        else if (str == "pop_back") {
            if (!deq.empty()) {
                cout << deq.back() << '\n';
                deq.pop_back();
            }
            else {
                cout << -1 << '\n';
            }
        }
        else if (str == "size") {
            cout << deq.size() << '\n';
        }
        else if (str == "empty") {
            if (!deq.empty()) {
                cout << 0 << '\n';
            }
            else {
                cout << 1 << '\n';
            }
        }
        else if (str == "front") {
            if (!deq.empty()) {
                cout << deq.front() << '\n';
            }
            else {
                cout << -1 << '\n';
            }
        }
        else if (str == "back") {
            if (!deq.empty()) {
                cout << deq.back() << '\n';
            }
            else {
                cout << -1 << '\n';
            }
        }
    }
}
cs
반응형
저작자표시 비영리 변경금지 (새창열림)

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

[ 백준 ] 1477번 - 휴게소 세우기 (C++)  (0) 2023.07.13
[ 백준 ] 2110번 - 공유기 설치 (C++)  (0) 2023.07.12
[ 백준 ] 3151번 - 합이 0 (C++)  (0) 2023.07.10
[ 백준 ] 5430번 - AC (C++)  (0) 2023.07.09
[ 백준 ] 17298번 - 오큰수 (C++)  (0) 2023.07.08

+ Recent posts

티스토리툴바