반응형
Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 소프티어
- OFFSET
- boj #19237 #어른 상어
- 처우산정
- 이분탐색
- 연결요소
- 처우협의
- upper_bound
- msSQL
- 13908
- Kafka
- softeer
- compose
- 퇴사통보
- 물채우기
- BFS
- 매개변수탐색
- BOJ
- 백준
- 기술면접
- @P0
- 성적평가
- 백트래킹
- 파라메트릭
- 6987
- dfs
- incr
- Docker
- 오퍼레터
- 경력
Archives
- Today
- Total
기술 블로그
2503번 숫자 야구 본문
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, true, sizeof(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 |