백준 20055 번 : 컨베이어 벨트 위의 로봇 풀이(Java) - 삼성 역량 테스트 A형 기출문제

www.acmicpc.net/problem/20055

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

문제 설명이 모호한 점이 많아서 삽질을 좀 했다. 먼저,

1. 회전할 때는 내구도가 소모되지 않는다. (오로지 이동할 때, 첫 칸에 로봇을 둘 때만 내구도가 감소한다.)

2. 그림이 2줄의 배열이 돌아가는 형태로 그려져서 오해하기 쉬운데, 로봇은 "내려가는 위치" 즉, [0][N-1] 에 도착하자마자 무조건 바로 떨어져서 사라진다. 즉, 이동에 의한 이동이든, 회전에 의한 이동이든 무조건 내려가는 위치에 도착하면 사라져야 한다.

3. 벨트는 회전한다. 이게 무슨 의미냐면, 벨트 한 칸마다 고유한 내구도가 있는데, 이것들이 회전을 해야한다는 말이다.

내구도가

 

10 10 10

9 9 9

 

로 되어있을 경우, 회전하면

 

9 10 10

9 9 10

 

으로 되어야 한다는 의미이다.

 

로봇의 이동이나 로봇을 새로 놓는 행위에 대해서, 고정적인 위치가 아니라는 의미이다.

 

나는 위의 세 가지를 제대로 파악 못해서 푸는 데 좀 걸렸다. 이런 구현 문제가 정말 어렵게 나오면 어려운 것 같다.

 

Solution

0. input 받기

- 내구도를 나타내는 A를 윗 줄인 topA와 bottomA 로 나눴고, 이들을 ArrayList<Integer> 로 설정했다.

- 로봇은 위의 한 줄에만 있으므로, topRobot 이라는 객체를 ArrayList<boolean> 으로 만들어줬다. true이면 로봇이 해당 위치에 있는 것, false 이면 없다는 것이다. 

 

이 때 bottomA에서 중요한 것이 있는데, input으로 들어오는 순서가 bottomA에서는 역순이 되어야 한다는 것이다. 내구도가 만약

 

1 2 3 4 5 6 7 8

 

로 들어오면, topA와 bottomA로 나눠보면

 

1 2 3 4

8 7 6 5

 

가 되어야 한다.

만약 topA를 받는 순서가 정순이라고 그대로 받으면,

 

1 2 3 4

5 6 7 8

 

이 되어버리므로, 주의하자. 나는 받고 난 후에 Collections.reverse(bottomA) 로 뒤집어줬다.

 

1. 회전

회전할 때는 "내려가는 위치"에 있는, 즉 topA의 마지막 요소 를 bottomA 의 마지막 요소로 넣어주고, "올라가는 위치" 에 "올라 가야할 요소" 즉, bottomA의 첫 번째 요소 를 topA의 첫 번째 요소로 넣어준다. 이후, topA의 마지막 요소, bottomA의 첫 번째 요소들은 이미 이동했으므로 삭제해주면, 자연스레 회전이 완성된다.

 

2. 이동

로봇은 왼쪽에서 오른쪽으로 이동하므로, (윗 벨트의 이동방향이 왼쪽->오른쪽이므로) 이동할 수 있는 조건은,

1. 다음 위치의 내구도가 0보다 큰지(초과)

2. 다음 위치에 로봇이 이미 있는지

3. 현재 위치에 로봇이 있어서 이동 가능 한지

 

이다. 이 때,

topRobot을 오른쪽에서 왼쪽으로 순회하면서 확인한다. 그렇지 않으면,

 

T F F F F

일 때, 왼쪽에서 오른쪽으로 순회하면

F F F F T 

가 될 것이다. 로봇은 한 번의 이동에서 한 칸 만 이동하므로 이는 일어나서는 안 된다.

 

3. 로봇 올리기

제일 간단한 메서드이다.

1. topA의 첫 번째 요소, 즉 "올라가는 위치"의 내구도가 0 보다 크고,

2. topRobot의 첫 번째 요소, 즉 "올라가는 위치"에 로봇이 없어야 한다.

그럴 경우, "올라가는 위치"에 topRobot 을 true 로 해서 로봇을 올려주고, topA는 1 감소 시켜주면 된다.

 

