문제 풀이

 

priority queue를 이용한 다익스트라 알고리즘을 사용하는 문제입니다. 노드의 수가 매우 많기 때문에 메모리를 줄이기 위하여 간선을 저장하였습니다. 단방향 그래프이기 때문에, 출발 노드와 도착 노드 중 출발 노드에만 간선을 저장해 주었습니다. check 배열에는 해당 노드를 방문한 적이 있는지 알아보았고, road 배열에는 최단 거리를 저장해주었습니다. 재방문하게 되는 경우, 최단 거리를 갱신하면서 탐색을 진행합니다.

다익스트라 알고리즘에 대해서 반드시 알아야 풀 수 있었던 문제라, 한 번 알아보시면 도움이 될 것 같습니다!

 

 

코드

 

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
#include <iostream>
#include <vector>
#include <queue>
#include <cstring>
#include <utility>
 
using namespace std;
 
const int MAX = 999999;
 
int ans;
bool check[20001];
int road[20001];
vector <pair<int, int>> g[20001];
 
void bfs(int a) {
 
    memset(check, false, sizeof(check));
    memset(road, MAX, sizeof(road));
    priority_queue <pair<int, int>, vector< pair<int,int> >, greater< pair<int, int> > > q;
    q.emplace(0, a);
    road[a] = 0;
    check[a] = true;
 
    while (!q.empty()) {
        pair<int, int> x;
        x = q.top();
        q.pop();
 
        for (int i = 0; i < g[x.second].size(); i++) {
            if (check[g[x.second][i].first] == false || road[g[x.second][i].first] > x.first + g[x.second][i].second)
            {
                check[g[x.second][i].first] = true;
                road[g[x.second][i].first] = x.first + g[x.second][i].second;
                q.emplace(x.first + g[x.second][i].second, g[x.second][i].first);
            }
        }
    }
}
 
