실력키우기 숫자 야구(C++)

1761 : 숫자 야구

제한시간: 1000 ms    메모리제한: 32 MB
해결횟수: 375 회    시도횟수: 936 회   

정보문화진흥원 정보 영재 동아리에서 동아리 활동을 하던 영수와 민혁이는 쉬는 시간을 틈타 숫자야구 게임을 하기로 했다.

 

* 영수는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 마음속으로 생각한다. (예: 324) 
* 민혁이는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 영수에게 묻는다. (예: 123) 
* 민혁이가 말한 세 자리 수에 있는 숫자들 중 하나가 영수의 세 자리 수의 동일한 자리에 위치하면 스트라이크 한 번으로 센다. 숫자가 영수의 세 자리 수에 있긴 하나 다른 자리에 위치하면 볼 한 번으로 센다.

예) 영수가 324를 갖고 있으면 
429는 1 스트라이크 1 볼이다. 
241은 0 스트라이크 2 볼이다. 
924는 2 스트라이크 0 볼이다.

 

 

영수는 민혁이가 말한 수가 몇 스트라이크 몇 볼인지를 답해준다.

 

* 민혁이가 영수의 세 자리 수를 정확하게 맞추어 3 스트라이크가 되면 게임이 끝난다. 아니라면 민혁이는 새로운 수를 생각해 다시 영수에게 묻는다.

 

현재 민혁이와 영수는 게임을 하고 있는 도중에 있다. 민혁이가 영수에게 어떤 수들을 물어보았는지, 그리고 각각의 물음에 영수가 어떤 대답을 했는지가 입력으로 주어진다. 이 입력을 바탕으로 여러분은 영수가 생각하고 있을 가능성이 있는 수가 총 몇 개인지를 알아맞혀야 한다.

 

아래와 같은 경우를 생각해보자.

 

민혁: 123 
영수: 1 스트라이크 1 볼. 
민혁: 356 
영수: 1 스트라이크 0 볼. 
민혁: 327 
영수: 2 스트라이크 0 볼. 
민혁: 489 
영수: 0 스트라이크 1 볼.

 

이 때 가능한 답은 324와 328, 이렇게 두 가지이다.

 

영수는 동아리의 규율을 잘 따르는 착한 아이라 민혁이의 물음에 곧이곧대로 정직하게 답한다. 그러므로 영수의 답들에는 모순이 없다.

 

민혁이의 물음들과 각각의 물음에 대한 영수의 답이 입력으로 주어질 때 영수가 생각하고 있을 가능성이 있는 답의 총 개수를 출력하는 프로그램을 작성하시오.

 

첫째 줄에는 민혁이가 영수에게 몇 번이나 질문을 했는지를 나타내는 1 이상 100 이하의 자연수 N이 주어진다. 이어지는 N개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트라이크 개수를 나타내는 정수와 볼의 개수를 나타내는 정수, 이렇게 총 세 개의 정수가 빈칸을 사이에 두고 주어진다.

첫 줄에 영수가 생각하고 있을 가능성이 있는 답의 총 개수를 출력한다.

[Copy] 4 123 1 1 356 1 0 327 2 0 489 0 1

[Copy] 2

출처 : KOI 본선 2008 초3

/**************************************************************
    Problem: 1761
    User: a132034
    Language: C++
    Result: Success
    Time:0 ms
    Memory:1744 kb
****************************************************************/
 
 
#include    <iostream>
using namespace std;
 
