[백준] 14891번 : 톱니바퀴

문제

 

---

풀이

 

원래는 그냥 단순 구현이라 이 문제에 대한 풀이를 쓸 생각이 없었는데...

맞고 나서 다른 사람들은 어떻게 했을까 싶어 블로그들을 보니 뭐 덱을 쓰기도 하고 이상한 복잡한 무언갈 하기도 하고 뭔가 나랑 비슷한건 없어보였다.

구현이 워낙 그냥 조건대로 돌아가기만 하면 그만인 문제라 그런걸지도 모르겠다.

아무튼 그래서 나의 풀이를 적어보겠다.

 

톱니바퀴는 동시에 돌아가니까 회전하게 될 톱니바퀴를 먼저 다 체크하고 한번에 회전해야 한다.

그리고 회전하게 될 톱니바퀴는 연속일 것이다.

 

회전시킬 톱니바퀴를 기준으로 왼쪽과 오른쪽을 따로 살펴보며 처음으로 돌아가게 될 톱니바퀴와 마지막으로 돌아가게 될 톱니바퀴를 확인한다.

 

만약 2번 톱니바퀴를 시계방향으로 돌렸는데 1번 톱니바퀴부터 돌아가기 시작한다면 시계 반대방향으로 시작해야 한다. 그래서 2번 톱니바퀴가 시계방향으로 돌아가기 때문이다.

 

말로 설명하면 와닿지 않을 수도 있는데 예제를 직접 머릿속으로 생각해보면 이해될 것이다.

---

소스코드

 

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<string> gear(4);

void moveGear(int idx, int dir) {
    string tmp;
    switch (dir) {
        case -1: //시계 반대방향
            tmp = gear[idx].substr(1, 7);
            tmp += gear[idx][0];
            break;
        case 1: //시계 방향
            tmp = gear[idx].substr(0, 7);
            tmp = gear[idx][7] + tmp;
            break;
    }
    gear[idx] = tmp;
}

int calcScore() { //점수 계산
    int score = 0, num = 1;
    for (int i = 0; i < 4; i++) {
        score += (gear[i][0] == '0') ? 0 : num;
        num *= 2;
    }
    return score;
}

int main() {
    int K, num, dir;

    for (int i = 0; i < 4; i++)
        cin >> gear[i];
    cin >> K;
    while (K--) {
        cin >> num >> dir;
        num--; //인덱스 조정
        int start = num, end = num; //바뀌기 시작하는 톱니바퀴, 마지막으로 바뀌는 톱니바퀴

        for (int i = num - 1; i >= 0; i--) { //왼쪽 톱니바퀴 확인
            if (gear[i][2] == gear[i + 1][6])
                break;
            start = i;
        }
        for (int i = num + 1; i < 4; i++) { //오른쪽 톱니바퀴 확인
            if (gear[i][6] == gear[i - 1][2])
                break;
            end = i;
        }
        if (start % 2 != num % 2) //시작 방향 조절
            dir *= -1;
        for (int i = start; i <= end; i++) { //톱니 회전
            moveGear(i, dir);
            dir *= -1;
        }
    }
    cout << calcScore(); //점수 계산
}

전체 소스코드다.

 

vector<string> gear(4);

각 톱니바퀴의 상태는 string으로 저장한다.

 

    while (K--) {
        cin >> num >> dir;
        num--; //인덱스 조정
        int start = num, end = num; //바뀌기 시작하는 톱니바퀴, 마지막으로 바뀌는 톱니바퀴

        for (int i = num - 1; i >= 0; i--) { //왼쪽 톱니바퀴 확인
            if (gear[i][2] == gear[i + 1][6])
                break;
            start = i;
        }
        for (int i = num + 1; i < 4; i++) { //오른쪽 톱니바퀴 확인
            if (gear[i][6] == gear[i - 1][2])
                break;
            end = i;
        }
        if (start % 2 != num % 2) //시작 방향 조절
            dir *= -1;
        for (int i = start; i <= end; i++) { //톱니 회전
            moveGear(i, dir);
            dir *= -1;
        }
    }

while문은 회전하게될 톱니바퀴를 찾는 과정과 톱니바퀴를 회전하는 과정으로 나뉜다.

 

        cin >> num >> dir;
        num--; //인덱스 조정
        int start = num, end = num; //바뀌기 시작하는 톱니바퀴, 마지막으로 바뀌는 톱니바퀴

        for (int i = num - 1; i >= 0; i--) { //왼쪽 톱니바퀴 확인
            if (gear[i][2] == gear[i + 1][6])
                break;
            start = i;
        }
        for (int i = num + 1; i < 4; i++) { //오른쪽 톱니바퀴 확인
            if (gear[i][6] == gear[i - 1][2])
                break;
            end = i;
        }

여기가 회전하게될 톱니바퀴를 찾는 부분이다.

먼저 num에서 1을 빼서 0부터 시작하는 인덱스로 만든다.

 

그리고 start는 처음으로 회전하는 톱니바퀴이고, end는 마지막으로 회전하는 톱니바퀴인데 둘다 num으로 초기화 한다.

num번째 톱니바퀴를 기준으로 왼쪽을 살펴보는데 두 톱니바퀴의 극이 같다면 break, 그렇지 않다면 start를 갱신한다.

그다음으론 오른쪽을 살펴보는데 아까처럼 두 톱니바퀴의 극이 같다면 break, 그렇지 않다면 end를 갱신한다.

 

        if (start % 2 != num % 2) //시작 방향 조절
            dir *= -1;
        for (int i = start; i <= end; i++) { //톱니 회전
            moveGear(i, dir);
            dir *= -1;
        }

start 톱니바퀴가 기존의 num 톱니바퀴보다 홀수개만큼 떨어져 있다면 처음의 회전 방향을 반대로 바꿔준다.

그리고 start 톱니바퀴를 시작으로 톱니바퀴들을 하나하나 회전해 준다. 회전할때마다 방향 바꾸는걸 잊으면 안된다.

 

void moveGear(int idx, int dir) {
    string tmp;
    switch (dir) {
        case -1: //시계 반대방향
            tmp = gear[idx].substr(1, 7);
            tmp += gear[idx][0];
            break;
        case 1: //시계 방향
            tmp = gear[idx].substr(0, 7);
            tmp = gear[idx][7] + tmp;
            break;
    }
    gear[idx] = tmp;
}

톱니바퀴를 회전하는 부분이다.

그냥 보면 알 것이다.

 

    cout << calcScore(); //점수 계산

이런식으로 K번의 회전횟수가 지나면 최종 점수를 계산한다.

 

int calcScore() { //점수 계산
    int score = 0, num = 1;
    for (int i = 0; i < 4; i++) {
        score += (gear[i][0] == '0') ? 0 : num;
        num *= 2;
    }
    return score;
}

i번째 톱니의 12시 방향은 gear[i][0]이니 그 곳의 값을 확인하며 점수를 갱신하면 된다.