koitp SDS_TEST_CLOCK 고장난시계

문제 링크입니다: https://koitp.org/problem/SDS_TEST_CLOCK/read/

같은 학교 학우인 sansan709(degurii.tistory.com)님의 도움으로 풀 수 있었던 문제였습니다.

XOR 연산을 이용하여 간단하게 풀 수 있는 문제였는데 아직 비트 연산에 익숙치 않은 저에게는 구현이 상당히 까다로웠던 문제였습니다.

알고리즘은 아래와 같습니다.

1. 0 ~ 9까지 세그먼트들을 이차원 배열에 미리 저장합니다.

2. 7개의 세그먼트들로 구성된 숫자 4개를 입력받고 해당 숫자들로 시간을 표현할 수 있으면 우선 해당 시간을 구합니다.

3. 세그먼트들은 최대 2번 고칠 수 있습니다.

i) 따라서, XOR 연산을 통해 하나의 세그먼트를 고친 뒤 시간을 표현할 수 있으면 해당 시간을 구하는데 기존 시간보다 이른 시간일 때만 업데이트합니다.

ii) XOR 연산을 통해 두개의 세그먼트를 고친 뒤 시간을 표현할 수 있으면 해당 시간을 구하는데 기존 시간보다 이른 시간일 때만 업데이트합니다.

#include <iostream>

#include <algorithm>

#include <queue>

using namespace std;

 

const int INF = 0x3f3f3f3f;

 

int p[4][7];

 

//0 ~ 9

const int digits[10][7] = {

        { 1, 1, 1, 1, 1, 1, 0 },

        { 0, 0, 0, 0, 1, 1, 0 },

        { 1, 0, 1, 1, 0, 1, 1 },

        { 1, 0, 0, 1, 1, 1, 1 },

        { 0, 1, 0, 0, 1, 1, 1 },

        { 1, 1, 0, 1, 1, 0, 1 },

        { 1, 1, 1, 1, 1, 0, 1 },

        { 1, 0, 0, 0, 1, 1, 0 },

        { 1, 1, 1, 1, 1, 1, 1 },

        { 1, 1, 0, 1, 1, 1, 1 }

};

 

//0 ~ 9 중 일치하는 숫자 찾는 함수

int segToDigit(int seg[])

{

        int num = -1;

        for (int i = 0; i < 10; i++)

        {

                 bool c = true;

                 for (int j = 0; j < 7; j++)

                 {

                         if (seg[j] != digits[i][j])

                         {

                                 c = false;

                                 break;

                         }

                 }

                 if (c)

                 {

                         num = i;

                         break;

                 }

        }

        return num;

}

 

//범위 내에 있는 시간이 맞는가 판별

bool isValidTime(int h, int m)

{

        if (0 <= h && h < 24 && 0 <= m && m < 60)

                 return true;

        return false;

}

 

//현재 시간 반환

//올바른 표기법이 아니라면 (-1, -1) 반환

pair<int, int> segToTime()

{

        //시간

        int h1 = segToDigit(p[0]);

        int h2 = segToDigit(p[1]);

        //분

        int m1 = segToDigit(p[2]);

        int m2 = segToDigit(p[3]);

 

        if (h1 == -1 || h2 == -1 || m1 == -1 || m2 == -1)

                 return { -1, -1 };

 

        int h = h1 * 10 + h2;

        int m = m1 * 10 + m2;

 

        if (isValidTime(h, m))

                 return { h, m };

        return { -1, -1 };

}

 

void calculateTime(pair<int, int> temp, int &hour, int &minute)

{

        //정상적인 시간이 아닐 경우

        if (temp.first == -1)

                 return;

        //시간, 분

        int h = temp.first, m = temp.second;

 

        //최소 시간 출력해야하기 때문에

        if (hour == h && minute > m)

        {

                 hour = h;

                 minute = m;

        }

        else if (hour > h)

        {

                 hour = h;

                 minute = m;

        }

}

 

int main() {

        ios_base::sync_with_stdio(false);

        cin.tie(0);

        int test_case;

        cin >> test_case;

 

        for (int t=1; t<=test_case; t++)

        {

                 int hour = 99, minute = 99;

                 for (int i = 0; i < 4; i++)

                         for (int j = 0; j < 7; j++)

                                 cin >> p[i][j];

                 calculateTime(segToTime(), hour, minute);

 

                 for (int i = 0; i < 28; i++)  // 하나만 고장

                 {

                         p[i / 7][i % 7] ^= 1;

                         calculateTime(segToTime(), hour, minute);

                         p[i / 7][i % 7] ^= 1;

                 }

                 for (int i = 0; i < 28; i++)  // 두개 고장

                 {

                         p[i / 7][i % 7] ^= 1;

                         for (int j = i + 1; j < 28; j++)

                         {

                                 p[j / 7][j % 7] ^= 1;

                                 calculateTime(segToTime(), hour, minute);

                                 p[j / 7][j % 7] ^= 1;

                         }

                         p[i / 7][i % 7] ^= 1;

                 }

 

                 cout << "#" << t << " " << hour << " " << minute << "\n";

        }

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~