문제 해석

진짜 진짜 문제 해석이 너무 어려운 문제였다.
글의 모든 부분을 잘 읽어야 풀 수 있다.

올리는 위치와 내리는 위치라는 것은 벨트 위에 올라간 로봇이 벨트 위에 새롭게 올라가거나 아예 내려가게 되는 위치를 말하는 것임.

또한,위의 빨간 줄 '언제든지 로봇이 내리는 위치에 도달하면 내린다' 라는 말에서 '언제든지'!!에 주의해야 한다. 이 빨간색 조건은 1번과 2번에 영향을 준다.

벨트는 매턴 로봇과 함께 한칸씩 슬라이딩하면서 이동하고, 로봇은 이후에 또 혼자 자체적으로 움직일 수 있는 턴을 갖게 된다. 해당 내용이 바로 파란 줄이며, 2번과 2-1번에 대한 내용이다.

문제 접근

우선, 처음에 특별한 자료구조를 떠올리기보다는 모듈러 연산을 적용해서 '올리는 위치'와 '내리는 위치'를 매턴 마다 새로 잡고 그 인덱스 구간 안에서 4개의 과정을 진행했다.

이후, 조금 더 쉬운 방법은 없을까 찾아보던 중에 링크드리스트를 활용해서 매턴 시작시, 벨트를 한 칸씩 이동할때 그냥 마지막 벨트 요소를 링크드리스트의 맨 앞으로 이동시키는 방법을 알게 되었다.

하지만, 링크드리스트의 단점인 인덱스를 사용하지 못해서 중간 요소에 접근하는데 선형 시간이 걸린다는 단점 때문인지, 시간 복잡도가 기존 풀이보다 4~5배 정도 오래걸렸다. 물론 문제 풀이는 통과됐지만 옳은 방법인지는 잘 모르겠어서 여기에는 둘 다 적어놓았다.

문제 풀이

첫 번째 풀이 (모듈러 연산 활용)

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int BELT_LENGTH = 2 * N;

        st = new StringTokenizer(br.readLine());

        int[] belt = new int[BELT_LENGTH];
        for (int i = 0; i < BELT_LENGTH; i++) {
            belt[i] = Integer.parseInt(st.nextToken());
        }

        boolean[] isPlaced = new boolean[BELT_LENGTH];

        int zeroSize = 0;
        int step = 0;
        int s = 0; // 로봇을 새로 올리는 위치에 해당하는 칸
        int e = N - 1; // 로봇을 내리는 위치에 해당하는 칸
        while (zeroSize < K) {
            s = (s == 0) ? BELT_LENGTH - 1 : s - 1; // 1번. 올리는 위치에 대응하는 칸 갱신
            e = (s + N - 1) % BELT_LENGTH; // 1번. 내리는 위치에 대응하는 칸 갱신

            isPlaced[e] = false; // e 위치에 있으면 내림.

            int[] turns = new int[N];
            for (int i = 0; i < N; i++) {
                turns[i] = (s + i) % BELT_LENGTH;
            }

            for (int i = N - 1; i >= 0; i--) {
                int next = (turns[i] + 1) % BELT_LENGTH;
                if (isPlaced[turns[i]] && (belt[next] >= 1 && !isPlaced[next])) {
                    isPlaced[turns[i]] = false;
                    isPlaced[next] = true;
                    belt[next]--;
                    if (belt[next] == 0) zeroSize++;
                }
            }
            isPlaced[e] = false;

            if (belt[s] > 0) {
                isPlaced[s] = true;
                belt[s]--;
                if (belt[s] == 0) zeroSize++;
            }
            step++;
        }

        System.out.println(step);
    }
}

두 번째 풀이(링크드리스트 활용)

import java.io.*;
import java.util.*;

class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        int BELT_LENGTH = 2 * N;

        st = new StringTokenizer(br.readLine());

        LinkedList<Integer> belt = new LinkedList<>();
        LinkedList<Boolean> isPlaced = new LinkedList<>(); // Deque 는 중간 인덱스 요소에 접근이 안된다. 자바는 걍 링크드리스트 쓰면 더 좋다.
        for (int i = 0; i < BELT_LENGTH; i++) {
            belt.addLast(Integer.parseInt(st.nextToken()));
            isPlaced.addLast(false);
        }

        int zeroSize = 0;
        int step = 0;
        while (zeroSize < K) {
            belt.addFirst(belt.getLast());
            isPlaced.addFirst(isPlaced.getLast());
            belt.removeLast();
            isPlaced.removeLast();
            isPlaced.set(N - 1, false); // 내림.

            for (int i = N - 1; i >= 0; i--) {
                int nextBelt = belt.get(i+1);
                if (isPlaced.get(i) && (nextBelt >= 1 && !isPlaced.get(i + 1))) {
                    isPlaced.set(i, false);
                    isPlaced.set(i + 1, true);
                    belt.set(i + 1, nextBelt - 1);
                    if (nextBelt == 1) zeroSize++;
                }
            }
            isPlaced.set(N - 1, false); // 내림

            int firstBelt = belt.getFirst();
            if (firstBelt > 0) {
                isPlaced.set(0, true);
                belt.set(0, firstBelt - 1);
                if (firstBelt == 1) zeroSize++;
            }
            step++;
        }

        System.out.println(step);
    }
}

시뮬레이션 문제 풀 때 주의사항

1. 시뮬레이션 풀 때는 하라는 대로 잘 따라하자.
2. 문제를 잘 읽자.
3. 문제를 다시 읽자.