c++) 6장 - 시계 맞추기

algospot.com :: CLOCKSYNC 알고스팟 문제입니다.

그림과 같이 4 x 4 개의 격자 형태로 배치된 16개의 시계가 있다. 이 시계들은 모두 12시, 3시, 6시,

혹은 9시를 가리키고 있다. 이 시계들이 모두 12시를 가리키도록 바꾸고 싶다.

시계의 시간을 조작하는 유일한 방법은 모두 10개 있는 스위치들을 조작하는 것으로,

각 스위치들은 모두 적게는 3개에서 많게는 5개의 시계에 연결되어 있다.

한 스위치를 누를 때마다, 해당 스위치와 연결된 시계들의 시간은 3시간씩 앞으로 움직인다.

스위치들과 그들이 연결된 시계들의 목록은 다음과 같다.

시계들은 맨 윗줄부터, 왼쪽에서 오른쪽으로 순서대로 번호가 매겨졌다고 가정하자.

시계들이 현재 가리키는 시간들이 주어졌을 때, 모든 시계를 12시로 돌리기 위해 최소한 눌러야 할

스위치의 수를 계산하는 프로그램을 작성하시오.

입력

첫 줄에 테스트 케이스의 개수 C (<= 30) 가 주어진다.
각 테스트 케이스는 한 줄에 16개의 정수로 주어지며, 각 정수는 0번부터 15번까지 각 시계가 가리키고 있는 시간을 12, 3, 6, 9 중 하나로 표현한다.

출력

각 테스트 케이스당 한 줄을 출력한다. 시계들을 모두 12시로 돌려놓기 위해 눌러야 할 스위치의 최소 수를 출력한다. 만약 이것이 불가능할 경우 -1 을 출력한다.

 

---

• 주의할 점

1) 모든 조합의 수를 따지려고 한다면 무한하기 때문에 풀 수 없다.

2) 스위치를 누를 때마다 3시간씩 증가한다. => 네 번 누르면 누르지 않은 것과 같기 때문에 최대 3번까지만 누른다.

#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
using namespace std;
#define INF 98765432
int C;
char connection[10][17] = {
    "oooxxxxxxxxxxxxx",
    "xxxoxxxoxoxoxxxx",
    "xxxxoxxxxxoxxxoo",
    "oxxxooooxxxxxxxx",
    "xxxxxxoooxoxoxxx",
    "oxoxxxxxxxxxxxoo",
    "xxxoxxxxxxxxxxoo",
    "xxxxooxoxxxxxxoo",
    "xoooooxxxxxxxxxx",
    "xxxoooxxxoxxxoxx"
};

bool allClear(vector < int > &clocks) {
    bool ok = true;
    for(int i=0; i<16; i++) {
        if(clocks[i] != 12) {
            ok = false;
            break;
        }
    }
    return ok;
}

void clickSwtch(vector < int > &clocks, int swtch) {
    for(int i=0; i<16; i++) {
        if(connection[swtch][i] == 'o') {
            if((clocks[i] += 3) > 12) clocks[i] = 3;
        }
    }
}

int solution(vector < int > &clocks, int swtch) {
    // 마지막 스위치까지 도달했을 시
    if(swtch == 10) return allClear(clocks) ? 0 : INF;

    int ret = INF;
    // 각 스위치를 0번 눌렀을 경우 ~ 3번 눌렀을 경우를 생각해본다.
    // 마지막에 4번째로 눌리기 때문에 초기화된다.
    for(int i=0; i<4; i++) {
        int tmp = i + solution(clocks,swtch+1);
        ret = min(ret,tmp);
        clickSwtch(clocks,swtch);
    }
    return ret;
}

int main() {
    scanf("%d",&C);
    int num;
    for(int tc=0; tc<C; tc++) {
        vector <int> clocks;
        for(int i=0; i<16; i++) {
            scanf("%d",&num);
            clocks.push_back(num);
        }
        int result = solution(clocks,0);
        (result == INF) ? printf("-1\n") : printf("%d\n",result);
    }
}