[AOJ][C++] 시계 맞추기 - CLOCKSYNC

https://www.algospot.com/judge/problem/read/CLOCKSYNC

algospot.com :: CLOCKSYNC

이번 문제에서는 정말 중요한 것을 배웠다.

 

일단 문제를 봤을 때 풀이는 어렵지않게 떠올렸고 O(4^10)인 것 까지 금방 계산해서 완탐으로 풀 수 있겠다! 라고 생각했었다.

 

그렇게 구현이 다 끝났고 테스트 케이스도 다 맞았다. 

 

그런데 뭔가 이상했다...

 

2

12 6 6 6 6 6 12 12 12 12 12 12 12 12 12 12

12 9 3 12 6 6 9 3 12 9 12 9 12 12 6 6

 

이 기본 테스트 케이스를 넣었을 때 답은 나오는데 시간이 0.27s나 걸렸다.

 

테케가 30개까지 들어올 수 있으므로 저거만 넣어도 8s가 넘게 걸린다. 시간제한이 10s니깐 최악의 경우가 들어올 경우에는 TLE가 뜨게 된다.

 

머리로는 분명히 사소한거 최적화 안됐다고 0.27s가 나올 수가 없다는 걸 알았지만 정말 이유가 감이 안와서 진짜 사소한 것들 줄이면서 최적화를 해서 0.01s라도 줄여보려고 노력했다.

 

그렇게 의미없는 노력을 3일에 걸쳐서 문제를 풀며 했다.

 

3일차에 문제를 처음부터 아예 다시 풀던 중 불현듯 종만북에서 읽었던 '실수 연산의 어려움' 파트가 생각났다.

 

실수 연산이 어렵고 느리다라는 내용인데 나는 재귀함수에서 실수연산을 사용하는 코드가 딱 한줄있었다.

 

시계를 2차원 벡터에[4][4]크기로 넣어놨기 때문에 시계의 y좌표와 x좌표를 계산해주기 위해 넣었던 코드인데 설마 실수연산이 느려서 TLE나는건가....??? 라는 의심이 들었다.

 

코드는 다음과 같았다(bd배열에는 시계의 시간이 저장되어있고 swt배열에는 시계의 번호가 들어있다.)

y=(int)(swt[bt][i]/4);
x=swt[bt][i]-(y*4);
bd[y][x] += 3*time;

종만북에서 실수연산이 느리다고 했었는데 설마 이거 때문인가? 해서 벡터를 1차원으로 바꾸고 실수연산을 뺐더니 바로 AC..

 

부동소숫점 연산이 생각보다 엄청 많이 느리다는걸 종만북 읽을 때는

 

"아~ 느리구나~ 근데 솔직히 느려봤자 내 암산보다 느리겠어~" 했었는데 뚝배기가 깨지고서야 알았다.

 

실수연산은 왠만하면 재귀나 반복문에서는 사용하지말자.

 

내가 구현력이 좋지는 않아도 완탐 재귀함수 하나는 짤 수 있다고 생각했었는데 종만북을 본뒤로 정말 그냥 짜기만 하는 수준이라는 것을 늘 느낀다. 나도 언젠간 간결한 코드를 짤 수 있으면 좋겠다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;
int swt[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 now_pushed[10]={0,};

bool is_all_12clock(vector<int>& bd)
{
    bool ok=true;

    for(int i=0;i<16;i++)
    {
        if(bd[i]%12 != 0)
        {
            ok=false;
            break;
        }
    }

    return ok;
}

void plus_time(vector<int>& bd, int bt, int time)
{
    for(int i=0;i<5;i++)
    {
        if(swt[bt][i]!=-1)
        {
            bd[swt[bt][i]] += 3*time;
        }
        else
            break;
    }
    return;
}

int solve(vector<int> bd, int now, int pushed, int nowret)
{
    int ret=987654321;
    if(now == 10)
    {
        for(int i=0;i<10;i++)
        {
            if(now_pushed[i]!=0)
                plus_time(bd, i, now_pushed[i]);
        }
        if(is_all_12clock(bd)) // 시계가 다 12시를 가르킬 경우
        {
            return pushed;
        }
    }
    else if(now<10 && pushed<nowret)
    {
        now_pushed[now]=0;
        ret = min(ret, solve(bd, now+1, pushed, ret));

        now_pushed[now]=1;
        ret = min(ret, solve(bd, now+1, pushed+1, ret));

        now_pushed[now]=2;
        ret = min(ret, solve(bd, now+1, pushed+2, ret));

        now_pushed[now]=3;
        ret = min(ret, solve(bd, now+1, pushed+3, ret));
    }

    return ret;
}

int main()
{
    int C;
    scanf("%d",&C);

    while(C--)
    {
        vector<int> map(16, 0);
        for(int i=0;i<16;i++)
        {
            scanf("%d",&map[i]);
        }
        int resert=solve(map,0,0,987654321);

        if(resert==987654321)
            printf("-1\n");
        else
            printf("%d\n",resert);

    }

    return 0;
}