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

https://www.acmicpc.net/problem/2503

영수는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 마음속으로 생각한다. 민혁이는 1에서 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 영수에게 묻는다. 민혁이가 말한 세 자리 수에 있는 숫자들 중 하나가 영수의 세 자리 수의 동일한 자리에 위치하면 스트라이크 한 번으로 센다. 숫자가 영수의 세 자리 수에 있긴 하나 다른 자리에 위치하면 볼 한 번으로 센다. 민혁이가 영수의 세 자리 수를 정확하게 맞혀 3 스트라이크가 되면 게임이 끝난다. 아니라면 민혁이는 새로운 수를 생각해 다시 영수에게 묻는다.

 

민혁이의 물음들과 각각의 물음에 대한 영수의 답이 입력으로 주어질 때, 영수가 생각하고 있을 가능성이 있는 답의 총 개수를 구하는 문제다.

 

---

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하며 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

ex. 가능한 시간 복잡도, 알고리즘 선택

입출력 제한

• 1 ≤ N ≤ 100

 

처음엔 질문과 답을 하나씩 입력받으면서 각각 조건을 추리고 모든 조건을 만족하는 숫자를 걸러내는 방법을 생각해봤는데, 각 질문의 스트라이크와 볼 값에 따라 생각해야 할 경우의 수가 너무 많아질 것 같았다. 그래서 차라리 N개의 질문을 모두 입력받고 123부터 987까지의 모든 숫자마다 N번 비교해가며 조건을 만족하는 숫자의 개수를 찾는 방법으로 구현해보기로 했다. 이 방법을 써도 N의 최댓값이 100이라 9 * 8 * 7 * 100 * 3 * 3 만에 해결할 수 있어서 시간 초과가 나지 않는다.

 

우선 민혁이가 물어본 질문과 그에 대한 답을 vector에 모두 저장하고, 스트라이크 개수가 3개인 경우엔 답이 무조건 1개뿐이므로 1을 출력하고 프로그램을 종료하도록 했다. 1부터 9까지의 서로 다른 숫자 세 개로 구성된 세 자리 수를 백트래킹으로 만들고, 각 수마다 민혁이가 물어본 모든 질문에 대한 답(스트라이크, 볼)을 만족하는지 확인하고 만족한다면 개수에 포함하도록 했다.

 

---

코드 설계하기

위의 [문제 탐색하기]에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡고, 문제 풀이를 본격적으로 하기 전 이 문제를 풀기 위한 로드맵을 그리는 과정!

- 어떤 순서로 코드를 작성해야 할지
- 어떤 함수들을 작성해야 할지

1. N 입력받기
2. N개의 질문과 그에 대한 답을 입력받아 vector에 저장하기
   1. 스트라이크 개수가 3개인 경우 1을 출력하고 프로그램 종료
3. 백트래킹 함수로 123부터 987까지의 숫자를 만들고 vector에 있는 모든 조건과 비교하기
4. 모든 조건을 만족하는 숫자의 개수 출력하기

 

---

시도 회차 수정 사항 (Optional)

- '틀렸습니다'를 받았다면 왜 틀렸는지 고민해보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검
- 한 번에 맞히면 pass해도 됨!

pass

 

---

정답 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;

int n,s,b,cnt;
string st;
vector<pair<string,pair<int,int>>> v;
bool visit[10];

void dfs(int dep, string str) {
    if (dep==3) {
        for (int i=0; i<n; i++) {
            int tmp_s=0, tmp_b=0;
            for (int j=0; j<3; j++) {
                for (int k=0; k<3; k++) {
                    if (str[j]==(v[i].first)[k]) {
                        if (j==k) tmp_s++;
                        else tmp_b++;
                    }
                }
            }
            if (tmp_s!=v[i].second.first || tmp_b!=v[i].second.second) return;
        }
        cnt++;
        return;
    }
    for (int i=1; i<=9; i++) {
        if (!visit[i]) {
            visit[i] = true;
            dfs(dep+1,str+to_string(i));
            visit[i] = false;
        }
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;
    for (int i=0; i<n; i++) {
        cin >> st >> s >> b;
        if (s==3) {
            cout << 1;
            return 0;
        }
        v.push_back({st,{s,b}});
    }

    dfs(0,"");

    cout << cnt;
}