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

 

10430번: 나머지

첫째 줄에 A, B, C가 순서대로 주어진다. (2 ≤ A, B, C ≤ 10000)

www.acmicpc.net

 

문제에서 요구하는 그대로 따라가시면 됩니다.

 

1
2
3
4
5
6
7
8
9
10
11
12
#include <iostream>
using namespace std;
 
int main() {
    int a, b, c;
    cin >> a >> b >> c;
    cout << (a + b) % c << endl;
    cout << (a % c + b % c) % c << endl;
    cout << (a * b) % c << endl;
    cout << (a % c * b % c) % c;
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

BOJ 1934번 최소공배수  (0) 2020.01.12
BOJ 2609번 - 유클리드 호제법  (0) 2020.01.12
BOJ 1168번 요세푸스 문제2  (0) 2020.01.12
BOJ 1158번 요세푸스 문제  (0) 2020.01.12
BOJ 1406번 에디터  (0) 2020.01.12

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

 

1168번: 요세푸스 문제 2

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 100,000)

www.acmicpc.net

 

링크드리스트를 사용했던 요세푸스 문제1은 한칸씩 이동해가며 모든범위를 계속 돌았기 때문에 느릴 수 밖에 없습니다.

그래서 범위가 커진 문제2는 시간초과를 줄이기 위해 모드계산을 통하여 문제를 해결하였습니다.

erase 를 이용하게 되면 분명 링크드리스트보다 삭제시 계산작업이 많아지기 때문에 효율이 떨어질 수 있지만

대신 모드계산을 한번에 할 수 있다는 장점이 있어 갈수록 계산이 빨라지므로 시간내에 해결할 수 있습니다.

 

더보기
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
#include <iostream>
#include <vector>
using namespace std;
 
int main(void)
{
    ios::sync_with_stdio(0);
    
    int N, M;
    cin >> N >> M;
    vector<int> v;
    for (int i = 1; i <= N; i++)
        v.push_back(i);
 
    int cur = M - 1;
 
    int copyN = N;
 
    cout << "<";
 
    for (int i = 0; i < N; i++) {
        cout << v[cur];
        if (i == N - 1)
            cout << ">\n";
        else
            cout << ", ";
 
        v.erase(v.begin() + cur);
        cur += (M - 1);
 
        if (--copyN > 0)
            cur %= copyN;
    }
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

BOJ 2609번 - 유클리드 호제법  (0) 2020.01.12
BOJ 10430번 나머지  (0) 2020.01.12
BOJ 1158번 요세푸스 문제  (0) 2020.01.12
BOJ 1406번 에디터  (0) 2020.01.12
BOJ 11656번 접미사 배열  (0) 2020.01.12

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

 

1158번: 요세푸스 문제

첫째 줄에 N과 K가 빈 칸을 사이에 두고 순서대로 주어진다. (1 ≤ K ≤ N ≤ 5,000)

www.acmicpc.net

 

링크드리스트를 이용,

K는 몆번째를 의미하기 때문에 자신을 포함하려면 K-1 번만 카운트 해가는 식으로 문제를 해결해주면 된다.

 

더보기
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
#include <iostream>
#include <list>
#include <queue>
using namespace std;
 
queue<int> q;
list<int> l;
list<int>::iterator it, finish;
 
int main() {
    int N, K;
    cin >> N >> K;
    for (int i = 1; i <= N; i++) l.push_back(i);
    it = l.begin();
    /*
    1 2 3 4 5 6 7
    1 2 4 5 6 7
    1 2 4 5 7
    1 4 5 7
    1 4 5
    1 4
    4
    */
 
    while (!l.empty()) {
        int cnt = 1;
        while (cnt < K) {
            if (it == --l.end()) it = l.begin();
            else it++;
            cnt++;
        }
        q.push(*it);
        if (it == --l.end()) {
            it = l.erase(it);
            it = l.begin();
        }
        else it = l.erase(it);
    }
 
    cout << "<" << q.front();
    q.pop();
    while (!q.empty()) {
        cout << ", " << q.front();
        q.pop();
    }
    cout << '>';
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

BOJ 10430번 나머지  (0) 2020.01.12
BOJ 1168번 요세푸스 문제2  (0) 2020.01.12
BOJ 1406번 에디터  (0) 2020.01.12
BOJ 11656번 접미사 배열  (0) 2020.01.12
BOJ 11655번 ROT13  (0) 2020.01.12

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

 

1406번: 에디터

문제 한 줄로 된 간단한 에디터를 구현하려고 한다. 이 편집기는 영어 소문자만을 기록할 수 있는 편집기로, 최대 600,000글자까지 입력할 수 있다. 이 편집기에는 '커서'라는 것이 있는데, 커서는 문장의 맨 앞(첫 번째 문자의 왼쪽), 문장의 맨 뒤(마지막 문자의 오른쪽), 또는 문장 중간 임의의 곳(모든 연속된 두 문자 사이)에 위치할 수 있다. 즉 길이가 L인 문자열이 현재 편집기에 입력되어 있으면, 커서가 위치할 수 있는 곳은 L+1가지 경우가

www.acmicpc.net

 

스택, 링크드리스트 둘중 하나를 이용하면 해결할 수 있다.

예전에 스택으로 해결한 적이 있어 오늘 다시 풀어볼때 링크드리스트로 구현해보았다.

자료구조 복습겸 처음에는 직접 리스트를 구현하였는데

잦은 실수가 있어 상당히 많이 틀렸다.

리스트 구현을 복습하고 난 후 STL 을 이용하여 깔끔하게 구현하였다.

 

더보기
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
#include <list>
#include <iostream>
#include <string>
using namespace std;
 
list<char> l;
 
int main() {
    string str;
    cin >> str;
    for (int i = 0; i < str.size(); i++) {
        l.push_back(str[i]);
    }
 
    char ch;
    list<char>::iterator pointer;
    int M; cin >> M;
    pointer = l.end();
    while (M--) {
        cin >> ch;
        if (ch == 'L') {
            if (pointer != l.begin()) pointer--;
        }
        else if (ch == 'D') {
            if (pointer != l.end()) pointer++;
        }
        else if (ch == 'B') {
            if (pointer != l.begin()) {
                pointer--;
                pointer = l.erase(pointer);
            }
        }
        else if (ch == 'P') {
            cin >> ch;
            l.insert(pointer, ch);
        }
    }
 
    list<char>::iterator start;
    for (start = l.begin(); start != l.end(); start++) {
        cout << *start;
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5text-decoration:none">Colored by Color Scripter

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

BOJ 1168번 요세푸스 문제2  (0) 2020.01.12
BOJ 1158번 요세푸스 문제  (0) 2020.01.12
BOJ 11656번 접미사 배열  (0) 2020.01.12
BOJ 11655번 ROT13  (0) 2020.01.12
BOJ 10820번 문자열 분석  (0) 2020.01.12

+ Recent posts

티스토리툴바