[BOJ] 숫자 야구 2503번 C++

2024. 5. 27. 14:42· Algorithm



문제

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

  • 영수는 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개의 줄에는 각 줄마다 민혁이가 질문한 세 자리 수와 영수가 답한 스트라이크 개수를 나타내는 정수와 볼의 개수를 나타내는 정수, 이렇게 총 세 개의 정수가 빈칸을 사이에 두고 주어진다.

출력

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


접근 방식

 

완전 탐색으로 간단하게 풀 수 있다

가능한 세자리 수를 모두 구해 질문에 맞는 스트라이크 개수와 볼의 개수가 맞다면 질문을 계속해서 이어가고 맞지 않다면 return 해주는 함수를 구현하면 된다!

특별한 점은 질문과 스트라이크, 볼의 개수를 tuple로 관리해주었다는 점 말고는 무난하게 풀었다

 

 

코드

 

#include<bits/stdc++.h>
using namespace std;

int N, ans = 0;
vector<tuple<int,int,int>> v;

void sol(int cur, string num) {
    if(cur == N) {
        ans++;
        return;
    }

    int x = get<0>(v[cur]);
    int y = get<1>(v[cur]);
    int z = get<2>(v[cur]);

    string comp = to_string(x);
    int strike = 0, ball= 0;

    for(int i=0; i<3; i++) {
        if(num[i] == comp[i]) strike++;
        else if(num[i] != comp[i] && comp.find(num[i]) != string::npos) ball++;
    }

    if(y == strike && z == ball) {
        sol(cur+1, num);
    }
    else return;

}
int main() {
    cin>>N;
    for(int i=0; i<N; i++) {
        int x,y,z;
        cin>>x>>y>>z;
        v.push_back({x,y,z});
    }

    for(int i=1; i<=9; i++) {
        for(int j=1; j<=9; j++) {
            for(int k=1; k<=9; k++) {
                if(i == j || j == k || i == k) continue;
                string num;
                num += to_string(i);
                num += to_string(j);
                num += to_string(k);
                sol(0, num);
            }
        }
    }

    cout<<ans;

}

'Algorithm' 카테고리의 다른 글

[BOJ] 링크와 스타트 15661번 C++  (0) 2024.05.29
[BOJ] 도영이가 만든 맛있는 음식 2961번 C++  (1) 2024.05.28
[BOJ] DNA 1969번 C++  (0) 2024.05.15
[BOJ] 큰 수 구성하기 18511번 C++  (0) 2024.05.14
[BOJ] 분해합 2231번 C++  (0) 2024.05.10
'Algorithm' 카테고리의 다른 글
  • [BOJ] 링크와 스타트 15661번 C++
  • [BOJ] 도영이가 만든 맛있는 음식 2961번 C++
  • [BOJ] DNA 1969번 C++
  • [BOJ] 큰 수 구성하기 18511번 C++
따봉치치
따봉치치
따봉치치
김치치의개발블로그
따봉치치
전체
오늘
어제
  • 분류 전체보기 (359)
    • 면접질문 (4)
    • CS (50)
    • FE (116)
      • Javascipt (16)
      • Typescipt (6)
      • React (16)
      • CSS (5)
      • Nextjs (1)
      • 리뷰 (70)
    • Algorithm (181)
    • ETC (3)
      • Bootcamp (4)

블로그 메뉴

  • 홈
  • 태그
  • 방명록

공지사항

인기 글

태그

  • 탐욕 알고리즘
  • 투 포인터
  • BOJ
  • typescript
  • 그리디
  • 알고리즘
  • react
  • TOPCIT
  • 백준
  • 자료구조
  • 누적합
  • Stack
  • 완전탐색
  • BFS
  • 리액트
  • 우선순위 큐
  • CS
  • 데이터베이스
  • 백트래킹
  • C++
  • 모던 자바스크립트 딥다이브
  • Fe
  • 스택
  • 문자열
  • 모던 리액트 딥다이브
  • 그래프 탐색
  • Greedy
  • 자바스크립트
  • javascript
  • dp

최근 댓글

최근 글

hELLO · Designed By 정상우.v4.2.2
따봉치치
[BOJ] 숫자 야구 2503번 C++
상단으로

티스토리툴바

단축키

내 블로그

내 블로그 - 관리자 홈 전환
Q
Q
새 글 쓰기
W
W

블로그 게시글

글 수정 (권한 있는 경우)
E
E
댓글 영역으로 이동
C
C

모든 영역

이 페이지의 URL 복사
S
S
맨 위로 이동
T
T
티스토리 홈 이동
H
H
단축키 안내
Shift + /
⇧ + /

* 단축키는 한글/영문 대소문자로 이용 가능하며, 티스토리 기본 도메인에서만 동작합니다.