2021. 2. 11. 11:57ㆍCODING
문제
(링크)14891번: 톱니바퀴 (acmicpc.net)
사고과정
톱니바퀴를 돌리는데 서로 마주보고 있는 톱니의 상태에 따라 같이 돌아가느냐와 돌아가지 않느냐가 문제이다. 처음엔 index를 줄이고 늘여가며 비교를 하려고 했다. a번 톱니의 2번 톱니는 시계방향으로 돌아가면 3번이 되기 때문에, 비교index를 1줄여주는 방식이다. 하지만 마지막에 결국 12시 방향의 톱니 상태를 알아야 하고, 위와 같은 방식으로 하려면 변수를 6개 지정해야 해서 헷갈릴 것 같았다. 그래서 그냥 톱니상태를 저장해둔 배열을 회전 여부에 따라 shifting을 하기로 했다.
각 명령의 톱니 번호와 회전 방향을 저장한다 -> 양옆으로 맞닿아 있는 톱니의 상태를 보고 각 톱니의 회전 방향을 정한다 -> 회전 시킨다 -> 회전방향을 저장한 배열을 초기화한다. -> (명령이 끝날 때까지 반복) -> 점수를 구한다.
내코드
#include <stdio.h>
#define N 0
#define S 1
#define CLOCK 1
#define CLOCK_OPPO -1
#define STOP 0
typedef struct {
int num, dir;
}command;
int CogWheel[4][8];
int direction[4];
command C[100];
void MoveWheel(int Wheel[][8], int* dir) {
for (int n = 0; n < 4; n++) {
if (dir[n] == CLOCK) {
int tmp = Wheel[n][7];
for (int i = 7; i > 0; i--) {
Wheel[n][i] = Wheel[n][i - 1];
}
Wheel[n][0] = tmp;
}
else if (dir[n] == CLOCK_OPPO) {
int tmp = Wheel[n][0];
for (int i = 0; i < 7; i++) {
Wheel[n][i] = Wheel[n][i + 1];
}
Wheel[n][7] = tmp;
}
else continue;
}
return;
}
int getPoint(int Wheel[][8]) {
int sum = 0;
for (int i = 0; i < 4; i++) {
if (Wheel[i][0] == N)continue;
else {
switch (i) {
case(0):
sum += 1;
break;
case(1):
sum += 2;
break;
case(2):
sum += 4;
break;
case(3):
sum += 8;
break;
}
}
}
return sum;
}
void getDir(int Wheel[][8], int* dir,int init_num) {
int i = init_num;
while (i < 3) { //check right
if (dir[i] != STOP) {
if (Wheel[i][2] == Wheel[i + 1][6]) {
dir[i + 1] = STOP;
}
else {
dir[i + 1] = -dir[i];
}
i++;
}
else break;
}
i = init_num;
while (i > 0) {//check left
if (dir[i] != STOP) {
if (Wheel[i][6] == Wheel[i - 1][2]) {
dir[i - 1] = STOP;
}
else {
dir[i - 1] = -dir[i];
}
i--;
}
else break;
}
}
void clear(int* dir) {
for (int i = 0; i < 4; i++) {
dir[i] = 0;
}
}
int main() {
int i, j, K;
for (i = 0; i < 4; i++) {
for (j = 0; j < 8; j++) {
scanf("%1d", &CogWheel[i][j]);
}
}
scanf("%d", &K);
for (i = 0; i < K; i++) {
scanf("%d %d", &C[i].num, &C[i].dir);
C[i].num -= 1;
}
for (i = 0; i < K; i++) {
direction[C[i].num] = C[i].dir;
getDir(CogWheel, direction, C[i].num);
MoveWheel(CogWheel, direction);
clear(direction);
}
int answer = getPoint(CogWheel);
printf("%d", answer);
return 0;
}
먼저 Command C는 명령들을 저장한 구조체 배열이다. 2중 배열을 사용할까 하다가 이름으로 지정해주는게 나을 것 같았다. 이후 입력을 해당 배열에 저장한다. 입력받는중 <C[i].num -=1>을 한 이유는 톱니의 이름와 index의 차이를 맞춰주기 위함이다. 다음은 위에서 설명한 사고과정에서와 같다. 명령에서 제시한 톱니번호와 방향을 direction배열에 저장한다. 이후 getDir을 이용해 양옆으로 방향을 갱신한다. 이후 MoveWheel을 이용해 앞에서 구한 회전방향대로 기존 CogWheel배열을 업데이트한다. direction배열을 stop상태로 초기화시켜 다음 과정에서 의도하지 않은 회전을 방지한다. 이 과정을 반복한 뒤 각 톱니의 12시방향을 조사하여 답을 구한다.
피드백
문제의 길이에 비해 간단하게 풀 수 있었다. 항상 다른 사람들과 4kB차이가 나는데 어디서 메모리 차이가 나는 것일까.
'CODING' 카테고리의 다른 글
백준 알고리즘 15684_사다리 조작 c (0) | 2021.02.17 |
---|---|
백준 알고리즘 15683_감시 c++ (0) | 2021.02.15 |
백준 알고리즘 14889_스타트와 링크 C++ (0) | 2021.02.10 |
백준 알고리즘 14890_경사로 C (0) | 2021.02.09 |
백준 알고리즘 14888_ 연산자 끼워넣기 C (0) | 2021.02.07 |