boj 20055 컨베이어 벨트 위의 로봇

www.acmicpc.net/problem/20055

20055번: 컨베이어 벨트 위의 로봇

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를 출력합니다.

 

Java LinkedList를 이용한 방법

Java 인덱스를 이동한 방법

 

로직은 같으나 컨베이어 이동을 시뮬레이션으로 직접 이동시키냐, 인덱스만 이동시키냐에 따라 시간 차이가 크게남을 확인하였습니다.

 

 

[벡터 이용한 풀이]

[C++]

#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;
}

[C++]

#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;
}

 

 

[Java]

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();
    }
}