🟦/백준
[골드 5] 컨베이어 벨트 위의 로봇
진뚱이용
2023. 8. 8. 20:56
https://www.acmicpc.net/problem/20055
20055번: 컨베이어 벨트 위의 로봇
길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부
www.acmicpc.net
와 이걸 진짜 ㅈㄴ 헤맸다
오른쪽으로 미는 경우
1. i=0부터
해서 i+1자리에 i를 넣으면 i+1이 사라진다 그러면 기억하면서 다녀야 하는데 생각보다 어려웠음
2. i=n-1부터
i-1을 i에 넣으면 데이터 손실도 없고 개 쉽겠다
근데 오기로 i=0부터 넣는 거 했음
public static void rotate(int[] arr) {
int now;
int prev = arr[0];
arr[0] = arr[arr.length - 1];
for (int i = 0; i < arr.length - 1; i++) {
now = arr[i + 1];
arr[i + 1] = prev;
prev = now;
}
}
* 2차원 배열로 new int [2][N] 할까 했는데 그럴 필요 없을 것 같아서 new int [2*N]
* ArrayList <Integer> 안 쓰고 가짜? 클래스 Robot 만든 이유 robots.get(i)++; 이 안돼 왜 안 되는 거냐
이런 문제는 짱구 돌리지 말고 그대로 푸는 게 마음 편하다
무한
1. answer++
1. arr 판 돌려
2. 로봇들 공짜로 돌려 근데 로봇 N-1 가면 죽여
3. 로봇 돈 주고 돌려
3-1. 앞칸 내구도 있어야 하고 i-1 로봇이 내 앞칸에 없어야 해!
3-2. 내구도 깎아 내구도 0이야? 내구도_count++;
3-3. 이동시켰는데 N-1? 죽여
4. 0에 내구도 있으면 로봇 만들어 내구도 깎아 내구도 0이야? 내구도_count++;
5. 내구도_cnt >= K이면 멈춰
import java.io.*;
import java.util.*;
class Robot {
int index;
}
class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st;
int N, K;
int[] arr;
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
K = Integer.parseInt(st.nextToken());
arr = new int[2 * N];
st = new StringTokenizer(br.readLine());
for (int i = 0; i < arr.length; i++)
arr[i] = Integer.parseInt(st.nextToken());
/////////////////////////////////////////////////
// 0이 올리는 위치 // N-1이 내리는 위치
// 0 index 로봇이 틀딱 로봇
ArrayList<Robot> robots = new ArrayList<>();
int durability_count = 0;
int answer = 0;
while (true) {
answer++;
// 1. 벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다.
rotate(arr);
for (int i = 0; i < robots.size(); i++) {
robots.get(i).index++;
if (robots.get(i).index == N - 1) {
robots.remove(i);
i--;
}
}
// 2. 가장 먼저 벨트에 올라간 로봇부터,
// 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 가만히 있는다.
for (int i = 0; i < robots.size(); i++) {
// 앞칸에 내구도가 있어
if (arr[robots.get(i).index + 1] > 0) {
// 내가 최초 로봇이다! || 내 앞에 로봇이 있는데 ㄱㅊ
if (i == 0 || robots.get(i).index + 1 != robots.get(i - 1).index) {
robots.get(i).index++;
arr[robots.get(i).index]--;
if (arr[robots.get(i).index] == 0) {
durability_count++;
}
}
}
// 이동 시켰더니 막칸이네 넌 내려가라
if (robots.get(i).index == N - 1) {
robots.remove(i);
i--;
}
}
if (arr[0] != 0) {
robots.add(new Robot());
arr[0]--;
if (arr[0] == 0)
durability_count++;
}
if (durability_count >= K)
break;
}
System.out.println(answer);
}
public static void rotate(int[] arr) {
int now;
int prev = arr[0];
arr[0] = arr[arr.length - 1];
for (int i = 0; i < arr.length - 1; i++) {
now = arr[i + 1];
arr[i + 1] = prev;
prev = now;
}
}
}