int feedback[111][9];
bool pass;
bool fullPass;
int cnt;
int main()
{
    int N;
    cin >> N;
 
    for (int i = 1; i <= N; ++i)
    {
        int num;
        cin >> num >> feedback[i][4] >> feedback[i][5];
        feedback[i][1] = num / 100;
        feedback[i][2] = (num) / 10 % 10;
        feedback[i][3] = num % 10;
    }
 
    for (int i = 1; i <= 9; ++i)
    {
        for (int j = 1; j <= 9; ++j)
        {
            if (i == j)
                continue;
            for (int k = 1; k <= 9; ++k)
            {
                if (i == k)
                    continue;
                if (j == k)
                    continue;
                 
                fullPass = true;
                for (int x = 1; x <= N; ++x) // feedback for loop
                {
                    pass = false;
                    if (feedback[x][4] == 3) //답이 나온 경우이므로
                    {
                        cout << 1 << endl;
                        return 0;
                    }
                    if (feedback[x][4] == 2)
                    {
                        if (feedback[x][5] == 0)
                        {
                            //두개는 같아야하고 하나는 없어야 함
                            if (i == feedback[x][1] && j == feedback[x][2])
                            {
                                if (k != feedback[x][3])
                                    pass = true;
                            }
                            else if (j == feedback[x][2] && k == feedback[x][3])
                            {
                                if (i != feedback[x][1])
                                    pass = true;
                            }
                            else if (i == feedback[x][1] && k == feedback[x][3])
                            {
                                if (j != feedback[x][2])
                                    pass = true;
                            }
                        }
                    }
                    if (feedback[x][4] == 1)
                    {
                        if (feedback[x][5] == 0)
                        {
                            //1개만 동일한 자리에 있고 나머지는 없어야 함
                            if (i == feedback[x][1])
                            {
                                if (j != feedback[x][2] && j != feedback[x][3] && k != feedback[x][2] && k != feedback[x][3])
                                    pass = true;
                            }
                            else if (j == feedback[x][2])
                            {
                                if (i != feedback[x][1] && i != feedback[x][3] && k != feedback[x][1] && k != feedback[x][3])
                                    pass = true;
                            }
                            else if (k == feedback[x][3])
                            {
                                if (i != feedback[x][1] && i != feedback[x][2] && j != feedback[x][1] && j != feedback[x][2])
                                    pass = true;
                            }
                        }
                        else if (feedback[x][5] == 1)
                        {
                            //하나는 동일한 자리 하나는 다른자리에 있어야 하고 하나는 없어야 함
                            if (i == feedback[x][1])
                            {
                                if (j == feedback[x][3])
                                {
                                    if (k != feedback[x][2])
                                        pass = true;
                                }
                                else if (k == feedback[x][2])
                                {
                                    if (j != feedback[x][3])
                                        pass = true;
                                }
                            }
                            else if (j == feedback[x][2])
                            {
                                if (i == feedback[x][3])
                                {
                                    if (k != feedback[x][1])
                                        pass = true;
                                }
                                else if (k == feedback[x][1])
                                {
                                    if (i != feedback[x][3])
                                        pass = true;
                                }
                            }
                            else if (k == feedback[x][3])
                            {
                                if (i == feedback[x][2])
                                {
                                    if (j != feedback[x][1])
                                        pass = true;
                                }
                                else if (j == feedback[x][1])
                                {
                                    if (i != feedback[x][2])
                                        pass = true;
                                }
                            }
                        }
                        else
                        {
                            //3개 다 있어야 하는데 한개 빼고 나머지는 위치가 달라야 함
                            if (i == feedback[x][1])
                            {
                                if (j == feedback[x][3] && k == feedback[x][2])
                                    pass = true;
                            }
                            else if (j == feedback[x][2])
                            {
                                if (i == feedback[x][3] && k == feedback[x][1])
                                    pass = true;
                            }
                            else if (k == feedback[x][3])
                            {
                                if (i == feedback[x][2] && j == feedback[x][1])
                                    pass = true;
                            }
                        }
                    }
                    if (feedback[x][4] == 0)
                    {
                        if (feedback[x][5] == 0)
                        {
                            //걍 하나라도 있으면 안됨
                            if ((i != feedback[x][1] && i != feedback[x][2] && i != feedback[x][3]) &&
                                (j != feedback[x][1] && j != feedback[x][2] && j != feedback[x][3]) &&
                                (k != feedback[x][1] && k != feedback[x][2] && k != feedback[x][3]))
                                pass = true;
 
                        }
                        else if (feedback[x][5] == 1)
                        {
                            //1개 있어야 하고 위치가 달라야 함
                            if (i == feedback[x][2] || i == feedback[x][3])
                            {
                                if (j != feedback[x][1] && j != feedback[x][2] && j != feedback[x][3] &&
                                    k != feedback[x][1] && k != feedback[x][2] && k != feedback[x][3])
                                    pass = true;
                            }
                            else if (j == feedback[x][1] || j == feedback[x][3])
                            {
                                if (i != feedback[x][1] && i != feedback[x][2] && i != feedback[x][3] &&
                                    k != feedback[x][1] && k != feedback[x][2] && k != feedback[x][3])
                                    pass = true;
                            }
                            else if (k == feedback[x][1] || k == feedback[x][2])
                            {
                                if (i != feedback[x][1] && i != feedback[x][2] && i != feedback[x][3] &&
                                    j != feedback[x][1] && j != feedback[x][2] && j != feedback[x][3])
                                    pass = true;
                            }
                        }
                        else if (feedback[x][5] == 2)
                        {
                            //2개 있어야 하는데 위치가 달라야 함
                            if (i == feedback[x][2] || i == feedback[x][3])
                            {
                                if (j == feedback[x][1] || j == feedback[x][3])
                                {
                                    if (k != feedback[x][1] && k != feedback[x][2] && k != feedback[x][3])
                                        pass = true;
                                }
                                else if (k == feedback[x][1] || k == feedback[x][2])
                                {
                                    if (j != feedback[x][1] && j != feedback[x][2] && j != feedback[x][3])
                                        pass = true;
                                }
                            }
                            else if (j == feedback[x][1] || j == feedback[x][3])
                            {
                                if (k == feedback[x][1] || k == feedback[x][2])
                                {
                                    if (i != feedback[x][1] && i != feedback[x][2] && i != feedback[x][3])
                                        pass = true;
                                }
                            }
                        }
                        else //feedback[x][5] == 3
                        {
                            //3개 다 있어야 하는데 다 위치가 달라야 함
                            if (i == feedback[x][2] || i == feedback[x][3])
                            if (j == feedback[x][1] || j == feedback[x][3])
                            if (k == feedback[x][1] || k == feedback[x][2])
                                pass = true;
                        }
                    }
                    if (!pass)
                        fullPass = false;
                    if (!fullPass)
                        break;
                }//end feedback for loop
 
                if (fullPass)
                    cnt++;
            }
        }
    }
    cout << cnt << endl;
    return 0;
}

