https://www.acmicpc.net/problem/20055
마찬가지로 구현이며, 삼성 SW 역량테스트 기출이다.
삼성은 참 구현을 선호하는 것 같다.
문제 설명 및 입출력
문제에서 추출할 수 있는 정보는 다음과 같다.
- 벨트 맨 왼쪽 위칸은 올리는 위치이며 로봇을 올릴 수 있다.
- 올리는 위치에 로봇을 올리면 내구도가 1 감소
- 이동하려는 칸에 로봇이 없고 내구도가 1 이상 남아 있어야 로봇이 이동 가능하다.
- 벨트 맨 오른쪽 아래칸은 내리는 위치이며,내리는 위치에 로봇이 도착하면 바로 제거한다.
- 내구도가 0인 칸의 개수가 k개 이상이 되는 순간의 단계를 구한다.
해결 과정
먼저 이 문제의 가장 핵심적인 로봇의 이동 과정을 순서대로 정리해보자.
1.벨트가 각 칸 위에 있는 로봇과 함께 한 칸 회전한다.
벨트는 2 * N 형태이므로 이를 표현하는 2차원 배열을 활용하자.
벨트가 로봇과 함께 회전함에 주의하자. 1번 벨트의 움직임과 2번 로봇의 움직임은 별개다.
벨트의 특정 칸은 로봇 탑승 유무와 현재 내구도에 대한 값을 동시에 지니고 있어야 한다.
우리는 벨트 구조체 및 컨베이어 벨트를 표현할 자료형을 선언해야 한다.
struct belt{
int hp; // 내구도
bool isOn; // 로봇 탑승여부
};
belt belts[2][101];벨트의 회전은 for문을 통해 구현하면 된다. 단 위층의 맨 오른쪽 칸과 아래층의 맨 왼쪽 칸은 따로 변수로 저장한 후 이동하려는 값에 따로 반영하면 된다.
내리는 자리는 컨베이어 벨트의 [0][n-1]에 해당하는 인덱스이기에, 만약 해당 벨트칸에 로봇이 있으면 제거해야 한다.
void rotatebelt(){
belt tmp1 = belts[0][n-1];
belt tmp2 = belts[1][0];
for(int i=n-1; i>=1; i--){ // 위층은 -> 방향 이동
belts[0][i] = belts[0][i-1];
}
for(int i=0; i<n; i++){ // 아래층은 <- 방향 이동
belts[1][i] = belts[1][i+1];
}
belts[0][0] = tmp2;
belts[1][n-1] = tmp1;
if(belts[0][n-1].isOn) // 내리는 자리 비우기
belts[0][n-1].isOn = false;
}2.가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 가만히 있는다.
로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 한다.
-> 조건문을 통해 이동할 수 있는지 여부를 파악하는 과정을 거치자.
로봇이 이동한 후 만약 내리는 자리에 로봇이 있으면 이 또한 제거해야 한다. (누락해서 시간을 꽤 날렸다...)
void moverobot(){
for(int i=n-1; i>=1; i--){
if(belts[0][i-1].isOn && !belts[0][i].isOn && belts[0][i].hp > 0){
belts[0][i-1].isOn = false;
belts[0][i].isOn = true;
belts[0][i].hp--;
}
}
if(belts[0][n-1].isOn) // 내리는 자리 비우기
belts[0][n-1].isOn = false;
}
- 올리는 위치에 있는 칸의 내구도가 0이 아니면 올리는 위치에 로봇을 올린다.
배열의 [0][0] 인덱스에 로봇을 올리고 내구도를 1 감소시키자.
참고로 [0][0] 인덱스는 매 단계마다 올리기 전엔 로봇이 없기에 따로 조건을 걸 필요는 없다.
void addrobot(){ // 올리는 자리에 놓기
if(belts[0][0].hp > 0){
belts[0][0].hp--;
belts[0][0].isOn = true;
}
}
- 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다.
그렇지 않다면 1번으로 돌아간다.
while문으로 1~3단계를 감싸고, 매 단계마다 내구도가 0인 칸이 k개 이상인지 체크하도록 하자.
int cnt = 0;
while(countzero() < k){
rotatebelt();
moverobot();
addrobot();
cnt++;
}
cout << cnt;소스 코드
#include <iostream>
struct belt{
int hp; // 내구도
bool isOn; // 로봇 탑승여부
};
using namespace std;
int n, k;
belt belts[2][101];
int countzero(){ // 0인 칸 개수 체크
int a = 0;
for(int i=0; i<2; i++){
for(int j=0; j<n; j++){
if(belts[i][j].hp == 0) a++;
}
}
return a;
}
void rotatebelt(){
belt tmp1 = belts[0][n-1];
belt tmp2 = belts[1][0];
for(int i=n-1; i>=1; i--){ // 위층은 -> 방향 이동
belts[0][i] = belts[0][i-1];
}
for(int i=0; i<n; i++){ // 아래층은 <- 방향 이동
belts[1][i] = belts[1][i+1];
}
belts[0][0] = tmp2;
belts[1][n-1] = tmp1;
if(belts[0][n-1].isOn) // 내리는 자리 비우기
belts[0][n-1].isOn = false;
}
void moverobot(){
for(int i=n-1; i>=1; i--){
if(belts[0][i-1].isOn && !belts[0][i].isOn && belts[0][i].hp > 0){
belts[0][i-1].isOn = false;
belts[0][i].isOn = true;
belts[0][i].hp--;
}
}
if(belts[0][n-1].isOn) // 내리는 자리 비우기
belts[0][n-1].isOn = false;
}
void addrobot(){ // 올리는 자리에 놓기
if(belts[0][0].hp > 0){
belts[0][0].hp--;
belts[0][0].isOn = true;
}
}
int main(){
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
cin >> n >> k;
for(int i=0; i<n; i++){ // 위층
cin >> belts[0][i].hp;
belts[0][i].isOn = false;
}
for(int i=n-1; i>=0; i--){ // 아래층
cin >> belts[1][i].hp;
belts[1][i].isOn = false;
}
int cnt = 0;
while(countzero() < k){ // 내구도가 0인 칸 개수가 k 미만
rotatebelt(); // 벨트 회전
moverobot(); // 로봇 이동
addrobot(); // 로봇 추가
cnt++;
}
cout << cnt;
return 0;
}
교훈
- 구현은 항상 침착하게, 조건을 빼먹지 말고 잘 정리한 후 시작하도록 하자.
