Taxol

I’ve always been.

백준 2503 - 단어 수학

Updated:

C++

2503 번 - 숫자 야구

문제

현재 민혁이와 영수는 게임을 하고 있는 도중에 있다. 민혁이가 영수에게 어떤 수들을 물어보았는지, 그리고 각각의 물음에 영수가 어떤 대답을 했는지가 입력으로 주어진다. 이 입력을 바탕으로 여러분은 영수가 생각하고 있을 가능성이 있는 수가 총 몇 개인지를 알아맞혀야 한다.
영수는 동아리의 규율을 잘 따르는 착한 아이라 민혁이의 물음에 곧이곧대로 정직하게 답한다. 그러므로 영수의 답들에는 모순이 없다.
민혁이의 물음들과 각각의 물음에 대한 영수의 답이 입력으로 주어질 때 영수가 생각하고 있을 가능성이 있는 답의 총 개수를 출력하는 프로그램을 작성하시오. 문제 출처

접근 방법

  1. DFS를 이용하여 1부터 9까지의 수 중 중복없이 3개를 뽑는다.
  2. 뽑은 수와 민혁이가 질문한 세자리의 수와 스트라이크, 볼의 개수를 가지고 비교하여 모두 해당하면 가능성이 있는 답으로 결정한다.
  3. 가능성이 있는 답의 개수를 구한다.

구현

Main()

민혁이가 부른 세자리 수와 strike, ball을 각각 think, sb에 저장한다.

DFS()

세 자리의 수를 뽑는다. lv은 각 수의 자리를 나타내며, visited를 통해 뽑은 수의 유무를 확인한다.
lv이 3이 되어 세개의 자리 수를 뽑으면 Cal()을 호출하여 가능성이 있는 답인지 확인한다.
true를 반환하면 답의 개수를 늘리고 DFS를 종료하고 다음 경우의 수를 호출한다.

Cal()

뽑은 세자리의 수와 민혁이가 뽑은 수를 비교한다. 뽑은 세자리의 수를 sel이라고 하고 민혁이가 뽑은 수를 str이라고 하면,
sel와 str의 각 자리와 수가 같으면 strike를 감소하고, 자리수는 다르지만 수가 같은 것이 나오면 ball을 감소한다.
strike와 ball이 각각 0이면 가능성이 있는 답이며 만약 하나라도 다를 시에는 가능성이 없는 수이므로 false를 리턴한다.

코드

#include <iostream>
#include <vector>
#include <string>

using namespace std;

int n, answer;
vector<string> think;
vector<pair<int, int>> sb;
void DFS(int lv);
bool Cal();
int visited[10];
int sel[3];

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> n;
	string temp;
	int s, b;
	for (int i = 0; i < n; i++) {
		cin >> temp;
		cin >> s;
		cin >> b;
		think.push_back(temp);
		sb.push_back(make_pair(s, b));
	}
	DFS(0);
	cout << answer;
}

void DFS(int lv) {
	if (lv == 3) {
		if (Cal())
			answer++;
		return;
	}
	for (int i = 1; i < 10; i++) {
		if (!visited[i]) {
			visited[i] = true;
			sel[lv] = i;
			DFS(lv + 1);
			visited[i] = false;
		}
	}
}

bool Cal() {
	for (int i = 0; i < n; i++) {	//민혁이가 부른 수를 하나씩 뽑아 확인한다.
		string str  = think.at(i);
		int strike  = sb.at(i).first;
		int ball	= sb.at(i).second;
		for (int j = 0; j < 3; j++) {
			if (sel[j] == str[j] - '0') {		//자리수가 같고 수가 같으면 strike를 감소
				strike--;
			}
			for (int k = 0; k < 3; k++) {
				if (j == k)						//같은 자리 수면 strike이며 우리는 ball을 찾아야 하므로 continue
					continue;
				if (sel[j] == str[k] - '0')
					ball--;
			}
		}
		if (strike != 0 || ball != 0) {			//strike, ball 둘 중 하나라도 0이 아니면 종료한다.
			return false;
		}
	}
	return true;
}

후기 및 개선할 점

변수 명을 select라고 설정하였다가 혼났다.
select라는 내장 함수가 있는 줄 몰랐다. 정석적인 dfs 문제

You may also enjoy