백준 14891번 톱니바퀴 문제는 삼성 SW 역량테스트 기출문제이며 시뮬레이션 유형입니다. 안타깝게도 시뮬레이션은 별도의 틀이 존재하지는 않습니다. 문제를 제대로 이해하고 각 프로세스를 만들어 구현할 수밖에 없습니다. 요구사항 구현 능력은 다양한 연습을 통해 사고력을 키울 수밖에 없습니다.
2021.04.16 - [알고리즘/SW역량테스트 기출문제] - [백준 14503번] 로봇 청소기 (시뮬레이션)
2021.04.16 - [알고리즘/SW역량테스트 기출문제] - [백준 15685번] 드래곤 커브 (시뮬레이션)
2021.04.17 - [알고리즘/SW역량테스트 기출문제] - [백준 14891번] 톱니바퀴 (시뮬레이션)
안녕하세요. 지칸입니다.
본 포스팅 문제는 톱니바퀴 백준 14891번으로 시뮬레이션 유형입니다. 역량테스트를 진행해보면 보통 2문제 모두 알고리즘 유형 혹은 1문제 알고리즘, 1문제 시뮬레이션 이런 식으로 문제 유형이 분배됩니다. 일반적으로 알고리즘 문제는 풀이의 틀이 정해져 있기 때문에 상대적으로 난이도가 쉽습니다. 시뮬레이션보다는 알고리즘 문제를 먼저 풀이하는 것이 좋은 접근 방법이라 생각합니다.
1) 문제 이해
2) 문제 풀이
저의 결론) 시뮬레이션 문제는 다양한 문제를 풀어가며 사고력을 키우는 방법밖에 없습니다.. 이 문제는 한 톱니바퀴의 회전을 구현하고, 특정 톱니바퀴 기준으로 왼쪽, 오른쪽 회전 확산에 대해 구현하면 됩니다.
1) 문제 이해
문제 출처 : www.acmicpc.net/problem/14891
문제)
총 8개의 톱니를 가지고 있는 톱니바퀴 4개가 아래 그림과 같이 일렬로 놓여 있다. 또, 톱니는 N극 또는 S극 중 하나를 나타내고 있다. 톱니바퀴에는 번호가 매겨져 있는데, 가장 왼쪽 톱니바퀴가 1번, 그 오른쪽은 2번, 그 오른쪽은 3번, 가장 오른쪽 톱니바퀴는 4번이다.
이때, 톱니바퀴를 총 K번 회전시키려고 한다. 톱니바퀴의 회전은 한 칸을 기준으로 한다. 회전은 시계 방향과 반시계 방향이 있고, 아래 그림과 같이 회전한다.
톱니바퀴를 회전시키려면, 회전시킬 톱니바퀴와 회전시킬 방향을 결정해야 한다. 톱니바퀴가 회전할 때, 서로 맞닿은 극에 따라서 옆에 있는 톱니바퀴를 회전시킬 수도 있고, 회전시키지 않을 수도 있다. 톱니바퀴 A를 회전할 때, 그 옆에 있는 톱니바퀴 B와 서로 맞닿은 톱니의 극이 다르다면, B는 A가 회전한 방향과 반대방향으로 회전하게 된다. 예를 들어, 아래와 같은 경우를 살펴보자.
두 톱니바퀴의 맞닿은 부분은 초록색 점선으로 묶여있는 부분이다. 여기서, 3번 톱니바퀴를 반시계 방향으로 회전했다면, 4번 톱니바퀴는 시계 방향으로 회전하게 된다. 2번 톱니바퀴는 맞닿은 부분이 S극으로 서로 같기 때문에, 회전하지 않게 되고, 1번 톱니바퀴는 2번이 회전하지 않았기 때문에, 회전하지 않게 된다. 따라서, 아래 그림과 같은 모양을 만들게 된다.
위와 같은 상태에서 1번 톱니바퀴를 시계 방향으로 회전시키면, 2번 톱니바퀴가 반시계 방향으로 회전하게 되고, 2번이 회전하기 때문에, 3번도 동시에 시계 방향으로 회전하게 된다. 4번은 3번이 회전하지만, 맞닿은 극이 같기 때문에 회전하지 않는다. 따라서, 아래와 같은 상태가 된다.
톱니바퀴의 초기 상태와 톱니바퀴를 회전시킨 방법이 주어졌을 때, 최종 톱니바퀴의 상태를 구하는 프로그램을 작성하시오.
(그림은 생략했습니다. 문제 출처에 가서 확인 바랍니다..)
-> 문제 해석
- 톱니바퀴 4개, 각 톱니바퀴는 8개의 톱니 가짐
- 맞닿은 톱니는 2번째 6번째로 정해져 있음
- 회전하기 이전에 이미 같은 극인지 아닌지로 회전 가능 여부를 체크할 수 있음
- 회전하고자 하는 톱니바퀴 기준으로 왼쪽, 오른쪽 두 방향으로 톱니바퀴 회전 체크
- 이웃한 톱니바퀴끼리 반대 방향
입력)
첫째 줄에 1번 톱니바퀴의 상태, 둘째 줄에 2번 톱니바퀴의 상태, 셋째 줄에 3번 톱니바퀴의 상태, 넷째 줄에 4번 톱니바퀴의 상태가 주어진다. 상태는 8개의 정수로 이루어져 있고, 12시 방향부터 시계방향 순서대로 주어진다. N극은 0, S극은 1로 나타나 있다.
다섯째 줄에는 회전 횟수 K(1 ≤ K ≤ 100)가 주어진다. 다음 K개 줄에는 회전시킨 방법이 순서대로 주어진다. 각 방법은 두 개의 정수로 이루어져 있고, 첫 번째 정수는 회전시킨 톱니바퀴의 번호, 두 번째 정수는 방향이다. 방향이 1인 경우는 시계 방향이고, -1인 경우는 반시계 방향이다.
-> 입력 해석
- 배열을 사용할 것이기 때문에 톱니바퀴의 번호를 0부터 시작
- 각 회전 k마다 톱니바퀴 회전하고 다음 k+1로 넘어가도 상관없음(K개 모아서 해도 됨)
- 시계, 반시계 관계가 1, -1 이기 때문에 반대 방향으로 바꾸는 작업이 -1을 곱하면 간단해짐
출력)
총 K번 회전시킨 이후에 네 톱니바퀴의 점수의 합을 출력한다. 점수란 다음과 같이 계산한다.
- 1번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 1점
- 2번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 2점
- 3번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 4점
- 4번 톱니바퀴의 12시방향이 N극이면 0점, S극이면 8점
-> 출력 해석
- 각 톱니바퀴가 0번째 인덱스 확인
- 1,2,4,8 이면 (1<< shift)를 통해 구현 가능
2) 문제 풀이
기본 세팅은 시험 시작하자마자 진행해줍니다.
2019.04.25 - [알고리즘/SW역량테스트] - (1장-1) 역량 테스트 기본 템플릿 준비
2-1) 초기 세팅
input를 받는 부분을 구현해줍니다. 우리는 gear라는 2차원 배열을 사용할 예정입니다. vector를 쓸지 일반 배열을 쓸지는 크게 상관없습니다. 저는 vector 쓰는 게 편해서 대부분 vector를 사용하여 문제를 풀고 있습니다.
#include <iostream>
#include <vector>
using namespace std;
#define MAX_GEAR 4
#define MAX_TOOTH 8
enum NS
{
N = 0,
S
};
enum Spindir
{
Anticlockwise = -1,
Clockwise = 1
};
vector<NS> gear[MAX_GEAR]; // 각 톱니의 상태
int sol = 0;
int main() {
char temp;
for (int i = 0; i < MAX_GEAR; i++) {
for (int j = 0; j < MAX_TOOTH; j++) {
cin >> temp; //빈칸없는 입력이기 때문에 char로 받음
if (temp == '0') {
gear[i].push_back(N);
}
else {
gear[i].push_back(S);
}
}
}
int K;
int spinNum, spindir;
cin >> K;
for (int i = 0; i < K; i++) {
cin >> spinNum >> spindir;
// 톱니바퀴 회전시키기
}
// 각 톱니바퀴 0번째 톱니 체크
cout << sol;
return 0;
}input을 보면 톱니의 상태가 빈칸 없이 8자리가 들어오기 때문에 아래 포스팅에서 설명했던 것처럼 char형으로 받아야 합니다. 하나씩 하나씩 8번 반복해서 문자로 받아서 '0'이면 N극, 아니면 S극으로 각 톱니바퀴에 넣어줍니다.
2021.03.09 - [알고리즘/SW역량테스트] - (1장-2) 변수의 크기와 입력 받는 법
모든 톱니바퀴의 상태를 입력하고 K개의 회전 변수들을 입력받으면 됩니다.
2-2) 톱니바퀴 회전하기
우리는 하나의 톱니바퀴를 시계방향 혹은 반시계 방향으로 회전시키는 동작을 구현해야 합니다. 아래 spin 함수가 그 내용을 담고 있습니다. 회전 방향에 신경쓰지 않기 위해 -1, 1 값인 걸 이용하여 통합하여 구현했습니다. 아래 함수에 대해 이해가 어렵다면 반시계방향일 때, 시계방향일 때 조건문으로 분기해서 노가다로 배열을 바꿔도 상관없습니다.
void spin(int gearnum, Spindir dir) {
vector<NS> geartemp;
for (int i = 0; i < MAX_TOOTH; i++) {
if ((i - dir) == -1) {
geartemp.push_back(gear[gearnum][MAX_TOOTH - 1]);
}
else if((i - dir) == MAX_TOOTH) {
geartemp.push_back(gear[gearnum][0]);
}
else {
geartemp.push_back(gear[gearnum][i - dir]);
}
}
gear[gearnum] = geartemp;
}예를 들면, 반시계 방향인지 if 조건문으로 확인 후 아래처럼 코딩합니다. 보시는 것처럼 스마트해 보이진 않지만 결과는 똑같습니다. 빠르게 코딩하는 방법으로는 이런 노가다 방식이 좋고 명확합니다. 단, 문제의 input이 변해도 동작이 변하지 않아야 합니다. 본 문제에서는 항상 톱니바퀴 4개와 8개의 톱니, 시계방향, 반시계방향으로 변수가 고정되어 있기 때문에 가능합니다.
geartemp[0] = gear[gearnum][1];
geartemp[1] = gear[gearnum][2];
geartemp[2] = gear[gearnum][3];
geartemp[3] = gear[gearnum][4];
geartemp[4] = gear[gearnum][5];
geartemp[5] = gear[gearnum][6];
geartemp[6] = gear[gearnum][7];
geartemp[7] = gear[gearnum][0];
gear[gearnum] = geartemp;
2-3) 모든 톱니바퀴 확인하기
K번 반복해야 하는 전체 톱니바퀴 회전 함수를 구현해보면 아래와 같습니다. 문제에서 분석한 것처럼 톱니바퀴 상태가 주어졌을 때, 각 톱니바퀴의 2,6번째 톱니를 알고 있어 같은 극인지 아닌지를 바로 알 수 있습니다. 가장 먼저 이 내용을 neighbortooth배열에 저장하고 있습니다. 같은 극이면 nochange, 다른 극이면 change 값을 넣어줍니다.
enum State
{
nochange,
change
};
State neighbortooth[MAX_GEAR - 1]; // 맞닿은 톱니의 변화
void spingear(int spinNum, Spindir spindir) {
for (int i = 0; i < MAX_GEAR - 1; i++) {
if (gear[i][2] == gear[i + 1][6]) {
neighbortooth[i] = nochange;
}
else {
neighbortooth[i] = change;
}
}
//본인
spin(spinNum, spindir);
//왼쪽 방향
Spindir tempdir = spindir;
for (int i = spinNum; i > 0; i--) {
if (neighbortooth[i - 1] == nochange) break;
tempdir = (Spindir)(-tempdir);
spin(i - 1, tempdir);
}
//오른쪽 방향
tempdir = spindir;
for (int i = spinNum; i < MAX_GEAR - 1; i++) {
if (neighbortooth[i] == nochange) break;
tempdir = (Spindir)(-tempdir);
spin(i + 1, tempdir);
}
}
int main() {
//.. 기존 코드 생략 ..
for (int i = 0; i < K; i++) {
cin >> spinNum >> spindir;
spingear(spinNum - 1,(Spindir) spindir);
}
//.. 기존 코드 생략 ..
return 0;
}총 3구역으로 나눠서 생각해 볼 수 있습니다. spinNum인 본인 자신의 톱니바퀴 회전, 본인 기준 왼쪽 톱니바퀴들의 회전, 본인 기준 오른쪽 톱니바퀴들의 회전입니다. neighbortooth와 gear의 인덱스에 주의하시기 바랍니다. neighbortooth[1]은 gear[1], gear[2] 사이를 의미합니다. 왼쪽, 오른쪽 방향의 경우, nochange를 만나면 더 진행하지 않고 반복문을 빠져나오면 됩니다.
tempdir 변수에 계속 회전 방향을 반대로 넣으면서 업데이트하고 있습니다. 단순히 -1을 곱해서 구현하고 있습니다.
2-4) 각 톱니바퀴의 12시 톱니 확인하기
K번 톱니바퀴를 회전시킨 후 calculation함수에서 각 톱니바퀴의 12시 톱니를 확인하는 과정을 구현합니다.
void calculation() {
sol = 0;
for (int i = 0; i < MAX_GEAR; i++) {
if (gear[i][0] == S) {
sol += (1<<i);
}
}
}톱니바퀴 인덱스와 점수의 관계를 쉬프트 연산자를 통해 코딩하였습니다. 쉬프트 연산의 결과는 아래와 같습니다.
- gear 0번째, 1<<0 , 0001 = 1
- gear 1번째, 1<<1 , 0010 = 2
- gear 2번째, 1<<2 , 0100 = 4
- gear 3번째, 1<<3 , 1000 = 8
마찬가지로, 쉬프트 연산 없이 노가다로 더해줘도 상관없습니다.
'알고리즘 > SW역량테스트 기출문제' 카테고리의 다른 글
| [백준 14501번] 퇴사 (조합) (0) | 2021.04.20 |
|---|---|
| [백준 15683번] 감시 (조합) (0) | 2021.04.18 |
| [백준 15685번] 드래곤 커브 (시뮬레이션) (0) | 2021.04.16 |
| [백준 14888번] 연산자 끼워넣기 (순열) (0) | 2021.04.16 |
| [백준 14503번] 로봇 청소기 (시뮬레이션) (0) | 2021.04.16 |
댓글