int main() {
 
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int n, e, s;
    cin >> n >> e >> s;
 
    for (int i = 1; i <= e; i++) {
        int u, v, w;
        cin >> u >> v >> w;
        g[u].emplace_back(v, w);
    }
 
    bfs(s);
 
    for (int k = 1; k <= n; k++) {
        
        if (!check[k])
            cout << "INF\n";
        else
            cout << road[k] << '\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/1753

 

1753번: 최단경로

첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. 셋째 줄부터 E개의 줄에 걸쳐 각 간선을 나타내는 세 개의 정수 (u, v, w)가 순서대로 주어진다. 이는 u에서 v로 가는 가중치 w인 간선이 존재한다는 뜻이다. u와 v는 서로 다르며 w는 10 이하의 자연수이다. 서로 다른 두

www.acmicpc.net

 

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

9655번: 돌게임 (백준 온라인 저지, C++)  (0) 2019.05.24
16988번: Baaaaaaaaaduk2 (Easy) (백준 온라인 저지, C++)  (0) 2019.05.07
17070번: 파이프 옮기기 1 (백준 온라인 저지, C++)  (0) 2019.05.01
17143번: 낚시왕 (백준 온라인 저지, C++)  (0) 2019.04.30
3053번: 택시 기하학  (0) 2019.04.27

문제 설명

 

규칙을 찾는다면 정말 허무하게 쉬운 문제입니다. 결론부터 말씀드리자면 홀수일때는 SK, 짝수일 때는 CY를 출력하면 됩니다. 왜 그런지 한 번 살펴보겠습니다.

 

5개일 때, 순서로 가능한 것을 생각해 보겠습니다. 언제나 돌을 1개 또는 3개만 가져갈 수 있기 때문에, 다음과 같은 조합이 가능합니다.

1sk + 1cy + 1sk + 1cy + 1sk

3sk (= 1sk + 1cy + 1sk) + 1cy + 1sk

1sk + 3cy (= 1cy + 1sk + 1cy) + 1sk

1sk + 1cy + 3sk (= 1sk+ 1cy+ 1sk)

즉, 모든 순서는 1 + 1+ 1 + .... 했을 때의 조합과 동일하게 나타낼 수 있고, 순서 또한 똑같습니다.

 

 

코드

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <iostream>
 
using namespace std;
 
int main() {
    
    int n;
    cin >> n;
 
    if (n % 2) cout << "SK\n";
    else cout << "CY\n";
 
    return 0;
}

 

 

제출 결과

 

 

 

문제 출처

 

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

 

9655번: 돌 게임

상근이가 게임을 이기면 SK를, 창영이가 게임을 이기면 CY을 출력한다.

www.acmicpc.net

 

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

1753번: 최단경로 (백준 온라인 저지, C++)  (0) 2019.05.24
16988번: Baaaaaaaaaduk2 (Easy) (백준 온라인 저지, C++)  (0) 2019.05.07
17070번: 파이프 옮기기 1 (백준 온라인 저지, C++)  (0) 2019.05.01
17143번: 낚시왕 (백준 온라인 저지, C++)  (0) 2019.04.30
3053번: 택시 기하학  (0) 2019.04.27

문제 풀이

 

 처음에 문제만 봤을 때는 오래 걸릴 것이라고 생각했는데, 생각보다 조건이 간단해서 금방 풀 수 있는 문제입니다. 브루트 포스 알고리즘을 이용하였습니다.

우선 바둑판에 있는 빈 칸에 2개의 내 바둑돌을 놓을 수 있는 모든 경우의 수를 고려하여 바둑돌을 놓습니다. 그리고 현재 바둑돌을 놓은 판에서 얼마나 바둑돌을 먹을 수 있는지 확인해 주었습니다. (countBlack함수)

바둑판을 탐색하며 검은색 바둑돌이 존재하는 경우, 이 바둑돌이 속한 군집을 check함수로 넘겨줍니다. 여기서 이 그룹이 먹힌다는 것은 이 그룹에 속한 바둑돌의 인접한 지역에 빈 칸이 하나도 없다는 뜻과 동치이므로, 이 조건에 부합한다면 cnt를 증가시켜 주었습니다. 추가 설명을 코드를 참조하시기 바랍니다!

 

 

코드

 

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
#include <iostream>
#include <queue>
#include <cstring>
 
using namespace std;
 
int n, m;
int a[21][21];
bool isVisit[21][21];
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
 
int check(int x, int y) {
 
    int cnt = 0;
 
    bool _get = true;
    queue <pair<int,int>> q;
    q.emplace(x, y);
    isVisit[x][y] = true;
    cnt++;
 
    while (!q.empty()) {
        
        int _x = q.front().first;
        int _y = q.front().second;
        q.pop();
        
        for (int i = 0; i < 4; i++) {
            int nx = _x + dx[i];
            int ny = _y + dy[i];
 
            if (nx < 0 || nx >= n || ny < 0 || ny >= m) continue;
            if (a[nx][ny] == 0) _get = false;
            if (a[nx][ny] == 2 && !isVisit[nx][ny]) {
                isVisit[nx][ny] = true;
                q.emplace(nx, ny);
                cnt++;
            }
        }
     }
 
    if (_get) {
        return cnt;
    }
    else {
        return 0;
    }
}
 
int countBlack() {
 
    int cnt = 0;
    memset(isVisit, false, sizeof(isVisit));
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (a[i][j] == 2 && !isVisit[i][j]) {
                cnt += check(i, j);
            }
        }
    }
 
    return cnt;
}
 
int main() {
 
    int ans = -1;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];
        }
    }
 
    for (int i1 = 0; i1 < n; i1++) {
        for (int j1 = 0; j1 < m; j1++) {
            if (a[i1][j1] == 0) {
                a[i1][j1] = 1;
 
                for (int i2 = i1; i2 < n; i2++) {
                    for (int j2 = 0; j2 < m; j2++) {
                        if ((i1 == i2) && (j1 == j2)) continue;
                        if (a[i2][j2] == 0) {
                            a[i2][j2] = 1;
 
                            int cnt = countBlack();
                            if (ans == -1 || cnt > ans) {
                                ans = cnt;
                            }
 
                            a[i2][j2] = 0;
                        }
                    }
                }
                a[i1][j1] = 0;
            }
        }
    }
 
    cout << ans << '\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/16988

 

16988번: Baaaaaaaaaduk2 (Easy)

서기 2116년, 인간은 더 이상 AI의 상대가 되지 못하게 되었다. 근력, 순발력, 창의력, 사고력, 문제해결능력, 심지어 인간미조차 AI가 인간을 앞선다. AI가 온 지구를 관리하며 이미 인류는 지구의 주인 자리에서 쫓겨난지 오래이다. 그나마 다행인 것은 AI가 인간을 적대적으로 대하지 않고, 도리어 AI가 쌓아올린 눈부신 기술의 발전으로 모든 사람이 무제한적인 재화를 사용할 수 있게 되어 한 세기 전의 사람들이 바라던 돈 많은 백수와 같은 삶을 누릴