4. 내구도가 0인 칸이 K를 넘어가는지 체크하기

단순하게 topA와 bottomA를 모두 돌면서 내구도가 0 이하인 칸을 세어주고, K보다 큰지 작은지 boolean 을 리턴해준다.

 

이렇게 4가지의 메서드를 만들고, main 에서,

while(!4()) {
	1();
    2();
    3();
    cnt++;
}

이런 식으로 구현해줬다.

 

Source Code

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

public class Main {
    static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
    static int N,K,cnt;
    static ArrayList<Integer> topA;
    static ArrayList<Integer> bottomA;
    static ArrayList<Boolean> topRobot;
    static void input() throws IOException {
        StringTokenizer nk = new StringTokenizer(bufferedReader.readLine());
        N = Integer.parseInt(nk.nextToken());
        K = Integer.parseInt(nk.nextToken());
        topA = new ArrayList<>();
        bottomA = new ArrayList<>();
        topRobot = new ArrayList<>();
        StringTokenizer a = new StringTokenizer(bufferedReader.readLine());
        for(int i = 0; i < 2; i++) {
            for(int j = 0 ; j < N;j++) {
                if(i == 0) {
                    topA.add(Integer.parseInt(a.nextToken()));
                    topRobot.add(false);
                } else {
                    bottomA.add(Integer.parseInt(a.nextToken()));
                }
            }
        }
        Collections.reverse(bottomA);
    }
    
    static void addRobot() {
        //System.out.println("3. 로봇 놓기 단계");
        if(topA.get(0) > 0 && !topRobot.get(0)) {
            topRobot.set(0, true);
            topA.set(0, topA.get(0) - 1);
        }
    }

    static void printRobots() { // 디버그용 메서드.
        System.out.println("==========로봇 상태==========");
        for(int j = 0 ; j < N;j++) {
            if(topRobot.get(j)) System.out.print("R ");
            else System.out.print("X ");
        }
        System.out.println("\n=========내구도 상태============");
        for(int i = 0; i < 2; i++) {
            for(int j = 0 ; j < N;j++) {
                if(i == 0) System.out.print(topA.get(j) + " ");
                else System.out.print(bottomA.get(j) + " ");
            }
            System.out.println();
        }
        System.out.println("=================");
    }

    static void rotate() {
        //System.out.println("1. 회전 단계");
        topRobot.add(0, false); // 처음에 robot을 없애주고
        topRobot.remove(topRobot.size() - 1); // 마지막에 robot은 땅으로
        topA.add(0, bottomA.get(0));
        bottomA.add(bottomA.size() , topA.get(topA.size() - 1));
        topA.remove(topA.size()-1);
        bottomA.remove(0);
        if(topRobot.get(topRobot.size() - 1)) {
            topRobot.set(topRobot.size() - 1, false);
        }
    }

    static void move() {
        //System.out.println("2. 움직임 단계");

        for(int i = N-1; i > 0; i--) {
            int now = topA.get(i);
            boolean isNowRobot = topRobot.get(i);
            boolean isBeforeRobot = topRobot.get(i-1);
            if(now > 0 && !isNowRobot && isBeforeRobot) {
                topA.set(i, topA.get(i) - 1);
                topRobot.set(i, true);
                topRobot.set(i-1, false);
            }
            if(topRobot.get(topRobot.size() - 1)) {
                topRobot.set(topRobot.size() - 1, false);
            }
        }
    }

    static boolean isZeroMoreThanK() {
        int zeroCnt = 0;
        for(int j = 0 ; j < N; j++) {
            if(topA.get(j) <= 0) {
                zeroCnt++;
            }
        }
        for(int j = 0 ; j < N; j++) {
            if(bottomA.get(j) <= 0) {
                zeroCnt++;
            }
        }
//        System.out.println("4. 체크 단계 : 현재 0인 칸의 갯수 : " + zeroCnt);
//        printRobots();
        if(zeroCnt >= K) {
            return true;
        }
        else {
            return false;
        }
    }

    static void solve() {
        while (!isZeroMoreThanK()) {
            rotate();
            move();
            addRobot();
            cnt++;
        }
        System.out.println(cnt);
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
    }
}