[BOJ] 숫자 야구(2503)

[백준(BOJ)] 숫자 야구(2503) C++

문제 : BOJ_2503번 숫자 야구

문제 설명

완전탐색

우리가 흔히 아는 야구게임을 구현하는 문제입니다.

세 자리 숫자를 맞춰야하고, 각 자리의 수는 중복이 허용되지 않습니다.

n개의 숫자가 주어지며, 각 숫자마다 볼과 스트라이크가 주어지고,

n개의 숫자 뒤에 가능성이 있는 답의 총 개수를 출력해야 합니다.

---

Solution

n의 최댓값이 100, 세자리 수의 최대값은 111~999인데,

중복을 허용하는 경우의 수라고 해도

100 * 888 = 88,800임으로 완전 탐색이 가능합니다.

저는 처음에 n마다 stirke의 수와 ball의 수에

따른 경우의 수로 조건문을 짜봤지만,

이렇게 하면 너무 복잡해지고, 각 n마다 체크되지않은 모든 수를 돌면서, 조건에 맞지 않으면 정답에서 탈락시키는 식으로 문제를 해결했습니다.

세 자리수를 하나 씩 체크하면서, 스트라이크의 개수와 볼의 개수를 알아보고, 주어진 input과 맞지않다면 그 수는 정답에서 제외했습니다.

---

Description

1. 각 자리 수 마다 0이 허용되지않으므로, 삼중포문으로 모든 경우의 수를 나타냈습니다.
2. 각 자리수가 겹치는 경우를 그대로 놔두면 wrong answer가 나오므로, 각 자리수가 겹치는 경우도 정답에서 제외를 해주어야합니다.

#include <iostream>
using namespace std;
int vis[1000]; // vis=1 이라면 정답에서 제외된 수
int res = 9 * 9 * 9; // 자리수가 중복되는 수 역시 정답의 가짓수에서 뺄 것 이므로 9*9*9
int main(void) {
    int N;
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        int num;
        scanf("%d", &num);
        int firstNum = num / 100;
        int secondNum = (num / 10) % 10;
        int thirdNum = num % 10;
        int strike, ball;
        scanf("%d%d", &strike, &ball);
        for (int j = 1; j <= 9; j++) {
            // 3중 포문으로 전체 수 확인 (자리수에서 중복되는 수는 마지막 포문에서 제외)
            for (int k = 1; k <= 9; k++) {
                for (int l = 1; l <= 9; l++) {
                    int value = 100 * j + 10 * k + l;
                    if (vis[value]) continue;
                    if (j == k || j == l || k == l) {
                        // 자리수에서 중복되는 것이 있으면 정답에서 제외
                        vis[value] = 1;
                        res--;
                        continue;
                    }
                    int nowStrike = 0;
                    int nowBall = 0;
                    int isStrike[1000] = { 0, };
                    if (j == firstNum) {
                        nowStrike++;
                        isStrike[j]++;
                    }
                    if (k == secondNum) {
                        nowStrike++;
                        isStrike[k]++;
                    }
                    if (l == thirdNum) {
                        nowStrike++;
                        isStrike[l]++;
                    }
                    if (!isStrike[j]) {
                        if (j == secondNum || j == thirdNum) nowBall++;
                    }
                    if (!isStrike[k]) {
                        if (k == firstNum || k == thirdNum) nowBall++;
                    }
                    if (!isStrike[l]) {
                        if (l == firstNum || l == secondNum) nowBall++;
                    }
                    if (strike == nowStrike && ball == nowBall) continue;
                    else {
                        vis[value]++;
                        res--;
                    }
                }
            }
        }
    }
    printf("%d\n", res);
    return 0;
}