www.acmicpc.net

 

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

1753번: 최단경로 (백준 온라인 저지, C++)  (0) 2019.05.24
9655번: 돌게임 (백준 온라인 저지, C++)  (0) 2019.05.24
17070번: 파이프 옮기기 1 (백준 온라인 저지, C++)  (0) 2019.05.01
17143번: 낚시왕 (백준 온라인 저지, C++)  (0) 2019.04.30
3053번: 택시 기하학  (0) 2019.04.27

문제 풀이

 

파이프를 옮기면서 목적지까지 도달할 수 있는 경우의 수를 고르는 문제입니다. 파이프의 좌표에 유의하여 문제를 풀이하였습니다. 우선 파이프의 초기 좌표는 pipe1 = (1,1), pipe2 = (1,2)입니다.

이 때 파이프를 옮기게 되면, pipe1은 항상 pipe2의 위치로 이동하게 됩니다.

pipe2의 경우, 각각 가로로 있는 경우와 세로로 있는 경우, 대각선으로 있는 경우를 고려하여 좌표를 이동시켜 주면 됩니다. 벽이 있는 경우와 지도를 탈출하는 경우에 주의합니다. 이 후 pipe2가 목적지에 도착하였다면, 결과값에 추가시켜 줍니다.

 

 

코드

 

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 <utility>
#include <vector>
 
using namespace std;
 
int n, ans;
int arr[17][17];
int dx[] = {0, 1, 1};
int dy[] = {1, 1, 0};
 
 
void movePipe(pair<int,int> p1, pair<int,int> p2) {
 
    if (p2 == make_pair(n, n)) {
        ans++;
    }
 
    pair<int, int> tmp_p2;
 
    for (int i = 0; i < 3; i++) {
        tmp_p2 = p2;
 
        if ((p1.first == p2.first) && (i == 2)) continue;
        else if ((p1.second == p2.second) && (i == 0)) continue;
 
        tmp_p2.first += dx[i]; tmp_p2.second += dy[i];
        if (tmp_p2.first <= n && tmp_p2.second <= n && tmp_p2.first > 0 && tmp_p2.second > 0 && arr[tmp_p2.first][tmp_p2.second] == 0) {
            if (i == 1) {
                int x1 = p2.first + dx[0], y1 = p2.second + dy[0], x2 = p2.first + dx[2], y2 = p2.second + dy[2];
                if ((x1 <= n && x1 > 0 && y1 <= n && y1 > 0) && (arr[x1][y1] == 1)) continue;
                if ((x2 <= n && x2 > 0 && y2 <= n && y2 > 0) && (arr[x2][y2] == 1)) continue;
                movePipe(p2, tmp_p2);
            }
            else {
                movePipe(p2, tmp_p2);
            }
        }
    }
}
 
int main() {
 
    ans = 0;
    cin >> n;
 
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> arr[i][j];
        }
    }
 
    pair<int, int> init_p1 = { 1,1 }, init_p2 = { 1,2 };
 
    movePipe(init_p1, init_p2);
    cout << ans << '\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/17070

 

17070번: 파이프 옮기기 1

유현이가 새 집으로 이사했다. 새 집의 크기는 N×N의 격자판으로 나타낼 수 있고, 1×1크기의 정사각형 칸으로 나누어져 있다. 각각의 칸은 (r, c)로 나타낼 수 있다. 여기서 r은 행의 번호, c는 열의 번호이고, 행과 열의 번호는 1부터 시작한다. 각각의 칸은 빈 칸이거나 벽이다. 오늘은 집 수리를 위해서 파이프 하나를 옮기려고 한다. 파이프는 아래와 같은 형태이고, 2개의 연속된 칸을 차지하는 크기이다. 파이프는 회전시킬 수 있으며, 아래와 같이

www.acmicpc.net

 

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

9655번: 돌게임 (백준 온라인 저지, C++)  (0) 2019.05.24
16988번: Baaaaaaaaaduk2 (Easy) (백준 온라인 저지, C++)  (0) 2019.05.07
17143번: 낚시왕 (백준 온라인 저지, C++)  (0) 2019.04.30
3053번: 택시 기하학  (0) 2019.04.27
5430번: AC (백준 온라인 저지, C++)  (1) 2019.04.25

