기술 블로그

2503번 숫자 야구 본문

알고리즘 문제/BOJ

2503번 숫자 야구

parkit 2018. 12. 9. 18:33
728x90
반응형

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


처음에 어떻게 접근해야할까 고민을 했다.


숫자 야구의 게임 원리를 잘(?) 알면 쉽게 푸는 문제였다.


예를 들어, 123 1 1을 입력 받았을 때,


123과 100~999를 서로 비교하여, strike 개수와 ball 개수가 다르면 false 처리해주면 된다.


어차피 100 ~ 999 중에 정답이 무조건 있고, 


100 ~ 999의 각 숫자들의 정답에 대한 strike 개수와 ball 개수는 


123의 정답에 대한 strike 개수(1)와 ball 개수(1)가 같다. 


다시 말해, 123 1 1은 정답과의 비교를 통한 확실한 정보이기 때문이다.


예)

123 1 1 일 때.

324와 123을 비교한다. 일단 strike = 1임을 바로 알 수 있다.


1 vs 2, 4

2 vs 3, 4

3 vs 3, 4


즉, ball = 1이다. strike와 ball이 입력한 123 1 1의 1 1과 같으므로 true(가능성이 있다.)이다.


724를 보자.


123

724

우선, strike = 1이다.


1 vs 2, 4

2, vs 7, 4

3 vs 7, 2


ball = 0이다. 123 1 1의 ball = 1과 다르기 때문에 false(가능성이 없다.)이다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
 
using namespace std;
 
bool num[1000= { false, };
 
void Chk(int f, int s, int t, int strike, int ball)
{
    for (int i = 100; i <= 999; i++)
    {
        int nstrike = 0, nball = 0;
 
        if (num[i])
        {
            int nf = i / 100;
            int ns = (i % 100/ 10;
            int nt = (i % 100) % 10;
 
            if (f == nf) ++nstrike;
            if (s == ns) ++nstrike;
            if (t == nt) ++nstrike;
 
            if (f != nf && (f == ns || f == nt)) ++nball;
            if (s != ns && (s == nf || s == nt)) ++nball;
            if (t != nt && (t == nf || t == ns)) ++nball;
 
            if (nstrike != strike || nball != ball) num[i] = false;
        }
    }
}
 
int main(void)
{
    int N = 0, input = 0, strike = 0, ball = 0;
 
    memset(num, truesizeof(num));
    // 일단 모두 된다고 가정
 
    for (int i = 100; i <= 999; i++)
    {
        int f = i / 100;
        int s = (i % 100/ 10;
        int t = (i % 100) % 10;
 
        if (f == s || s == t || t == f)
        {
            num[i] = false;
        }
 
        if (f == 0 || s == 0 || t == 0)
        {
            num[i] = false;
        }
    }
 
    scanf("%d"&N);
 
    for (int i = 0; i < N; i++)
    {
        int f = 0, s = 0, t = 0;
 
        scanf("%1d%1d%1d"&f, &s, &t);
        scanf("%d %d"&strike, &ball);
 
        Chk(f, s, t, strike, ball);
    }
 
    int result = 0;
 
    for (int i = 100; i <= 999; i++)
    {
        if (num[i]) ++result;
    }
 
    printf("%d\n", result);
 
    return 0;
}
cs


728x90
반응형

'알고리즘 문제 > BOJ' 카테고리의 다른 글

4690번 완전 세제곱  (0) 2018.12.09
10804번 카드 역배치  (0) 2018.12.09
1021번 회전하는 큐  (0) 2018.12.09
1057번 토너먼트  (0) 2018.12.07
1966번 프린터 큐  (0) 2018.12.05