글 읽기 - 1039번 도움 요청드립니다.

ilovefilm 9년 전 0

안녕하세요. 교환문제를 풀고 있는데요. 도저히 답이 나오지 않아 도움 요청드립니다.

나름 많은 테스트 케이스를 통해 검증을 해봤는데요. 제 생각에는 정답인것 같은데 채점 시 계속 틀렸다고 나오네요.

고수님들 조언좀 부탁드리겠습니다.

#include <iostream>
using namespace std;
#define MAX_QUEUE 10000000
#define MAX_VISIT 1000010
#define MAX_DEPTH 11
int N;
int M;
// 수행 횟수
int K;
int POWVALUE[9] = { 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, };
int QUEUE[MAX_QUEUE];
int rear;
int front;

int Swap(int value, int pos_a, int pos_b);
int getSingleData(int value, int pos);

int visit[MAX_DEPTH][MAX_VISIT];

void init() {
	rear = 0;
	front = 0;

	for (int i = 0; i < MAX_DEPTH; i++) {
		for (int j = 0; j < MAX_VISIT; j++) {
			visit[i][j] = 0;
		}
	}
}

void enqueue(int data) {
	QUEUE[rear] = data;
	rear++;
	if (rear >= MAX_QUEUE) {
		cout << "Queue overflow " << endl;
	}
}

int dequeue() {
	int ret = QUEUE[front];
	front++;
	return ret;
}

bool isEmpty() {
	if (front == rear) return true;
	return false;
}


int getDepth(int value) {
	if (value >= 10000000) return 10;
	int ret = (value % 10000000);
	if (ret > 0) ret = ret / 1000000;
	return ret;
}

void dumpQueue() {
	for (int i = front; i < rear; i++) {
		cout << QUEUE[i] << endl;
	}
}

int _max(int a, int b) {
	if (a > b) return a;
	return b;
}

int getMaxData() {
	int ret = K * 1000000;
	for (int i = front; i < rear; i++) {
		ret = _max(ret, QUEUE[i]);
	}
	ret -= K * 1000000;
	return ret;
}

void findMaxValue() {

	enqueue(N);

	while (isEmpty() == false) {
		int current = dequeue();
		int depth = getDepth(current);
		if (depth >= K) {
			enqueue(current);
			break;
		}
				
		for (int i = M; i > 1 ; i--) {
			for (int j = i-1 ; j >= 1 ; j--) {
				if (i == M && getSingleData(current, j) == 0) continue;	

				int data = current;
				data = Swap(data, i, j);
				// sets depth using
				data = data + 1000000;
				int visitData = data - ((depth+1)* 1000000);
				if (visit[depth + 1][visitData] == 1) continue;
				visit[depth + 1][visitData] = 1;
				enqueue(data);
			}
		}
	}

}

int genM() {
	int div = 1000000;
	for (int i = 7; i >= 1; i--) {
		if (N / div > 0) {
			return i;
		}
		div = div / 10;
	}
	return 1;
}

int Swap(int value, int pos_a, int pos_b) {
	int valueA = (value % POWVALUE[pos_a]);
	if(valueA > 0) valueA = valueA / POWVALUE[pos_a - 1];
	int valueB = (value % POWVALUE[pos_b]);
	if (valueB > 0) valueB = valueB / POWVALUE[pos_b - 1];

	value -= valueA * POWVALUE[pos_a - 1];
	value -= valueB * POWVALUE[pos_b - 1];

	valueA = valueA * POWVALUE[pos_b-1];
	valueB = valueB * POWVALUE[pos_a-1];
	value += valueA;
	value += valueB;
	return value;
}


int getSingleData(int value, int pos) {
	int ret = 0;
	int valueA = (value % POWVALUE[pos]);


	if (valueA > 0) valueA = valueA / POWVALUE[pos - 1];
	return valueA;
}


int main() {
	init();
	cin >> N;
	cin >> K;
	M = genM();
	findMaxValue();
	int result = getMaxData();
	if (result > 0) {
		cout << result << endl;
	}
	else {
		cout << "-1" << endl;
	}
	return 0;
}

yukariko 9년 전 2

1000000 10

에서 -1이 나오네요.

1000000 이 나와야 맞습니다.

ilovefilm 9년 전 0

@yukariko 님 이틀 연속 도움 받네요. 사실 1000000이라는 숫자 * K를 Queue를 사용할때 교환의 횟수로 사용하고 있었습니다.(ㅠ.ㅠ)
도움 너무 감사드립니다. ^^

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

1039번 도움 요청드립니다.

ilovefilm 9년 전 0

yukariko 9년 전 2

ilovefilm 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말