Language
JAVA
Input
-
컨베이어 벨트 길이 N, 종료 기준 K
(내구도가 0인 칸의 개수가 K개 이상이면 종료) -
벨트 각 칸의 내구도 A1, A2, ..., A2N
(컨베이어 벨트의 길이가 N이면, 전체 벨트의 길이가 2N)
Output
몇 번째 단계가 진행 중일때 종료되었는지 출력
문제 이해 및 풀이
문제 종류 : 시뮬레이션, 구현
문제 풀이에 걸린 시간 : 1시간 20분 (분발하자...)
단순 시뮬레이션 문제이다. 따라서, 벨트의 구조만 잘 설정하면 된다.
한 번의 iteration은 총 4단계로 이루어진다.
- 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다.
- 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 가만히 있는다.
- 로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 한다.
- 올리는 위치에 있는 칸의 내구도가 0이 아니면 올리는 위치에 로봇을 올린다.
- 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다.
벨트의 구조
벨트는 array로 설정하였고, 각 belt의 칸은 총 4개의 정보가 담겨있는 구조체가 되도록 설정하였다.
class tile{
int cost, position, index;
boolean isRobot;
public tile(int index, int position, int cost, boolean isRobot){
this.index = index; this.position = position; this.cost = cost;
this.isRobot = isRobot;
}
}
position은 벨트의 위치, index는 그 벨트의 고유번호(항상 belt[i].index = i
이지만 헷갈리지 않기 위해서 넣었다.), cost는 해당 칸의 내구도이다.
STEP 1
- 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다.
오른쪽으로 한 칸씩 이동해준다. 기본적으로 포지션이 +1이 되지만, 만약 2*N 포지션에 있던 벨트 칸이라면 1 포지션으로 올라가게 된다. 그리고 1 포지션(해당 단계에서 로봇이 올라가게 될 포지션)으로 갱신이 된다면, upIndex의 index를 갱신해주도록 한다.
public static void step1(){
for(int i = 1; i <= 2*N; i++){
if(belt[i].position == 2*N) {
belt[i].position = 1; //2*N 포지션에 있던 칸 => 1로
upIndex = belt[i].index;//1번 포지션에 있는 칸의 index로 업데이트
}
else{
belt[i].position += 1;
//만약 N 포지션에 도착한 칸에 로봇이 있다면 로봇을 내려준다.
if(belt[i].position == N) {
belt[i].isRobot = false;
}
}
}
}STEP 2
- 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 가만히 있는다.
- 로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 한다.
이제 컨베이어 벨트 위에 있는 벨트에 한정하여 로봇을 움직일 수 있으면 움직여 주는 작업을 한다.
public static void step2(){
int tmp_Index,next_Index;
for(int i = N-2; i >= 0; i--){
tmp_Index = upIndex + i; // check해야할 Index
if(tmp_Index > 2* N) tmp_Index %= (2*N);
next_Index = tmp_Index + 1;
if (next_Index > 2*N) next_Index = 1;
//이 칸에 로봇이 있고, 다음 칸에 로봇이 없고, 다음 칸의 내구도가 1 이상이면 로봇을 옮긴다.
if(belt[tmp_Index].isRobot && !belt[next_Index].isRobot && belt[next_Index].cost >= 1){
//로봇을 옮김
belt[tmp_Index].isRobot = false;
belt[next_Index].isRobot = true;
//로봇이 이동하였으므로 해당 칸 내구도 -1
belt[next_Index].cost -= 1;
if(belt[next_Index].cost == 0) ZERO += 1; //만약 0이 되면 zero를 +1
if(belt[next_Index].position == N) belt[next_Index].isRobot = false;
}
}
}STEP 3
- 올리는 위치에 있는 칸의 내구도가 0이 아니면 올리는 위치에 로봇을 올린다.
올리는 위치에 있는 칸 = POSITION 1 = STEP 1에서 저장하였던 index의 벨트 =
upIdex !!
public static void step3(){
if(belt[upIndex].cost > 0){
belt[upIndex].isRobot = true; //로봇을 올려줌
belt[upIndex].cost -= 1; //로봇을 올렸으므로 내구도 -1
if(belt[upIndex].cost == 0) ZERO += 1; //만약 내구도가 0이 되면 0인 칸 개수 +1
}
}Code
import java.io.*;
class tile{
int cost, position, index;
boolean isRobot;
public tile(int index, int position, int cost, boolean isRobot){
this.index = index; this.position = position; this.cost = cost;
this.isRobot = isRobot;
}
}
public class Main {
public static tile belt[]; // belt의 길이 2N (1~2N), 각 array에는 내구도 저장
public static int N,K;
public static int result = 0;
public static int upIndex = 1; //처음 올리는 칸의 인덱스 1로 초기화
public static int ZERO = 0;
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String str = br.readLine();
String[] sp = str.split(" ");
N = Integer.parseInt(sp[0]);
K = Integer.parseInt(sp[1]);
belt = new tile[2*N + 1];
str = br.readLine();
sp = str.split(" ");
//belt 초기 상태 저장 : index = i, position = i, cost = 입력, isRobot=false
for(int i = 1; i <= 2*N; i++){
belt[i] = new tile(i,i,Integer.parseInt(sp[i-1]),false);
}
while(true){
result++;
step1();
step2();
step3();
//STEP4
if(ZERO >= K) break;
}
bw.write(result+"");
bw.flush();
}
// step 1 : 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다.
public static void step1(){
for(int i = 1; i <= 2*N; i++){
if(belt[i].position == 2*N) {
belt[i].position = 1; //2*N 포지션에 있던 칸 => 1로
upIndex = belt[i].index;//1번 포지션에 있는 칸의 index로 업데이트
}
else{
belt[i].position += 1;
//만약 N 포지션에 도착한 칸에 로봇이 있다면 로봇을 내려준다.
if(belt[i].position == N) {
belt[i].isRobot = false;
}
}
}
}
//step 2
//가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다.
// 만약 이동할 수 없다면 가만히 있는다.
//로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 한다.
public static void step2(){
int tmp_Index,next_Index;
for(int i = N-2; i >= 0; i--){
tmp_Index = upIndex + i; // check해야할 Index
if(tmp_Index > 2* N) tmp_Index %= (2*N);
next_Index = tmp_Index + 1;
if (next_Index > 2*N) next_Index = 1;
//이 칸에 로봇이 있고, 다음 칸에 로봇이 없고, 다음 칸의 내구도가 1 이상이면 로봇을 옮긴다.
if(belt[tmp_Index].isRobot && !belt[next_Index].isRobot && belt[next_Index].cost >= 1){
//로봇을 옮김
belt[tmp_Index].isRobot = false;
belt[next_Index].isRobot = true;
//로봇이 이동하였으므로 해당 칸 내구도 -1
belt[next_Index].cost -= 1;
if(belt[next_Index].cost == 0) ZERO += 1; //만약 0이 되면 zero를 +1
if(belt[next_Index].position == N) belt[next_Index].isRobot = false;
}
}
}
//step 3 : 올리는 위치에 있는 칸의 내구도가 0이 아니면 올리는 위치에 로봇을 올린다
public static void step3(){
if(belt[upIndex].cost > 0){
belt[upIndex].isRobot = true; //로봇을 올려줌
belt[upIndex].cost -= 1; //로봇을 올렸으므로 내구도 -1
if(belt[upIndex].cost == 0) ZERO += 1; //만약 내구도가 0이 되면 0인 칸 개수 +1
}
}
}check
- 시뮬레이션 문제는 설명이 어렵다..
- 전체 골자는 40분 정도에 다 짰지만, step3에서 포지션 N에서 즉시 로봇을 내려주는 작업을 하지 않아서 "단 한 줄" 으로 나머지 시간을 소비해버렸다..
문제를 꼼꼼하게 읽고 처음에 무조건 체크해주도록 하자
