https://www.acmicpc.net/problem/20055
삼성 기출 문제를 풀어보았다.
우선탐색, 동적 계획법 문제들 보다는 상대적으로 쉬운 시뮬레이션 문제였다.
하지만 점점 문제의 티어가 올라가면 올라갈 수록 아 괜히 이 티어와 레벨이 아니구나 라는걸 느끼게 된다.
문제를 이해하기가 상당히 난해했다.
정리하자면,
1. 먼저 컨베이어벨트를 가동한다.
2. 로봇을 처음 위치 belt[0]에 탑승시킨다.
3. 컨베이어벨트가 이동한다.
4. 로봇을 처음 위치에서 조건 확인 후 계속 올리고, 컨베이어 벨트 위에 있는 로봇들은 조건이 맞으면 계속 이동시키고 내릴 위치 belt[N-1]에 내려준다.
5. 내구도 0을 체크한다.
6. 3번부터 5번까지 반복한다.
시뮬레이션 문제라서 제한사항이 적혀있는 데로 개발해주면 된다.
이 문제를 풀면서 겪었던 시행착오를 적어보겠다.
※ 시행착오
(1) 컨베이어벨트 회전시킬 때 N-1의 위치에 오면 로봇이 있을 때 로봇을 내려주지 않았음
-> 로봇을 내려주지 않아서 2번케이스에서 엉뚱한 답, 3번 케이스 이후로 계속 무한루프에 빠졌었다.
(2) 컨베이어벨트 회전 시 i의 위치가 0일때 i+1의 위치로 벨트를 옮겨주지 않았다.
-> 1번 케이스에서 엉뚱한 답, 2번케이스 이후로 무한루프에 빠진다.
(3) 원래 int robotCnt = 0; 이라는 변수를 만들어서 로봇의 개수가 0일때와 아닐 때의 경우를 나눠서 0이면 for문을 돌지 않게 했다. 어찌되었든 로봇의 갯수를 세는 부분은 불필요한 부분이었다.
-> 어짜피 시작 위치에서만 로봇을 올려주면 되니까 라는 생각으로 belt[0].durability와 onRobot 값을 초기화했지만, 결과적으로 4번 케이스에서 476이라는 결과가 나왔었다. (4번 케이스 정답 : 472)
package samsung;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;
public class RobotOnConveyor {
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());
Belt[] belt = new Belt[2*N];
st = new StringTokenizer(br.readLine(), " ");
for (int i = 0; i < belt.length; i++) {
belt[i] = new Belt();
belt[i].durability = Integer.parseInt(st.nextToken());
belt[i].onRobot = false;
}
int stage = 1;
int k2 = 0;
do {
// 1. 벨트 회전
Stack<Belt> stack = new Stack<Belt>();
for (int i = belt.length - 1; i >= 0; i--) {
// 벨트 끝에 있는 벨트 한 덩이를 스택에 넣는다
if(i == belt.length - 1) {
stack.push(belt[i]);
// 처음 위치일 때 스택에 있는 벨트 한 덩어리를 빼넣는다.
} else if (i == 0) {
belt[i+1] = belt[i];
belt[i] = stack.pop();
// N 위치일 때 로봇이 있으면 로봇을 내린다.
} else {
if(belt[i].onRobot && i == N-1) {
belt[i].onRobot = false;
}
belt[i+1] = belt[i];
}
}
// 로봇 이동
for (int i = N -1; i >= 0; i--) {
// 첫 위치에 로봇을 올린다.
if(i == 0) {
if(!belt[i].onRobot && belt[i].durability > 0) {
belt[i].onRobot = true;
belt[i].durability--;
if(belt[i].durability == 0) k2++; // 내구도 체크
}
// N번쨰 위치에서 로봇을 내린다.
} else if(i == N -1) {
if(belt[i].onRobot) belt[i].onRobot = false;
// 로봇을 이동시킨다.
} else {
if(belt[i].onRobot && !belt[i+1].onRobot && belt[i+1].durability > 0) {
belt[i].onRobot = false;
belt[i+1].onRobot = true;
belt[i+1].durability--;
if(belt[i+1].durability == 0) k2++; // 내구도 체크
}
}
if(k2 >= K) break; // 내구도 K개 이상일 때 나간다
}
if(k2 >= K) break;
stage++;
} while (k2 < K);
System.out.println(stage);
}
}
class Belt {
int durability;
boolean onRobot;
public Belt() {}
public Belt(int durability, boolean onRobot) {
this.durability = durability;
this.onRobot = onRobot;
}
@Override
public String toString() {
return "durability : " + this.durability + ", onRobot : " + this.onRobot + "\n";
}
}
'코딩테스트 > 백준' 카테고리의 다른 글
[백준/java] 21922번: 학부 연구생 민상 - BFS (0) | 2021.08.10 |
---|---|
[백준/java] 1926번: 그림 - BFS(Breath-First-Search) (0) | 2021.08.07 |
[백준/java] 5430번: AC - 큐 (0) | 2021.08.05 |
[백준/java] 1966번: 프린터 큐 (0) | 2021.08.04 |
[백준/java] 1021번: 회전하는 큐 - 얕은 복사, 깊은 복사 (0) | 2021.08.03 |
댓글