[C] 백준 20055번 컨베이어 벨트 위의 로봇
안녕하세요 ! ლ(╹◡╹ლ)
요즘 출근에, 밀린 수업에, 동아리 교육에 정말 정신이 없네요 (심한 욕)
지난 날의 제 선택을 후회하는 휴일을 보내고 있습니다..^^
그런 의미에서(?) 오늘 백준 삼성 SW 역량 테스트 기출문제를 풀어보았습니다.
난이도가 낮은 문제부터 풀고 있는데, 드디어 (solved.ac 기준) 실버 영역을 다 풀었답니다!
짝짝 👏👏
20055번: 컨베이어 벨트 위의 로봇
길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부
www.acmicpc.net
오늘 문제는 그림으로 주어진 상황을 실제로 구현하는 시뮬레이션 문제입니다!
사실 저는 이런 그림과 부가 설명이 구구절절한 문제를 굉장히 싫어한답니다 ..
우선 그림이 있으면 뭔가 문제 읽기가 싫어지기도 하고,
문제를 완전히 이해하는 데 시간이 좀 걸리는 것 같습니다.ㅎㅎ
저는 이번 문제는 설명에 제시되어 있는 로봇 옮기는 순서에 따라 구현해보았습니다. (각 단계별로 함수를 구현하였습니다.)
1. 벨트가 한 칸 회전한다.
rotate 함수
우선 벨트가 한 칸 이동하는 과정에 대해 생각해보았습니다.
벨트는 1부터 2N번까지의 칸이 존재하고 한 번에 시계 방향으로 한 칸씩 이동하는 것을 알 수 있습니다.
하지만 입력값으로 들어오는 배열은 1차원 배열이기 때문에
벨트가 한 칸씩 회전할 때 1차원 배열 상으로는 어떠한 변화가 생기는지 먼저 확인해보았습니다.
위의 사진을 살펴보면 벨트가 한 칸씩 회전할 때마다 1차원 배열이 오른쪽으로 한 칸씩 이동한다는 것을 알 수 있습니다.
제일 큰 index의 값은 배열의 첫 번째 index로 오게 되겠죠.
따라서 벨트를 회전하는 함수에서는 입력으로 받아온 1차원 배열 (각 칸의 내구도)을 한 칸씩 이동시켜주었습니다.
참고로 저는 이때 durability라는 이름의 1차원 배열을 사용하였습니다.
2. 가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 가만히 있는다.
+) 로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 한다.
rotate 함수
다음 단계에서는 로봇을 이동시킬 수 있다면 한 칸씩 시계 방향으로 이동시키는 과정입니다.
이때 고려해야 할 사항은
1. 가장 먼저 벨트에 올라간 로봇부터 체크
2. 이때 N번째 칸(내려가는 위치)에 있는 로봇은 땅으로 내려줘야 함 (★)
3. 다음 칸에 로봇이 없어야 함
4. 다음 칸에 내구도가 1 이상이어야 함
입니다.
저는 로봇이 해당 칸에 있는지를 체크해주기 위해 robot이라는 배열을 별도로 선언하였습니다.
해당 배열의 경우에는 벨트 위의 상황만 나타내면 되기 때문에 범위를 1부터 N까지로만 잡았습니다!
3. 올라가려는 위치에 로봇이 없다면 로봇을 하나 올린다.
putRobot 함수
해당 단계에서는 로봇이 1번째 칸에 있는지를 확인한 후, (robot 배열 사용)
로봇이 없다면 로봇을 올리고 내구도를 1 감소시켜줍니다.
4. 내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다.
check 함수
마지막으로 종료 조건을 탐색하는 단계입니다.
durability 배열의 값이 0인 경우를 count 한 후, 입력으로 받은 K보다 그 값이 크다면 벨트의 회전을 종료합니다.
그렇지 않다면 1번부터 다시 반복합니다.
문제에서 구하고자 하는 답은 진행되고 있었던 단계가 몇 단계인지이기 때문에
별도의 step이라는 변수를 사용하여 해당 과정의 반복 횟수를 count 해주었습니다.
아래는 위의 과정을 나타낸 최종적인 코드입니다.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
// 순서 1
void rotate(int N, int * durability, int *robot) {
int first = durability[2 * N];
for (int i = 2 * N - 1; i >= 1; i--)
durability[i + 1] = durability[i];
durability[1] = first;
for (int i = N - 1; i >= 1; i--)
robot[i + 1] = robot[i];
robot[1] = 0;
}
// 순서 2
void move(int N, int * durability, int *robot) {
// 로봇 땅으로 내리기
if (robot[N] == 1)
robot[N] = 0;
for (int i = N - 1; i >= 1; i--) {
if (robot[i] != 1)
continue;
// 순서 2-1의 조건
if (robot[i + 1] == 0 && durability[i + 1] != 0) {
robot[i + 1] = 1;
durability[i + 1]--;
robot[i] = 0;
}
}
}
// 순서 3
void putRobot(int* durability, int* robot) {
if (robot[1] == 0 && durability[1] != 0) {
robot[1] = 1;
durability[1]--;
}
}
// 순서 4
int check(int N, int * durability) {
int cnt = 0;
for (int i = 1; i <= N * 2; i++)
if (durability[i]==0)
cnt++;
return cnt;
}
int main()
{
int N, K;
scanf("%d%d", &N, &K);
int* durability = (int*)malloc(sizeof(int) * (2 * N + 1));
int* robot = (int*)malloc(sizeof(int) * (N + 1));
for (int i = 1; i <= N; i++)
robot[i] = 0;
for (int i = 1; i <= 2 * N; i++) {
scanf("%d", &durability[i]);
}
int step = 0;
while (1) {
step++;
rotate(N, durability, robot);
move(N, durability, robot);
putRobot(durability, robot);
if (check(N, durability) >= K)
break;
}
printf("%d\n", step);
free(durability);
free(robot);
return 0;
}
해당 문제는 주어진 그림과 부가적인 설명을 제대로 읽는다면 쉽게 풀 수 있는 문제였습니다!
저는 문제를 설렁설렁 읽는 바람에,, 잘못 이해한 부분을 알아내느라 시간이 좀 걸렸답니다.ㅎ
그래도 오랜만에 나름 재밌는 문제를 풀었던 것 같습니다.