algorithm/Implementation
boj 20055 컨베이어 벨트 위의 로봇
와이에쓰
2021. 2. 23. 21:30
20055번: 컨베이어 벨트 위의 로봇
길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부
www.acmicpc.net
1번 칸 - 로봇이 올라가는 위치
N번 칸 - 로봇이 내려가는 위치
로봇은 무조건 1번 칸에만 놓아야하며, 컨베이어 벨트에서의 이동은 가능합니다.
컨베이어 벨트를 이용하여 로봇들을 옮기는 과정은
1. 벨트가 한 칸 회전합니다.
2. 벨트에 로봇이 올라가있으면 회전하는 방향으로 한 칸 이동할 수 있으면 이동합니다.
3. 로봇이 이동한 칸의 내구도가 1 감소합니다.
4. 올라가는 위치(1번 칸)에 로봇이 없고, 내구도가 0이 아니면 로봇을 하나 올립니다.
5. 로봇이 올라가면서 올라가는 위치(1번 칸)의 내구도가 1 감소합니다.
6. 내구도가 0인 칸의 갯수가 K개 이상이면 과정을 종료, 아니면 1번부터 다시 수행합니다.
7. 과정이 종료되면 t를 출력합니다.
두 가지 방법으로 해결하였는데
첫 번째는 벡터(C++)와 연결리스트(Java)를 이용하여 컨베이어 벨트를 직접 옮긴 후에 로봇 이동
두 번째는 올라가는 위치와 내려가는 위치를 인덱스로만 유지하고 로봇 이동
당연히 두 번째방법이 훨씬 효율적이었습니다. 업로드는 두 가지 모두 업로드하겠습니다.
벡터와 연결리스트를 이용한 방법입니다.
저는 벡터를 사용하여 칸의 내구도, 로봇의 존재여부를 저장하였습니다.
컨베이어 벨트가 이동하는 것은 벡터의 마지막 요소를 begin()에 넣어주었고,
N ~ 1번 칸까지 역순으로 컨베이어 벨트 위에있는 모든 로봇을 이동시켜주었습니다.
그 다음 1번 칸에 로봇을 놓았고 이 과정에서 칸의 내구도가 0이되면 ans를 1증가하였습니다.
반복문 마지막에 ans가 K 이상인지 확인하였고, 이상이면 t를 출력하고 리턴, 아니면 계속 반복문을 돌려주었습니다.
그 다음은 인덱스를 유지한 방법입니다.
l = 1
r = N
으로 시작하고 컨베이어 이동 시마다 1씩 빼줍니다. (0이되면 2 * N으로)
그 다음 r부터 l까지 역순으로 컨베이어 벨트 위에있는 모든 로봇을 이동시켜줍니다.
그 다음 l번 칸에 로봇을 놓고 내구도를 감소시킵니다.
이 과정에서 내구도가 0이되면 ans++, ans가 K 이상이면 t를 출력합니다.
로직은 같으나 컨베이어 이동을 시뮬레이션으로 직접 이동시키냐, 인덱스만 이동시키냐에 따라 시간 차이가 크게남을 확인하였습니다.
[벡터 이용한 풀이]
[C++]
|
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
|
#include <iostream>
#include <vector>
using namespace std;
vector<pair<int, int> > list;
int N, K, ans;
void func() {
for (int t = 1; ; t++) {
list.insert(list.begin(), list[2 * N - 1]);
list.pop_back();
for (int i = N - 1; i >= 0; i--) {
if (i == N - 1) {
list[i].second = 0;
continue;
}
if (!list[i].second) continue;
if (!list[i + 1].first || list[i + 1].second) continue;
if (i + 1 != N - 1) list[i + 1].second = 1;
list[i].second = 0;
list[i + 1].first--;
if (!list[i + 1].first) ans++;
}
if (list[0].first) {
list[0].second = 1;
list[0].first--;
if (!list[0].first) ans++;
}
if (ans >= K) {
cout << t << '\n';
break;
}
}
}
void input() {
int x;
cin >> N >> K;
for (int i = 1; i <= 2 * N; i++) {
cin >> x;
list.push_back({ x, 0 });
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
[Java]
|
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
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static LinkedList<int[]> list = new LinkedList<>();
static int N, K, ans;
static void func() {
for (int t = 1;; t++) {
list.addFirst(list.pollLast());
for (int i = N - 1; i >= 0; i--) {
if (i == N - 1) {
list.get(i)[1] = 0;
continue;
}
if (list.get(i)[1] == 0)
continue;
if (list.get(i + 1)[0] == 0 || list.get(i + 1)[1] != 0)
continue;
if (i + 1 != N - 1)
list.get(i + 1)[1] = 1;
list.get(i)[1] = 0;
list.get(i + 1)[0]--;
if (list.get(i + 1)[0] == 0)
ans++;
}
if (list.get(0)[0] > 0) {
list.get(0)[0]--;
list.get(0)[1] = 1;
if (list.get(0)[0] == 0)
ans++;
}
if (ans >= K) {
System.out.println(t);
break;
}
}
}
static void input() throws Exception {
int x;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
st = new StringTokenizer(br.readLine());
for (int i = 0; i < 2 * N; i++) {
x = Integer.parseInt(st.nextToken());
list.addLast(new int[] { x, 0 });
}
}
public static void main(String[] args) throws Exception {
input();
func();
}
}
|
cs |
[인덱스 유지]
[C++]
|
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
|
#include <iostream>
using namespace std;
pair<int, int> list[201];
int N, K, ans;
void func() {
int l = 1;
int r = N;
for (int t = 1; ; t++) {
l--;
r--;
if (!l) l = 2 * N;
if (!r) r = 2 * N;
for (int i = r; ; i--) {
if (!i) i = 2 * N;
if (i == r) {
list[i].second = 0;
continue;
}
int next = i + 1;
if (next == 2 * N + 1) next = 1;
if (!list[i].second) {
if (i == l) break;
continue;
}
if (!list[next].first || list[next].second) {
if (i == l) break;
continue;
}
if (next != r) list[next].second = 1;
list[i].second = 0;
list[next].first--;
if (!list[next].first) ans++;
if (i == l) break;
}
if (list[l].first) {
list[l].second = 1;
list[l].first--;
if (!list[l].first) ans++;
}
if (ans >= K) {
cout << t << '\n';
break;
}
}
}
void input() {
int x;
cin >> N >> K;
for (int i = 1; i <= 2 * N; i++) {
cin >> list[i].first;
}
}
int main() {
cin.tie(NULL); cout.tie(NULL);
ios::sync_with_stdio(false);
input();
func();
return 0;
}
|
cs |
[Java]
|
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
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static int list[][];
static int N, K, ans;
static void func() {
int l = 1;
int r = N;
for (int t = 1;; t++) {
l--;
r--;
if (l == 0)
l = 2 * N;
if (r == 0)
r = 2 * N;
for (int i = r;; i--) {
if (i == 0)
i = 2 * N;
if (i == r) {
list[i][1] = 0;
continue;
}
int next = i + 1;
if (next == 2 * N + 1)
next = 1;
if (list[i][1] == 0) {
if (i == l)
break;
continue;
}
if (list[next][0] == 0 || list[next][1] == 1) {
if (i == l)
break;
continue;
}
if (next != r)
list[next][1] = 1;
list[i][1] = 0;
list[next][0]--;
if (list[next][0] == 0)
ans++;
if (i == l)
break;
}
if (list[l][0] > 0) {
list[l][1] = 1;
list[l][0]--;
if (list[l][0] == 0)
ans++;
}
if (ans >= K) {
System.out.println(t);
break;
}
}
}
static void input() throws Exception {
int x;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
list = new int[2 * N + 1][2];
st = new StringTokenizer(br.readLine());
for (int i = 1; i <= 2 * N; i++) {
list[i][0] = Integer.parseInt(st.nextToken());
}
}
public static void main(String[] args) throws Exception {
input();
func();
}
}
|
cs |