글 읽기 - 고수님들 도와주세요 ㅠㅠㅠ(시간초과 에러 발생)

pda_pro12 6년 전 0

어느 부분에서 시간초과를 줄이는게 효율적인지 도무지 모르겠습니다... ㅠㅠ

탐색하는 과정에서 D,S,L,R연산을 매번 탐색하면서 가는게 시간이 오래 걸리는거 같은데...

다른 방법이 있는지 궁금합니다..ㅠㅠ

그게 아니라면 어느부분에서 시간초과 문제를 해결할 수 있을지...하... 4시간 넘게 고민하는데 답이 안나와서

헬프 요청합니다..ㅠㅠ

#include<stdio.h>
#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
#include<string.h>

using namespace std;

struct DATA {
	//vector<char> clc;
	int cnt;
	int x;
	char arr[10001];
}d;

int T, N, Dest;
int D(int N); int S(int N); int L(int N); int R(int N);  // 함수 정의
int visit[10001];

int main()
{
	cin >> T;
	

	for (int tc = 0; tc < T; tc++) {
		cin >> N >> Dest;

		queue<DATA> block;

		d.x = N; d.cnt = 0; 
		block.push(d);

		while (!block.empty()) {
			int x1 = block.front().x;   // 레지스터 현재 저장된 값
			int cnt1 = block.front().cnt;
			
			int arr1[10001];

			for (int i = 0; i <= cnt1; i++) {
				arr1[i] = block.front().arr[i];
			}

			visit[x1] = 1;     // 수 방문 처리

			if (x1 == Dest) {    // 레지스터 내 현재 값이 목적값에 다다름
				for (int i = 0; i <= cnt1; i++) {
					cout << block.front().arr[i];
				}
				cout << endl;

				memset(arr1, 0, sizeof(arr1));    // 배열 0 으로 초기화 
				memset(visit, 0, sizeof(visit));
				break;
			}

			block.pop();

			// D연산 수행
			if (visit[D(x1)] == 0) {
				visit[D(x1)] = 1;
				d.x = D(x1);

				arr1[cnt1] = 'D';
				for (int i = 0; i <= cnt1; i++) {
					d.arr[i] = arr1[i];
				}
				d.arr[cnt1] = 'D';
				d.cnt = cnt1 + 1;
				block.push(d);
			}

			// S연산수행
			if(visit[S(x1)] == 0) {
				visit[S(x1)] = 1;
				d.x = S(x1);

				arr1[cnt1] = 'S';
				for (int i = 0; i <= cnt1; i++) {
					d.arr[i] = arr1[i];
				}

				d.cnt = cnt1 + 1;
				d.arr[cnt1] = 'S';  // S연산으로 인한 결과가 방문하지 않은 수
				block.push(d);
			}

			// L연산 수행
			if (visit[L(x1)] == 0) {     // L연산으로 인한 결과가 방문하지 않은 수
				visit[L(x1)] = 1;
				d.x = L(x1);

				arr1[cnt1] = 'L';
				for (int i = 0; i <= cnt1; i++) {
					d.arr[i] = arr1[i];
				}

				d.arr[cnt1] = 'L';
				d.cnt = cnt1 + 1;
				block.push(d);
			}

			// R연산 수행
			if (visit[R(x1)] == 0) {             // R연산으로 인한 결과가 방문하지 않은 수
				visit[R(x1)] = 1;
				d.x = R(x1);

				arr1[cnt1] = 'R';
				for (int i = 0; i <= cnt1 + 1; i++) {
					d.arr[i] = arr1[i];
				}
				d.cnt = cnt1 + 1;
				d.arr[cnt1] = 'R';
				block.push(d);

			}
		}

	}  // 테스트케이스 scope 종료
	return 0;
}




int D(int N) {   // D 연산
	visit[N] = 1; 
	N = N * 2;
	if (N >= 10000) {
		N = N % 10000;
	}
	return N;
}

int S(int N) {  // S 연산 
	visit[N] = 1; 
	N -= 1;
	if (N == 0) {
		N = 9999;
	}
	return N;
}

int L(int N) {  // Left Shift
	visit[N] = 1; 
	int ans = N;

	int r1 = N / 1000;
	ans = N - (N / 1000) * 1000;

	int r2 = ans / 100;
	ans = ans - (ans / 100) * 100;

	int r3 = ans / 10;
	ans = ans - (ans / 10) * 10;

	int r4 = ans;

	N = r2 * 1000 + r3 * 100 + r4 * 10 + r1;
	return N;
};


int R(int N) { // Right Shift
	visit[N] = 1; 
	int ans = N;

	int r1 = N / 1000;
	ans = N - (N / 1000) * 1000;

	int r2 = ans / 100;
	ans = ans - (ans / 100) * 100;

	int r3 = ans / 10;
	ans = ans - (ans / 10) * 10;

	int r4 = ans;

	N = r4 * 1000 + r1 * 100 + r2 * 10 + r3;
	return N;
};

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

문제

문제

출처

ICPC

고수님들 도와주세요 ㅠㅠㅠ(시간초과 에러 발생)

pda_pro12 6년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말