문제 풀이

 

알고리즘은 다음과 같습니다. 우선 두 개의 큰 함수를 만들었습니다.

- fishing: 물고기 잡는 함수

- moving: 물고기가 이동하는 함수

 

물고기를 잡는 함수 같은 경우 해당 열에서 맨 위에 위치하는 물고기를 삭제해주면 되는 간단한 함수입니다. 그러나 물고기가 이동하는 함수같은 경우는 약간 까다롭습니다.

우선 물고기가 들어있는 arr과 같은 _tmp 배열을 만들어주고 arr을 비워줍니다. _tmp 배열을 탐색하면서 물고기가 있다면 moveThisShark 함수를 이용하여 이동시켜 주었습니다. moveThisShark 함수에서는 물고기가 이동했을 경우 어디로 이동하는지에 대한 좌표를 리턴해 주었습니다.

이 때, 속력이 매우 큰 경우를 고려하여 한번 왔다갔다 하고 제자리로 돌아온 경우를 배제하기 위해, 다음과 같은 식을 적용해 주었습니다.

이 후, 반환된 좌표값의 arr을 참조하였을 때, 이미 물고기가 있다면 이는 이동을 마친 물고기가 있는 것으로 따라서 물고기의 크기를 비교하여 더 큰 물고기를 배열에 넣어주었습니다. 물고기가 없다면 바로 배열에 넣어줍니다. 중복을 방지하기 위해 이동을 마친다면 _tmp의 값을 삭제하여 줍니다. 자세한 풀이는 코드를 첨부하도록 하겠습니다.

 

 

코드

 

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
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
#include <string>
 
using namespace std;
 
struct shark {
    int s; //속력
    int d; //이동 방향
    int z; //크기
};
 
int R, C, M;
shark arr[101][101];
shark _tmp[101][101];
int dr[] = { -1, 1, 0, 0 };
int dc[] = { 0, 0, 1, -1 };
 
void _reset(string s, int r, int c) {
    if (s == "arr") {
        arr[r][c].s = 0; arr[r][c].d = 0; arr[r][c].z = 0;
    }
    else {
        _tmp[r][c].s = 0; _tmp[r][c].d = 0; _tmp[r][c].z = 0;
    }
}
 
void _set(string s, int r, int c, int ss, int dd, int zz) {
    if (s == "arr") {
        arr[r][c].s = ss; arr[r][c].d = dd; arr[r][c].z = zz;
    }
    else {
        _tmp[r][c].s = ss; _tmp[r][c].d = dd; _tmp[r][c].z = zz;
    }
}
 
int fishing(int a) {
 
    for (int i = 1; i <= R; i++) {
        if (arr[i][a].z > 0) {
            int tmp = arr[i][a].z;
            _reset("arr", i, a);
            return tmp;
        }
    }
    return 0;
}
 
pair<int,int> moveThisShark(int r, int c) {
    
    int tmp_r = r;
    int tmp_c = c;
 
    shark sh;
    sh.s = _tmp[r][c].s; sh.d = _tmp[r][c].d; sh.z = _tmp[r][c].z;
 
    if (sh.d == 0 || sh.d == 1) sh.s -= (sh.s / (R * 2 - 2)) * (R * 2 - 2);
    else sh.s -= (sh.s / (C * 2 - 2)) *(C * 2 - 2);
 
    for (int i = 0; i < sh.s; i++) {
        int nr = r + dr[sh.d];
        int nc = c + dc[sh.d];
        if (nr < 1 || nr > R || nc < 1 || nc > C) {
            if (sh.d == 0) sh.d = 1;
            else if (sh.d == 1) sh.d = 0;
            else if (sh.d == 2) sh.d = 3;
            else sh.d = 2;
            r += dr[sh.d];
            c += dc[sh.d];
        }
        else {
            r = nr;
            c = nc;
        }
    }
 
    _tmp[tmp_r][tmp_c].d = sh.d;
 
    return make_pair(r, c);
}
 