실력키우기 마지막 문제... 드디어 풀었다 ㅠㅠ 

나름 2주일 넘게 고민 고민 고민... 하다가 결국 지금까지 고민한거랑은 전혀 썡뚱맞은 방법으로 풀게 되었다. 

초등학교 3학년 문제인데 너무 어려운 것 같다... 이걸 어떻게 초3이... 대단... 

초등학교 문제라는  약간은 단순하게 접근했더니 해결되었다. 

풀이방법은 사실 너무나 간단하다. 코드가 길 뿐.... (물론 여기서 얼마든 더 줄일 수 있을것이다. 가독성과 미천한 실력으로 인해 200줄이 넘는 코드가 나왔다..)

1. 111~999까지 (같은 수는 안된다고 하였으므로 111~999까지 for loop가 돌기는 하나 사실상 123~987일 것이다.) 모든 수를 돈다.

2. 입력받은 조건과 맞추어 본다. 모든 조건을 통과하면 후보. 

3. 끝. 

이렇게 되면 대략 111~999까지 대충 700개정도의 숫자를 최대 100개의 조건에 맞춰보는 것이므로 그리 많은 연산은 아니다. 여기서 뭐 좀더 가지치기를 하거나 연산을 짧게 만든다면 물론 더 짧아질 수도 있을 것이다. 

2번의 조건 통과가 주요 구현 내용인데 결국 말을 코드로 쓴 것이나 다름없다. 

> 조건은 하나하나 if문과 else문으로 떡칠해준다. 

경우의 수 (strike, ball)는 아래와 같다. 

3 0

2 0

1 0, 1 1, 1 2

0 0, 0 1, 0 2, 0 3

1) 3 0인 경우 이게 답이 되므로 1 출력 후 종료하면 된다.

2) 2 0인 경우 민혁이가 말한 값 중 2개가 정확히 맞아야 하고 한 개는 맞으면 안된다. 

3) 1 0인 경우 1개가 정확히 맞아야 하며 나머지 2개는 정답에 없어야 한다. 

4) 1 1인 경우 1개가 정확히 맞아야 하며 나머지 1개는 위치가 다르지만 숫자는 맞아야 하고 나머지 1개는 정답에 없어야 한다.

5) 1 2인 경우 1개가 정확히 맞아야 하며 나머지 두개가 서로 위치가 크로스되어 맞으면 된다. 

6) 0 0인 경우 전부 정답이 아니어야 한다.

7) 0 1인 경우 1개가 다른 위치에서 맞아야 하고 나머지 2개는 정답이 아니어야 한다.

8) 0 2인 경우 2개가 다른 위치에서 맞아야 하고 나머지 2개는 정답이 아니어야 한다.

9) 0 3인 경우 3개가 모두 다른위치에서 맞아야 한다. 

설명을 쓰다보니 뭔가 어렵기도 하고 처음보면 이해가 잘 안갈것같지만... 분명 하루정도 고민한 사람이라면 무슨 의미인지 알 것이다... 아마도...

9가지 경우가 위에 전부 코드화 되어 있으니 코드를 보며 이해하는 것도 나쁘지 않을 것 같다. 

feedback 배열은 1번째 2번째 3번째 수 strike수 ball수 순서로 1 2 3 4 5번 배열에 들어있고

현재 후보값은 i, j, k가 각각 1번째 2번째 3번째 수이다.

모든 조건을 통과하면 fullPass 변수가 true가 유지되고 하나라도 통과하지 못하면 pass 변수가 false가 되어 fullPass 변수가 false가 된다. 

모든 조건을 통과하는 i,j,k 조합이 나오면 cnt를 1 증가해준다.