02.06. 숫자 야구[Brute-force Search][백준 2503]

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

2503번: 숫자 야구

 

Algorithm classification : Brute-force Search

 

02.06.1. Problem

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

• 영수는 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, 이렇게 두 가지이다.

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

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

 

02.06.2. Input limit

In the first line, a natural number N between 1 and 100 is given, indicating how many times Minhyuk asked Youngsu a question. In the next N lines, in each line, three integers are given with a space in between: the three-digit number asked by Minhyuk, an integer representing the number of strikes answered by Youngsoo, and an integer representing the number of balls.

 

02.06.3. Output

In the first line, print the total number of possible answers that the zero is thinking of.

 

02.06.4. Solution

모든 경우를 커버할 수 있는 배열을 만들고 질문마다 나올 수 없는 값을 지우는 방식을 사용하면 됩니다. 그 후 남아있는 수의 개수를 세면 되죠. 

 

이때, 배열의 size 자체는 1000에서 900으로 떨굴수는 있습니다. 범위가 111~999니까요. 하지만 indexing이 귀찮아지니 그냥 size를 1000으로 하였습니다.

int check[1000] = {0};

 

만약 추론을

	for(i = 0; i < n; i++){
		scanf("%d %d %d", &a, &s, &b);
		a3 = a%10;
		a2 = (a/10)%10;
		a1 = (a/100)%10;
		if(s == 0){
			if(b == 1){
				for(i = 1; i < 1000; i++){
					i3 = i%10;
					i2 = (i/10)%10;
					i1 = (i/100)%10;
					if(!(i1 == a2 || i1 == a3) && !(i2 == a1 || i2 == a3) || !(i3 == a1 || i3 == a2))
						check[i] = 0;
					
				}
			}
			if(b == 3){
				...
			}
		}
	}

이런식으로 하면 어떻게 될까요? 진짜 이따구로 하면 힘들어집니다. 어떤 숫자일지 추론해서 나오는 숫자를 제외한 나머지 숫자를 제외하는 방식보다 역추론이 편합니다. 즉, 볼과 스트라이크를 각각의 수에 대해 계산하고 입력과 맞지 않으면 바로 탈락시키는 거죠. 상당히 난잡해 보일 수 있지만 간단합니다.

	for(i = 111; i < 1000; i++){
		i3 = i%10;
		i2 = (i/10)%10;
		i1 = (i/100)%10;
		if(i1 * i2 * i3 == 0 || i1 == i2 || i2 == i3 || i1 == i3)
			check[i] = 1;
	}
	for(j = 0; j < n; j++){ 
		scanf("%d %d %d", &a, &s, &b);
		a3 = a%10;
		a2 = (a/10)%10;
		a1 = (a/100)%10;
		for(i = 111; i < 1000; i++){
			s1 = b1 = 0;
			
			i3 = i%10;
			i2 = (i/10)%10;
			i1 = (i/100)%10;
			
			if(i1 == a1)
				s1++;
			else if(i1 == a2 || i1 == a3)
				b1++;
			if(i2 == a2)
				s1++;
			else if(i2 == a1 || i2 == a3)
				b1++;
			if(i3 == a3)
				s1++;
			else if(i3 == a1 || i3 == a2)
				b1++;
			if(!(s == s1 && b == b1))
				check[i] = 1;
		} 
	}
	int count = 0;
	for(i = 111; i < 1000; i++){
		if(check[i] == 0)
			count++;
	}
	printf("%d", count);

문제를 직접 풀어볼 여러분들을 위해 data set을 적어두겠습니다. 도움이 되길 바라겠습니다.

 

Case 1

1
123 0 2
>> 54