void moving() {
 
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            if (arr[i][j].z > 0) {
                _set("_tmp", i, j, arr[i][j].s, arr[i][j].d, arr[i][j].z);
                _reset("arr", i, j);
            }
        }
    }
 
    for (int i = 1; i <= R; i++) {
        for (int j = 1; j <= C; j++) {
            if (_tmp[i][j].z > 0) {
 
                pair<int, int> x;
                x = moveThisShark(i, j);
 
                if (arr[x.first][x.second].z > 0) {
                    if (arr[x.first][x.second].z < _tmp[i][j].z) {
                        _set("arr", x.first, x.second, _tmp[i][j].s, _tmp[i][j].d, _tmp[i][j].z);
                    }
                }
                else {
                    _set("arr", x.first, x.second, _tmp[i][j].s, _tmp[i][j].d, _tmp[i][j].z);
                }
                _reset("_tmp", i, j);
            }
        }
    }
}
 
int main() {
 
    int ans = 0;
    cin >> R >> C >> M;
 
    for (int i = 0; i < M; i++) {
        int r, c;
        cin >> r >> c;
        cin >> arr[r][c].s >> arr[r][c].d >> arr[r][c].z;
        arr[r][c].d -= 1;    
    }
 
    for (int i = 1; i <= C; i++) {
        ans += fishing(i);
        moving();
        ans += 0;
    }
 
    cout << ans;
 
    return 0;
}
http://colorscripter.com/info#e" target="_blank" style="color:#e5e5e5; text-decoration:none">Colored by Color Scripter

 

 

제출 결과

 

 

 

문제 출처

 

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

 

17143번: 낚시왕

낚시왕이 상어 낚시를 하는 곳은 크기가 R×C인 격자판으로 나타낼 수 있다. 격자판의 각 칸은 (r, c)로 나타낼 수 있다. r은 행, c는 열이고, (R, C)는 아래 그림에서 가장 오른쪽 아래에 있는 칸이다. 칸에는 상어가 최대 한 마리 들어있을 수 있다. 상어는 크기와 속도를 가지고 있다. 낚시왕은 가장 처음에 1번 열의 한 칸 왼쪽에 있다. 다음은 1초 동안 일어나는 일이며, 아래 적힌 순서대로 일어난다. 낚시왕은 가장 오른쪽 열의 오른쪽 칸에

www.acmicpc.net

 

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

16988번: Baaaaaaaaaduk2 (Easy) (백준 온라인 저지, C++)  (0) 2019.05.07
17070번: 파이프 옮기기 1 (백준 온라인 저지, C++)  (0) 2019.05.01
3053번: 택시 기하학  (0) 2019.04.27
5430번: AC (백준 온라인 저지, C++)  (1) 2019.04.25
1021번: 회전하는 큐 (백준 온라인 저지, C++)  (0) 2019.04.25

최대한 짧게 만들어 본 코드입니다. 문제 자체는 어려운 문제가 아니라 풀이는 생략하도록 하겠습니다!

 

 

문제 출처

 

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

 

3053번: 택시 기하학

문제 19세기 독일 수학자 헤르만 민코프스키는 비유클리드 기하학 중 택시 기하학을 고안했다. 택시 기하학에서 두 점 T1(x1,y1), T2(x2,y2) 사이의 거리는 다음과 같이 구할 수 있다. D(T1,T2) = |x1-x2| + |y1-y2| 두 점 사이의 거리를 제외한 나머지 정의는 유클리드 기하학에서의 정의와 같다. 따라서 택시 기하학에서 원의 정의는 유클리드 기하학에서 원의 정의와 같다. 원: 평면 상의 어떤 점에서 거리가 일정한 점들의 집합

www.acmicpc.net

 

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

17070번: 파이프 옮기기 1 (백준 온라인 저지, C++)  (0) 2019.05.01
17143번: 낚시왕 (백준 온라인 저지, C++)  (0) 2019.04.30
5430번: AC (백준 온라인 저지, C++)  (1) 2019.04.25
1021번: 회전하는 큐 (백준 온라인 저지, C++)  (0) 2019.04.25
1916번: 최소비용 구하기  (0) 2019.04.21

문제 풀이

 

순서의 뒤집기를 말 그대로 뒤집지 않고, reverse라는 bool type의 변수를 두어 뒤집어진 경우에는 뒤에서 삭제, 뒤에서 출력을 해주면 문제 풀이가 가능합니다. 그 외에도 strtok라는 함수를 써서 입력을 받으면 한결 간편하게 입력받기가 가능합니다.

 

 

코드

 

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
#include <iostream>
#include <string>
#include <cstring>
#include <deque>
 
