문제 풀이
단순한 구현문제, 별 다른 기술이 필요한 것이 아니고 문제를 잘 이해하고 구현하는게 핵심인 듯하다.
각 칸의 hp를 저장할 배열 하나, 각 칸에 로봇이 있는지 없는지 나타낼 배열 하나, 컨베이어 벨트 위에 올라간 로봇의 위치 정보를 차례대로 담을 큐 하나를 활용한다.
로봇을 옮기는 과정 순서를 보면
-
벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다.
- 원형으로 컨베이어 벨트가 이어져있으므로 hp 배열과 robot위치 배열을 현재의 마지막이 다음 첫번째가 되도록 잘 회전시켜준다.
- 큐를 사용하면된다. 현재 큐 사이즈만큼만 for문을 돌면 순서가 잘 유지 된다.
for (int i = 0; i < len; i++) { int cur = q.poll(); int next_pos = 0; is_robot[cur] = 0; if (cur + 1 == 2 * n) next_pos = 0; else next_pos = cur + 1; if(next_pos == n-1) continue; q.add(next_pos); is_robot[next_pos] = 1; }```- pop 한다.
- 로봇이 있던 칸에는 로봇이 없어진다.(이동할 것이므로 0)
- 다음 위치를 정한다. (현재칸 + 1, 배열의 마지막일 경우 0)
- 4.1. 내리는 위치일 경우(next_pos == n-1)
- 다음으로 넘어간다
- 4.2. 내리는 위치가 아닐경우
- 이동 했으므로 다음 위치에는 로봇이 있다고 표시
- 큐에 다시 로봇의 위치를 push
- 4.1. 내리는 위치일 경우(next_pos == n-1)
-
가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 가만히 있는다.
- 로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 한다.
- 위의 의사 코드와 전체적으로 비슷하지만 움직이지 않았을 경우 다시 현재 위치에 로봇이있다고 표시하고 현재 위치를 큐에 push한다.
- 이동했다면 이동했으므로 내구도를 깎는다.
- 올리는 위치에 있는 칸의 내구도가 0이 아니면 올리는 위치에 로봇을 올린다.
- 올리는 위치에 로봇이 있는 상황은 없다 내구도만 고려해서 올리면 된다.
- 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다.
- hp[i] == 0 일때마다 k를 깎아주고 종료 조건을 k == 0으로 하면 된다.
※내가 한 실수
- 올리는 곳과 내리는 곳의 인덱스를 잘 확인하자. 칸의 인덱스는 0부터 시작하므로 내리는 곳은 n이 아닌 n-1이다.
- 처음엔 arrayList에 로봇의 위치를 저장하고 로봇이 내려가면 위치를 -1로 설정해주고 로봇을 이동할때마다 모든 arrayList의 로봇들을 순회했다.(로봇이 너무 많아지면 시간초과)
-> 큐를 사용하고 큐를 현재 size만큼 pop하는 방법을 쓰자.
문제 링크
소스코드
import java.io.*;
import java.util.*;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws IOException {
StringTokenizer st = new StringTokenizer(br.readLine());
int n = Integer.parseInt(st.nextToken());
int k = Integer.parseInt(st.nextToken());
int []hp= new int [2*n];
int []is_robot= new int [2*n];
st = new StringTokenizer(br.readLine());
for(int i=0;i<2*n;i++)
{
hp[i] = Integer.parseInt(st.nextToken());
}
Queue<Integer> q = new LinkedList<>();
int cnt = 0;
while(k>=1) {
cnt++;
int tmp = hp[2 * n - 1];
for (int i = 2 * n - 1; i >= 1; i--) {
hp[i] = hp[i - 1];
}
hp[0] = tmp;
int len = q.size();
for (int i = 0; i < len; i++) {
int cur = q.poll();
int next_pos = 0;
is_robot[cur] = 0;
if (cur + 1 == 2 * n)
next_pos = 0;
else
next_pos = cur + 1;
if(next_pos == n-1)
continue;
q.add(next_pos);
is_robot[next_pos] = 1;
}
len = q.size();
for (int i = 0; i < len; i++) {
int cur = q.poll();
is_robot[cur] = 0;
int next_pos = 0;
if (cur + 1 != 2 * n)
next_pos = cur + 1;
if (is_robot[next_pos] != 1 && hp[next_pos] >= 1) {
hp[next_pos]--;
if(hp[next_pos]==0)
k--;
if(next_pos == n-1)
continue;
q.add(next_pos);
is_robot[next_pos] = 1;
}
else
{
is_robot[cur] =1;
q.add(cur);
}
}
if (hp[0] != 0) {
q.add(0);
is_robot[0] = 1;
hp[0]--;
if(hp[0] == 0)
k--;
}
int check = 0;
}
bw.write(Integer.toString(cnt));
bw.flush();
}
}.jpg)
be