문제 풀이

 

 최소 비용일때마다 fee 배열에 저장된 최소비용을 갱신해줍니다. fee[finish]에 start node에서 finish node로 가는 최소 비용이 저장됩니다.

 

 

코드

 

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
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
 
using namespace std;
 
int n, m, finish;
int fee[1001];
vector <pair<int,int>> graph[1001];
 
int go(int start) {
 
    queue<int> q;
    q.push(start);
    fee[start] = 0;
 
    while (!q.empty()) {
        int x = q.front();
        q.pop();
 
        for (int i = 0; i < graph[x].size(); i++) {
            int nx, cost;
            nx = graph[x][i].first;
            cost = graph[x][i].second;
            if (fee[nx] == -1 || fee[x] + cost < fee[nx]) {
                fee[nx] = fee[x] + cost;
                if (nx != finish) {
                    q.push(nx);
                }
            }
        }
    }
    return fee[finish];
}
 
int main() {
 
    memset(fee, -1, sizeof(fee));
    cin >> n >> m;
 
    while (m--) {
        int b, e, c; cin >> b >> e >> c;
        graph[b].push_back(make_pair(e, c));
    }
 
    int start; cin >> start >> finish;
 
    cout << go(start) << '\n';
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5; text-decoration:none">Colored by Color Scripter

 

 

제출 결과

 

 

 

문제 출처

 

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

 

1916번: 최소비용 구하기

첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 주어진다. 그리고 그 다음에는 도착지의 도시 번호가 주어지고 또 그 버스 비용이 주어진다. 버스 비용은 0보다 크거나 같고, 100,000보다 작은 정수이다. 그리고 M+3째 줄에는 우리가 구하고자 하는 구간

www.acmicpc.net

 

'algorithm codes > baekjoon online judge' 카테고리의 다른 글

5430번: AC (백준 온라인 저지, C++)  (1) 2019.04.25
1021번: 회전하는 큐 (백준 온라인 저지, C++)  (0) 2019.04.25
10866번: 덱 (백준 온라인 저지, C++)  (0) 2019.04.20
2902번: KMP는 왜 KMP일까? (백준 온라인 저지, C++)  (0) 2019.04.20
4307번: 개미  (0) 2019.04.18

코드

 

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
#include <iostream>
#include <string>
 
using namespace std;
 
int d[20001];
 
int main() {
 
    int n, x; cin >> n;
    int b = 10000, e = 10000;
 
    while(n--) 
    {
        string s; cin >> s;
 
        if (s == "push_front")
        {
            cin >> x;
            d[b] = x;
            b--;
        }
        else if (s == "push_back")
        {
            cin >> x;
            e++;
            d[e] = x;
        }
        else if (s == "pop_front")
        {
            if (e - b == 0) {
                cout << "-1\n";
            }
            else {
                b++;
                cout << d[b] << '\n';
            }
        }
        else if (s == "pop_back")
        {
            if (e - b == 0) {
                cout << "-1\n";
            }
            else {
                cout << d[e] << '\n';
                e--;
            }
        }
        else if (s == "size")
        {
            cout << e - b << '\n';
        }
        else if (s == "empty")
        {
            if (e - b == 0) {
                cout << "1\n";
            }
            else {
                cout << "0\n";
            }
        }
        else if (s == "front")
        {
            if (e - b == 0) {
                cout << "-1\n";
            }
            else {
                cout << d[b + 1] << '\n';
            }
        }
        else if (s == "back")
        {
            if (e - b == 0) {
                cout << "-1\n";
            }
            else {
                cout << d[e] << '\n';
            }
        }
    }
 
    return 0;
}

 

 

채점 결과

 

 

 

문제 출처

 

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

 

10866번: 덱

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

www.acmicpc.net

 

'algorithm codes > baekjoon online judge' 카테고리의 다른 글

1021번: 회전하는 큐 (백준 온라인 저지, C++)  (0) 2019.04.25
1916번: 최소비용 구하기  (0) 2019.04.21
2902번: KMP는 왜 KMP일까? (백준 온라인 저지, C++)  (0) 2019.04.20
4307번: 개미  (0) 2019.04.18
1874번: 스택 수열  (0) 2019.04.16

문제 풀이

 

아스키 코드를 활용하여 대문자인 경우 출력해주었습니다.

 

 

코드

 

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 <string>
 
using namespace std;
 
int main() {
 
    string s;
    cin >> s;
 
    for (int i = 0; i < s.size(); i++) {
        
        int a = s[i];
 
        if (i == 0) {
            cout << s[i];
        }
        else if (a >= 65 && a <= 90) {
            cout << s[i];
        }
    }
 
    cout << '\n';
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5; text-decoration:none">Colored by Color Scripter

 

 

제출 결과

 

 

 

문제 출처

 

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

 

2902번: KMP는 왜 KMP일까?

문제 KMP 알고리즘이 KMP인 이유는 이를 만든 사람의 성이 Knuth, Morris, Prett이기 때문이다. 이렇게 알고리즘에는 발견한 사람의 성을 따서 이름을 붙이는 경우가 많다. 또 다른 예로, 유명한 비대칭 암호화 알고리즘 RSA는 이를 만든 사람의 이름이 Rivest, Shamir, Adleman이다. 사람들은 이렇게 사람 성이 들어간 알고리즘을 두 가지 형태로 부른다. 첫 번째는 성을 모두 쓰고, 이를 하이픈(-)으로 이어 붙인 것이다. 예

www.acmicpc.net

 

'algorithm codes > baekjoon online judge' 카테고리의 다른 글

1916번: 최소비용 구하기  (0) 2019.04.21
10866번: 덱 (백준 온라인 저지, C++)  (0) 2019.04.20
4307번: 개미  (0) 2019.04.18
1874번: 스택 수열  (0) 2019.04.16
10828번: 스택 (백준 온라인 저지, C++)  (0) 2019.04.15

문제 풀이

 

 개미가 부딪혔을 경우, 개미의 방향이 반대가 된다는 조건에 의해 개미를 각각으로 생각하여 풀이할 수도 있습니다. 그러나 1차원의 경우 부딪혀서 반대가 되어도 결국 교차한 것과 같게 되므로 단순히 개미의 진행방향만 고려하여 문제를 풀이하면 쉽게 문제를 풀 수 있습니다.

 

 

코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
    int t;
    cin >> t;
    while (t--) {
        int l, n, x;
        cin >> l >> n;
        int mn = -1, mx = -1;
        while (n--) {    
            cin >> x;
            mn = max(mn, min(x, l-x));
            mx = max(mx, max(x, l-x));     
        }
        cout << mn << ' ' << mx << '\n';
    }
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5; text-decoration:none">Colored by Color Scripter

 

 

제출 결과

 

 

 

문제 출처

 

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

 

4307번: 개미

문제 개미 여러 마리가 길이가 lcm인 막대 위에 있다. 각 개미의 이동 속도는 모두 일정하며, 1cm/s이다. 개미가 막대의 마지막까지 걸어간다면, 개미는 그 즉시 떨어지게 된다. 또, 두 개미가 만나게 된다면, 방향을 반대로 바꾸어 걸어가게 된다. 가장 처음에 막대 상에서 개미의 위치를 알고 있다. 하지만, 개미가 어느 방향으로 움직이는 지는 알 수가 없다. 이때, 모든 개미가 땅으로 떨어질 때까지 가능한 시간 중 가장 빠른 시간과 느린 시간을 구하는

www.acmicpc.net

 

'algorithm codes > baekjoon online judge' 카테고리의 다른 글

10866번: 덱 (백준 온라인 저지, C++)  (0) 2019.04.20
2902번: KMP는 왜 KMP일까? (백준 온라인 저지, C++)  (0) 2019.04.20
1874번: 스택 수열  (0) 2019.04.16
10828번: 스택 (백준 온라인 저지, C++)  (0) 2019.04.15
4948번: 베르트랑 공준  (0) 2019.04.15

문제 해설

 

 스택을 이용해서 주어진 수열을 출력할 수 있는가에 대한 문제입니다. 스택의 경우 LIFO 구조를 가지고 있으므로, 순서에 유의하여야 합니다. 예시로 주어진 "5->3->4" 의 경우, 5를 출력하고 나면 스택에 남은 숫자는 {3, 4}입니다. 이 때, 나올 수 있는 수는 더 늦게 스택에 push된 4이므로 4보다 3을 먼저 출력할 수 없습니다. 따라서 NO를 출력해야 합니다. 이후의 설명은 코드를 첨부하도록 하겠습니다.

 

 

코드

 

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
#include <iostream>
#include <stack>
#include <vector>
#include <cstring>
 
using namespace std;
 
bool isUse[100001];
 
int main() {
 
    int n, now = 0;
    cin >> n;
 
    memset(isUse, false, sizeof(isUse));
 
    //stack을 만든다.
    stack <int> s;
    vector <char> output;
    bool isTrue = true;
 
    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
 
        if (now < x) { // 만약 현재 위치보다 출력해야 하는 값이 크다면, 스택에 넣어준다.
            for (int i = now + 1; i <= x; i++) {
                if (!isUse[i]) {
                    s.push(i);
                    output.push_back('+');
                    isUse[i] = true;
                }
            }
            now = s.top();
        }
 
        if (now == x) {
            s.pop();
            output.push_back('-');
            if (!s.empty()) {
                now = s.top();
            }
            else {
                now = 0;
            }
        }
        else {
            isTrue = false;
            break;
        }
    }
 
    if (isTrue) {
        for (auto i : output) {
            cout << i << '\n';
        }
    }
    else {
        cout << "NO\n";
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5; text-decoration:none">Colored by Color Scripter

 

 

제출 결과

 

 

 

문제 출처

 

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

 

1874번: 스택 수열

1부터 n까지에 수에 대해 차례로 [push, push, push, push, pop, pop, push, push, pop, push, push, pop, pop, pop, pop, pop] 연산을 수행하면 수열 [4, 3, 6, 8, 7, 5, 2, 1]을 얻을 수 있다.

www.acmicpc.net

 

'algorithm codes > baekjoon online judge' 카테고리의 다른 글

2902번: KMP는 왜 KMP일까? (백준 온라인 저지, C++)  (0) 2019.04.20
4307번: 개미  (0) 2019.04.18
10828번: 스택 (백준 온라인 저지, C++)  (0) 2019.04.15
4948번: 베르트랑 공준  (0) 2019.04.15
1929번: 소수 구하기  (0) 2019.04.15

코드

 

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
#include <iostream>
#include <string>
 
using namespace std;
 
int stck[10001];
 
int main() {
 
    string s;
    int n, x;
    int t = -1;    //top index
    cin >> n;
 
    while (n--) {
        cin >> s;
 
        if (s == "push") {
            cin >> x;
            t++;
            stck[t] = x;
        }
        else if (s == "pop") {
            if (t == -1) {
                cout << -1 << '\n';
            }
            else {
                cout << stck[t] << '\n';
                t--;
            }
        }
        else if (s == "size") {
            cout << t + 1 << '\n';
        }
        else if (s == "empty") {
            if (t == -1) {
                cout << 1 << '\n';
            }
            else {
                cout << 0 << '\n';
            }
        }
        else if (s == "top") {
            if (t == -1) {
                cout << -1 << '\n';
            }
            else {
                cout << stck[t] << '\n';
            }
        }
    }
 
    return 0;
}

 

 

제출 결과

 

 

 

문제 출처

 

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

 

10828번: 스택

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

www.acmicpc.net

 

'algorithm codes > baekjoon online judge' 카테고리의 다른 글

4307번: 개미  (0) 2019.04.18
1874번: 스택 수열  (0) 2019.04.16
4948번: 베르트랑 공준  (0) 2019.04.15
1929번: 소수 구하기  (0) 2019.04.15
2581번: 소수 (백준 온라인 저지, C++)  (0) 2019.04.15

코드

 

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 <cstring>
 
using namespace std;
 
bool number[1000001];
 
int main() {
 
    memset(number, true, sizeof(number));
 
    number[1] = false;
 
    for (int i = 2; i <= 2 * 123456; i++) {
        if (number[i]) {
            for (int j = 2; j <= 2 * 123456 / i; j++) {
                number[j * i] = false;
            }
        }
    }
 
    while (1) {
 
        int n, num = 0;
        cin >> n;
 
        if (n == 0) break;
 
        for (int i = n + 1; i <= 2 * n; i++) {
            if (number[i]) {
                num++;
            }
        }
 
        cout << num << '\n';
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5; text-decoration:none">Colored by Color Scripter

 

 

제출 결과

 

 

 

문제 출처

 

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

 

4948번: 베르트랑 공준

문제 베르트랑 공준은 임의의 자연수 n에 대하여, n보다 크고, 2n보다 작거나 같은 소수는 적어도 하나 존재한다는 내용을 담고 있다. 이 명제는 조제프 베르트랑이 1845년에 추측했고, 파프누티 체비쇼프가 1850년에 증명했다. 예를 들어, 10보다 크고, 20보다 작거나 같은 소수는 4개가 있다. (11, 13, 17, 19) 또, 14보다 크고, 28보다 작거나 같은 소수는 3개가 있다. (17,19, 23) n이 주어졌을 때, n보다 크고, 2n보

www.acmicpc.net

 

'algorithm codes > baekjoon online judge' 카테고리의 다른 글

1874번: 스택 수열  (0) 2019.04.16
10828번: 스택 (백준 온라인 저지, C++)  (0) 2019.04.15
1929번: 소수 구하기  (0) 2019.04.15
2581번: 소수 (백준 온라인 저지, C++)  (0) 2019.04.15
17135번: 캐슬 디펜스 (백준 온라인 저지, C++)  (0) 2019.04.08

문제 풀이

 

 에라토스테네스의 체를 활용하여 소수를 구하였습니다.

 

 

코드

 

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
#include <iostream>
#include <cstring>
 
using namespace std;
 
bool number[1000001];
 
int main() {
 
    int m, n;
 
    cin >> m >> n;
 
    memset(number, true, sizeof(number));
 
    number[1] = false;
 
    for (int i = 2; i <= n; i++) {
        if (number[i]) {
            for (int j = 2; j <= n / i; j++) {
                number[j * i] = false;
            }
        }
    }
 
    for (int i = m; i <= n; i++) {
        if (number[i]) {
            cout << i << ' ';
        }
    }
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5; text-decoration:none">Colored by Color Scripter

 

 

제출 결과

 

 

 

문제 출처

 

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

 

1929번: 소수 구하기

첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000)

www.acmicpc.net

 

'algorithm codes > baekjoon online judge' 카테고리의 다른 글

10828번: 스택 (백준 온라인 저지, C++)  (0) 2019.04.15
4948번: 베르트랑 공준  (0) 2019.04.15
2581번: 소수 (백준 온라인 저지, C++)  (0) 2019.04.15
17135번: 캐슬 디펜스 (백준 온라인 저지, C++)  (0) 2019.04.08
3184번: 양 (백준 온라인 저지, C++)  (0) 2019.04.05

+ Recent posts

티스토리툴바