using namespace std;
 
deque <int> dq;
char arr[400005];
 
int main() {
 
    int t;
    cin >> t;
 
    while (t--) {
        
        memset(arr, '\0', sizeof(arr));
        bool e = false;
        bool r = false;
        dq.clear();
        string p; int n;
        cin >> p >> n >> arr;
 
        char * tmp = strtok(arr, "[,]");
        while (tmp) {
            dq.push_back(stoi(tmp));
            tmp = strtok(NULL, "[,]");
        }
 
        for (int i = 0; i < p.size(); i++) {
            if (p[i] == 'R') {
                if (r) r = false;
                else r = true;
            }
            if (p[i] == 'D') {
                if (dq.empty()) {
                    e = true;
                    break;
                }
                if (r) dq.pop_back();
                else dq.pop_front();
            }
        }
 
        if (e) cout << "error\n";
        else {
            cout << '[';
            for (int i = 0; i < dq.size(); i++) {
                if (r) cout << dq[dq.size() - 1 - i];
                else cout << dq[i];
 
                if (i == dq.size() - 1) continue;
                else cout << ',';
            }
            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/5430

 

5430번: AC

문제 선영이는 주말에 할 일이 없어서 새로운 언어 AC를 만들었다. AC는 정수 배열에 연산을 하기 위해 만든 언어이다. 이 언어에는 두 가지 함수 R(뒤집기)과 D(버리기)가 있다. 함수 R은 배열에 있는 숫자의 순서를 뒤집는 함수이고, D는 첫 번째 숫자를 버리는 함수이다. 배열이 비어있는데 D를 사용한 경우에는 에러가 발생한다. 함수는 조합해서 한 번에 사용할 수 있다. 예를 들어, "AB"는 A를 수행한 다음에 바로 이어서 B를 수행하는 함수이다.

www.acmicpc.net

 

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

17143번: 낚시왕 (백준 온라인 저지, C++)  (0) 2019.04.30
3053번: 택시 기하학  (0) 2019.04.27
1021번: 회전하는 큐 (백준 온라인 저지, C++)  (0) 2019.04.25
1916번: 최소비용 구하기  (0) 2019.04.21
10866번: 덱 (백준 온라인 저지, C++)  (0) 2019.04.20

문제 풀이

 

빼고자 하는 숫자의 위치를 파악한 후, 2번 연산과 3번 연산 중 더 적게 수행할 수 있는 연산을 수행하여, 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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <iostream>
#include <deque>
 
using namespace std;
 
int n, m, cnt;
deque <int> dq;
 
void _op2() {
 
    int a = dq.front();
    
    dq.pop_front();
    dq.push_back(a);
    cnt++;
 
    return;
}
 
void _op3() {
 
    int a = dq.back();
 
    dq.pop_back();
    dq.push_front(a);
    cnt++;
 
    return;
}
 
int main() {
 
    cnt = 0;
    cin >> n >> m;
 
    for(int i = 1; i <= n; i++) {
        dq.push_back(i);
    }
 
    while (m--) {
        
        int t = 0;
        int now; cin >> now;
 
        for (int i = 0; i < dq.size(); i++) {
            if (dq[i] == now) {
                t = i;
                break;
            }
        }
 
        if (t < dq.size() - t) {
            for (int i = 0; i < t; i++) {
                _op2();
            }
        }
        else {
            for (int i = 0; i < dq.size() - t; i++) {
                _op3();
            }
        }
        dq.pop_front();
    }
    cout << cnt << '\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/1021

 

1021번: 회전하는 큐

첫째 줄에 큐의 크기 N과 뽑아내려고 하는 수의 개수 M이 주어진다. N은 50보다 작거나 같은 자연수이고, M은 N보다 작거나 같은 자연수이다. 둘째 줄에는 지민이가 뽑아내려고 하는 수의 위치가 순서대로 주어진다. 위치는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

www.acmicpc.net

 

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

3053번: 택시 기하학  (0) 2019.04.27
5430번: AC (백준 온라인 저지, C++)  (1) 2019.04.25
1916번: 최소비용 구하기  (0) 2019.04.21
10866번: 덱 (백준 온라인 저지, C++)  (0) 2019.04.20
2902번: KMP는 왜 KMP일까? (백준 온라인 저지, C++)  (0) 2019.04.20

+ Recent posts

티스토리툴바