6.8 문제: 시계 맞추기 (문제 ID: CLOCKSYNC, 난이도: 중)

★★★★★다시 풀어볼 문제★★★★★

알고리즘 문제해결 전략 1권

6.8 문제: 시계 맞추기 (문제 ID: CLOCKSYNC, 난이도: 중)

문제를 제대로 읽지 못해서 풀지 못한 케이스.

처음에는 단순히 0번 부터 9번까지 스위치를 킬것인지 말것인지 로 풀었다가

다시 읽어서 여러번 스위치를 켤 수 있지만 10번만 누르는 것인 줄 스스로 착각한 문제.

그러다보니 기저 조건 등을 틀리게 작성해버렸다.

그리고 다시 짤때도 스위치를 누르지 않는다/ 스위치를 1~3번 누른다로 나누어서 생각하는 바람에

한참을 고민했었다. 하지만 스위치를 0~3번 누른다로 생각을 바꿔서 푸니까 쉽게 풀렸다.

문제를 잘 읽는게 정말 중요하다는 것을 느꼈다.

시간 초과 코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int clck[16];
int button[10][5] = {
    {0,1,2,-1,-1},{3,7,9,11,-1},{4,10,14,15,-1},{0,4,5,6,7},{6,7,8,10,12},{0,2,14,15,-1},{3,14,15,-1,-1},{4,5,7,14,15},{1,2,3,4,5},{3,4,5,9,13}    //연결된 스위치
    };
int ans;
 
void push(int n)
{
    bool finished = true;
 
    for (int i = 0; i < 16; i++)
    {
        if (clck[i] % 12 != 0)                //모두 12시인지 확인
        {
            finished = false;
            break;
        }
    }
 
    if (finished)
    {
        ans = min(ans, n);
        return;
    }
 
    if (!finished && n >= 10)                //안 끝났는데 버튼을 10개 다 누른경우
    {
        return;
    }
 
    if (ans <= n)                            //이미 최소값을 넘은 경우
    {
        return;
    }
 
    for (int i = 0; i < 10; i++)            //10가지 버튼 누르기
    {
        for (int j = 0; j < 5; j++)
        {
            if (button[i][j] != -1)
            {
                clck[button[i][j]] += 3;
            }
        }
        push(n + 1);
 
        for (int j = 0; j < 5; j++)
        {
            if (button[i][j] != -1)
            {
                clck[button[i][j]] -= 3;
            }
        }
    }
 
    return;
}
int main()
{
    //freopen("input.txt", "r", stdin);
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        ans = 987654321;
 
        for (int i = 0; i < 16; i++)
        {
            cin >> clck[i];
        }
 
        push(0);
 
        if (ans == 987654321)                    //답이 존재하지 않는 경우
        {
            ans = -1;
        }
 
        cout << ans << endl;
    }
 
    return 0;
}

정답

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int clck[16];
int button[10][5] = {
    {0,1,2,-1,-1},{3,7,9,11,-1},{4,10,14,15,-1},{0,4,5,6,7},{6,7,8,10,12},{0,2,14,15,-1},{3,14,15,-1,-1},{4,5,7,14,15},{1,2,3,4,5},{3,4,5,9,13}    //연결된 스위치
    };
int ans;
 
void push(int n ,int cnt)
{
    bool finished = true;
 
    for (int i = 0; i < 16; i++)
    {
        if (clck[i] % 12 != 0)                //모두 12시인지 확인
        {
            finished = false;
            break;
        }
    }
 
    if (finished)
    {
        ans = min(ans, cnt);                    //정답과 횟수 비교
        return;
    }
 
    if (ans <= cnt) //이미 최소값을 넘은 경우
    {
        return;
    }
 
    if (!finished && n==10)       //끝나지 않았지만 마지막 스위치까지 다 누른경우                   
    {
        return;
    }
 
    for (int i = 0; i < 4; i++)            //버튼을 몇번 누를것인지?    4번 이상 누를수 없게
    {
        for (int j = 0; j < 5; j++)
        {
            if (button[n][j] != -1)
            {
                clck[button[n][j]] += 3*i;        //시계 값들을 변경
            }
        }
 
        push(n + 1,cnt + i);                    //다음 스위치로 넘겨주고, 누른 횟수 넘겨주기
 
        for (int j = 0; j < 5; j++)
        {
            if (button[n][j] != -1)
            {
                clck[button[n][j]] -= 3*i;
            }
        }
 
    }
 
    return;
}
int main()
{
    //freopen("input.txt", "r", stdin);
    int tc;
    cin >> tc;
 
    for (int t = 1; t <= tc; t++)
    {
        ans = 987654321;
 
        for (int i = 0; i < 16; i++)
        {
            cin >> clck[i];
        }
 
        push(0,0);
 
        if (ans == 987654321)                    //답이 존재하지 않는 경우
        {
            ans = -1;
        }
 
        cout << ans << endl;
    }
 
    return 0;
}