Problem C : 숫자 야구2
제한시간: 1000 ms 메모리제한: 128 MB
Special Judge
정현이는 다음과 같이 동작하는 숫자 야구 프로그램을 만들었다.
* 프로그램은 0~9까지 10개의 수를 사용하여 4자리 수의 정답을 생성한다. 0으로 시작할 수 있다.
* 10개의 수는 한번씩만 사용되므로 정답에 중복된 수는 없다.
* 프로그램에게 임의의 4자리 수를 물어보면 프로그램은 그 수를 정답과 비교한 결과를 알려준다.
* 프로그램은 자리가 일치한 숫자는 strike,
정답에 포함되나 자리가 틀린 수를 ball로 판단하여 strike와 ball의 수를 알려준다.
따라서 정답을 맞췄을 경우 프로그램의 리턴값은 strike=4, ball=0 이다.
사용자 코드가 아래와 같이 주어질 때, 주어진 소스를 분석하여
프로그램에게 질의하는 query 함수를 최대한 적게(10번 이하) 호출하여
정답을 맞출 수 있도록 tryBest함수를 완성하시오.
* 질의는 query 함수를 사용하며 정답은 tryBest함수의 input parameter int suppose[] 배열에 저장한다.
* struct Result 와 함수 Result query(int suppose[]) 는 수정할 수 없다.
* 그 외 추가적인 전역변수나 함수는 사용 가능하다.
* 질의 수가 2,520을 초과하거나 1124 같은 잘못된 숫자를 질의했을 경우
프로그램은 strike=-1, ball=-1을 리턴한다.
[참고]
사용자 소스파일을 분리컴파일 하여 문제를 푸는경우
사용자는 아래 정의한 구조체를 사용자 소스 파일의 상단에 추가하여 코딩합니다.
// *** user.cpp ***
2.#ifdef _WIN32
3.#define ACTIVE 1
4.#else
5.#define ACTIVE 0
6.#endif // __WIN32
7.#if ACTIVE
8.typedef struct Data {
9. int strike;
10. int ball;
11.} Data;
12.
13.#endif // ACTIVE
14.
15.extern Data query(int supose[]);
16.
17.void tryBest(int suppose[]) {
18.
19.}
20.
21.
22.// *** main_code ***
23.
24.#define _CRT_SECURE_NO_WARNINGS
25.#include <stdio.h>
26.#include <stdlib.h>
27.#include <time.h>
28.
29.#define MAX 4
30.#define MAX_COUNT 2520
31.
32.static int baseballNumbers[MAX];
33.static int numbersCheck[10];
34.
35.static int T;
36.
37.extern void tryBest(int suppose[]); ////************
38.
39.static int queryCallCount;
40.
41.static const int queryLimit = 110;
42.static int scoreTable[MAX_COUNT + 5];
43.
44.typedef struct Data {
45. int strike;
46. int ball;
47.} Data;
48.
49.static bool isAble(int suppose[]) {
50. int supposeCheck[10];
51.
52. for (int count = 0; count < 10; ++count)
53. supposeCheck[count] = 0;
54. for (int idx = 0; idx < MAX; ++idx) {
55. if (suppose[idx] < 0 || suppose[idx] >= 10 || supposeCheck[suppose[idx]] > 0)
56. return false;
57. supposeCheck[suppose[idx]]++;
58. }
59. return true;
60.}
61.
62.Data query(int suppose[]) {
63. Data result;
64.
65. if (queryCallCount > MAX_COUNT) {
66. result.strike = -1;
67. result.ball = -1;
68. return result;
69. }
70.
71. queryCallCount++;
72.
73. if (!isAble(suppose)) {
74. result.strike = -1;
75. result.ball = -1;
76. return result;
77. }
78.
79. result.strike = 0;
80. result.ball = 0;
81.
82. for (int idx = 0; idx < MAX; ++idx)
83. if (suppose[idx] == baseballNumbers[idx])
84. result.strike++;
85. else if (numbersCheck[suppose[idx]] > 0)
86. result.ball++;
87.
88. return result;
89.}
90.
91.static void initialize() {
92. for (int count = 0; count < 10; ++count)
93. numbersCheck[count] = 0;
94. for (int idx = 0; idx < MAX;) {
95. int c = rand() % 10;
96. if (numbersCheck[c] == 0) {
97. baseballNumbers[idx] = c;
98. numbersCheck[c]++;
99. idx++;
100. }
101. }
102. queryCallCount = 0;
103.}
104.
105.static bool check(int suppose[]) {
106. for (int idx = 0; idx < MAX; ++idx) {
107. if (suppose[idx] != baseballNumbers[idx])
108. return false;
109. }
110. return true;
111.}
112.
113.
114.void initScoreTable() {
115. int i;
116. for (i = 0; i <= 10; ++i)
117. scoreTable[i] = 100;
118. for (; i <= queryLimit; ++i)
119. scoreTable[i] = 110 - i;
120.}
121.
122.
123.int main() {
124. int total_score = 0;
125.
126.//freopen("input.txt", "r", stdin);
127. setbuf(stdout, NULL);
128.
129.//scanf("%d", &T);
130. T = 50;
131. initScoreTable();
132. srand((unsigned int)time(NULL));
133. for (int testcase = 1; testcase <= T; ++testcase) {
134. initialize();
135.
136. int suppose[MAX] = { 0 };
137. tryBest(suppose);
138.
139. if (!check(suppose)) {
140. queryCallCount = MAX_COUNT;
141. total_score = 0;
142. break;
143. }
144. printf("#%d %d : ", testcase, queryCallCount);
145. for (int i = 0; i < 4; ++i)
146. printf("%d", suppose[i]);
147. puts("");
148. if (queryCallCount > queryLimit)
149. queryCallCount = queryLimit;
150. total_score += scoreTable[queryCallCount];
151. }
152. printf("Total Score = %d\n", total_score / T);
153.
154. return 0;
155.}
// main.c
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define MAX 4
#define MAX_COUNT 2520
#define _CRT_SECURE_NO_WARNINGS
static int baseballNumbers[MAX];
static int numbersCheck[10];
static int T;
extern void tryBest(int suppose[]); ////************
static int queryCallCount;
static const int queryLimit = 110;
static int scoreTable[MAX_COUNT + 5];
typedef struct Data {
int strike;
int ball;
} Data;
static bool isAble(int suppose[]) {
int supposeCheck[10];
for (int count = 0; count < 10; ++count) supposeCheck[count] = 0;
for (int idx = 0; idx < MAX; ++idx) {
if (suppose[idx] < 0 || suppose[idx] >= 10 || supposeCheck[suppose[idx]] > 0) return false;
supposeCheck[suppose[idx]]++;
}
return true;
}
Data query(int suppose[]) {
Data result;
if (queryCallCount > MAX_COUNT) {
result.strike = -1;
result.ball = -1;
return result;
}
queryCallCount++;
if (!isAble(suppose)) {
result.strike = -1;
result.ball = -1;
return result;
}
result.strike = 0;
result.ball = 0;
for (int idx = 0; idx < MAX; ++idx)
if (suppose[idx] == baseballNumbers[idx])
result.strike++;
else if (numbersCheck[suppose[idx]] > 0)
result.ball++;
return result;
}
static void initialize() {
for (int count = 0; count < 10; ++count) numbersCheck[count] = 0;
for (int idx = 0; idx < MAX;) {
int c = rand() % 10;
if (numbersCheck[c] == 0)
{
baseballNumbers[idx] = c;
numbersCheck[c]++;
idx++;
}
}
queryCallCount = 0;
}
static bool check(int suppose[]) {
for (int idx = 0; idx < MAX; ++idx)
{
if (suppose[idx] != baseballNumbers[idx])
return false;
}
return true;
}
void initScoreTable() {
int i;
for (i = 0; i <= 10; ++i) scoreTable[i] = 100;
for (; i <= queryLimit; ++i) scoreTable[i] = 110 - i;
}
int main() {
int total_score = 0;
//freopen("sample_input.txt", "r", stdin);
setbuf(stdout, NULL);
//scanf("%d", &T);
T = 1;
initScoreTable();
srand((unsigned int)time(NULL));
for (int testcase = 1; testcase <= T; ++testcase) {
initialize();
int suppose[MAX];
tryBest(suppose);
if (!check(suppose)) {
queryCallCount = MAX_COUNT;
total_score = 0;
break;
}
printf("#%d %d : ", testcase, queryCallCount);
for (int i = 0; i < 4; ++i) printf("%d", suppose[i]);
puts("");
//if (queryCallCount > queryLimit)
// queryCallCount = queryLimit;
total_score += queryCallCount;
}
printf("Total Score = %d\n", total_score);
return 0;
}
// user.c
typedef struct Data {
int strike;
int ball;
} Data;
int chk[10000];
extern Data query(int supose[]);
void encode(int num, int arr[])
{
for (int i = 3; i >= 0; i--) {
arr[i] = num % 10;
num /= 10;
}
}
Data myquery(int a[], int b[])
{
Data result = { 0, 0 };
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (a[i] == b[j]) {
if (i == j) result.strike++;
else result.ball++;
}
}
}
return result;
}
int confirm(int num)
{
int arr1[4], arr2[4], cnt = 0, ans;
encode(num, arr1);
Data result1 = query(arr1), result2; // query 불러서 확인함
if (result1.strike == 4) return num; // 정답입니다
for (int i = num + 1; i <= 9876; i++) { // 다음 숫자를 넘어봄
if (chk[i]) continue;
encode(i, arr2);
result2 = myquery(arr1, arr2);
if (result1.strike != result2.strike || result1.ball != result2.ball) chk[i] = 1; // 거른다
else {
cnt++;
ans = i;
}
}
if (cnt == 1) return ans;
return -1;
}
void tryBest(int suppose[]) {
int i, j, k;
for (i = 123; i <= 9876; i++) { // 0123 ~ 9876 차례대로 검사
chk[i] = 0;
encode(i, suppose);
for (j = 0; j < 3; j++) for (k = j + 1; k < 4; k++) {
if (suppose[j] == suppose[k]) chk[i] = 1; // 같은 숫자가 있으면 chk 표시함
}
}
for (i = 123; i <= 9876; i++) {
if (chk[i]) continue; // 중복된 수는 거르고
k = confirm(i);
if (k >= 0) break;
}
encode(k, suppose);
}
'Computer Science' 카테고리의 다른 글
| Problem A : Bit_ImageMap3 (0) | 2020.01.30 |
|---|---|
| Problem D : 어디 있니?( where are you?) (0) | 2020.01.28 |
| 4 Problem B : 타일 채우기 (0) | 2020.01.13 |
| 4 Problem A : 책 복사하기 (0) | 2020.01.13 |
| Problem D : 쌓기나무 (0) | 2020.01.10 |
댓글