Problem D : 어디 있니?( where are you?)

Problem D : 어디 있니?( where are you?)

 

제한시간: 1000 ms    메모리제한: 128 MB

 

 

 1 ~ 256까지의 정수 중에서 200개를 중복되지 않게 골라내어 임의의 순서로 나열한 수열 SEQ[]가 있다.

여러분은 이 수열의 구성을 정확하게 찾아서 seq[] 배열에 담아야 하는 임무를 수행해야 한다.

 

사용자는 consistOf(int seq[]) 함수에서  main.cpp에 선언된

countScore(int seq[]) 함수를 이용하여 SEQ​[]배열에 대한 힌트를 얻을 수 있다.

countScore(int seq[]) 함수는 배열의 구성원을 비교하여 다음과 같이 score를 구해서 돌려준다.

 

1. seq[] 배열과 SEQ[]배열의 같은 위치의 값이 같다면 256점을 추가한다.

2. SEQ[]배열의 값이 seq[]배열에 한번 등장할 때마다 1점을 추가한다.

 

예를 들어 SEQ​[] = {5, 1, 2, 4, 3}이라고 하고 seq[] = {2, 2, 2, 3, 6}이라고 하자.

이경우 countScore(int seq[]) 함수​를 실행하면 SEQ[2] 와 seq[2]가 같으므로 256점을 얻고

SEQ에 있는 원소가 seq에 모두 4개(2, 2, 2, 3)가 있으므로 4점을 추가하여 260점을 리턴하게 된다.​​

 

자세한 내용은 아래 코드를 참조하여  consistOf(int seq[]) 함수를 작성하자.   ​

 

// *** main.cpp ***
 
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
 
extern void consistOf(int seq[]);
static int SEQ[200];
 
int countScore(int seq[]) {
    int strike = 0, ball = 0;
 
    for (register int i = 0; i < 200; i++)
        if (SEQ[i] == seq[i]) strike++;
 
    for (register int i = 0; i < 200; i++)
        for (register int j = 0; j < 200; j++)
            if (SEQ[i] == seq[j]) ball++;
 
    return strike * 256 + ball;
}
 
int main(void) 
{
    int SCORE = 0;
    srand(5); // number(5) can be changed
    for (int TC = 0; TC < 50; TC++) {
        int chk[256] = { 0 };
 
        for (register int i = 0; i < 200; i++) {
            int k;
            while (1) {
                k = rand() % 255;
                if (chk[k] == 0) break;
            }
            chk[k] = 1;
            SEQ[i] = k + 1;
        }
        int seq[200] = { 0 };
 
        clock_t start = clock();
        consistOf(seq);
 
        SCORE += (int)(clock() - start) / (CLOCKS_PER_SEC / 1000);
        for (register int i = 0; i < 200; i++)
            if (SEQ[i] != seq[i]) SCORE += 100000;
    }
    printf("SCORE: %d\n", SCORE);
 
    return 0;
}
 
// *** user.cpp ***
 
extern int countScore(int seq[]); 
 
void consistOf(int seq[])
{ 
}

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

extern void consistOf(int seq[]);
static int SEQ[200], score;

int countScore(int seq[]) {

	score++;
	int strike = 0, ball = 0;

	for (register int i = 0; i < 200; i++) // strike 숫자 확인
	if (SEQ[i] == seq[i]) strike++;

	for (register int i = 0; i < 200; i++)
	for (register int j = 0; j < 200; j++)
	if (SEQ[i] == seq[j]) ball++; // ball 숫자 확인

	return strike * 256 + ball;
}

int main(void)
{
	int SCORE = 0;
	srand(5); // number(5) can be changed
	for (int TC = 0; TC < 100; TC++) {
		int chk[256] = { 0 };

		for (register int i = 0; i < 200; i++) {
			int k;
			while (1) {
				k = rand() % 255;
				if (chk[k] == 0) break; // 중복 방지
			}
			chk[k] = 1; // 사용된 숫자 체크
			SEQ[i] = k + 1; // 
		}
		int seq[200] = { 0 };

		clock_t start = clock();
		consistOf(seq);

		SCORE += (int)(clock() - start) / (CLOCKS_PER_SEC / 1000);
		for (register int i = 0; i < 200; i++)
		if (SEQ[i] != seq[i]) SCORE += 100000; // 확인
	}
	printf("SCORE: %d\n", score);

	return 0;
}

#include <stdio.h>
int *Seq, rem[200], nf[200];

extern int countScore(int seq[]);

void remfill()
{
	int i, j, k, p, q = 0, arr[200] = { 0 }, score;
	for (i = 1; i <= 256; i += 7) { // 
		p = 0;
		for (j = 0; j < 7; j++) {
			for (k = 0; k < (1 << j); k++) {
				arr[p++] = i + j; // 1은 한개, 2는 2개, 3은 3개 이런식으로 배열을 채움
			}
		}
		score = countScore(arr) % 256; // rem 전처리 과정
		for (j = 0; j < 7; j++) {
			if ((score >> j) & 1) rem[q++] = i + j; // rem에 있는 숫자들이 정리 된건가-> 비트연산 있으면 그 숫자에 표시됨
		}
	}
}

void match(int s, int e, int score)
{
	int i, j, k;
	if (score == 0) return; // 스트라이크가 없음 -> 이쪽 방향에 대해 정리 끝 
	if (score == e - s + 1) {
		for (i = s; i <= e; i++) Seq[nf[i]] = rem[nf[i]], rem[nf[i]] = 0; // 스트라이크 복사
		return;
	}
	int m = (s + e) / 2, arr[200] = { 0 };
	for (i = s; i <= m; i++) arr[nf[i]] = rem[nf[i]]; // 반절만 일단 채워봄
	int lscore = countScore(arr) / 256;
	match(s, m, lscore); // 왼쪽에 스트라이크
	match(m + 1, e, score - lscore); // 오른쪽에 스트라이크
}

void consistOf(int seq[])
{
	int i, j, k, ncnt = 200;
	Seq = seq; // 가져다가 복사하고
	for (i = 0; i < 200; i++) nf[i] = i; // 인덱스 숫자 채워넣고
	remfill();
	while (1) {
		match(0, ncnt - 1, countScore(rem) / 256); // 스트라이크 개숫가 들어감
		ncnt = 0;
		for (i = 0; i < 200; i++) {
			if (rem[i]) nf[ncnt++] = i;
		}
		if (ncnt == 0) break;
		k = rem[nf[0]];
		for (i = 1; i < ncnt; i++) rem[nf[i - 1]] = rem[nf[i]]; // 왼쪽으로 한칸씩 이동
		rem[nf[ncnt - 1]] = k; 
	}
}