글 읽기 - 도저히 모르겠습니다 ㅠㅠ 도와주세요 고수님들 ㅠㅠㅠ

so6275 5년 전 0

s와 t가 1억까지 가능하기때문에 이를 1억짜리 memorization하기에는 메모리가 초과되서 s와 t를 축소시킨다음에 bfs로 연산이 가능한지 확인하는식으로 구현했습니다.

몇가지 테스트케이스 계산기 돌려가면서 만들어서 다 잘 작동되길래 통과될줄 알았는데 바로 틀렸습니다 뜨네요 ㅠㅠ

어떤 예외 케이스가 있을까요 ?

어디서 틀렸을까요? ㅠㅠ

고수님들 도와주세요 ㅠㅠㅠㅠ

#include <iostream>
#include <string>
#include <queue>
#include <math.h>
using namespace std;

int target_t[100]; // t가 10000보다 클때 이것을 루트 또는 나누기2로 값을 축소시켜서 10000이하 값으로 만들어준다   
string target_s[100]; // target_t배열에 idx에 맞는 숫자가 되려면 이만큼 곱셈 또는 덧셈을 해줘야한다
int target_idx = 0; 
bool visit[10001];  // 10^4을 줄여야함
bool candoit = false; // 연산을 통해 t를 만들 수 있다면 true 아닐시 false로 -1출력
int s, t; // 입력받는 s와 t

struct pos {
	string s; // 지금까지의 연산을 저장
	int num; // 지금까지의 연산을 통해 나온값 저장
	pos(string a, int b) :s(a), num(b) {}
};

void bfs();
int checking(int num);

int main()
{
	cin >> s >> t;
	if (s == t) cout << 0; // 둘이 숫자가 같으면 0을 출력
	else if (t == 0) cout << "-"; // t가 0이라면 -를 통해 한번에 0을 만들 수 있음 (0은 * + -를 해도 0이고 /는 연산불가)
	else if (t == 1) cout << "/"; // t가 1이라면 /한번으로 출력가능
	else // 그 외의 경우
	{
		bool out = false; // s가 10000보다 클때 s에 2^n만큼 곱해서 t가 될 수 있다면
		string st = "";  // 연산 저장
		if (s > 10000) // s가 10000보다 큰 상황
		{
			for (int i = 1; i < 15; i++) // s가 10000일때, s * 2^14보다 큰 경우는 1억을 넘어가서 값 초과 / s가 10000보다 크다면 제곱할경우 1억을 초과함
			{
				if (s * (int)pow(2, i) == t) // s에 2^i을 곱해서 t를 만들 수 있다면 
				{
					out = true; // bfs를 안돌려도 됨
					for (int j = 0; j < i; j++) cout << "+"; // i만큼 덧셈 출력
					break;
				}
				else if (s*(int)pow(2, i) > 1000000000) break; // 만약 s에 2^i를 곱했을때 1억을 초과한다면 값 초과 break
			}
			if (!out) // s에 2^n만큼 곱해도 t가 될 수 없는 경우
			{
				s = 1; // 바로 s를 1로 나눠버린다
				st += "/"; //  나눗셈 연산저장
			}
		}

		if (!out) // s에 2^n만큼 곱해도 t가 될 수 없는 경우
		{
			visit[s] = true; // 해당 숫자는 방문함
			if (t > 10000) // t가 10000보다 큰 경우
			{
				int small_t; // 나누기 2로 축소시키기 위한 t
				int check_t; // 루트로 축소시키기 위한 t

				check_t = (int)sqrt(t); // t에 루트를 씌웠을 때
				if (check_t * check_t == t) // 루트씌운값을 (int)으로 변환해서 소수는 버리고 제곱했을때 같은 값이된다면 제곱가능
				{
					target_t[target_idx] = check_t; // 루트씌운 값을 넣어준다
					target_s[target_idx++] = "*"; // 연산저장
				}
				if (t % 2 == 0) // 짝수인경우  ( 홀수인경우 어차피 2로 나눠지지 않기때문에 생각하지 않아도 됨 )
				{
					string st = "+"; // 덧셈연산추가
					small_t = t / 2; // t나누기 2
					bool again = true;

					while (again)
					{
						if (small_t <= 10000) // 축소시켜서 10000보다 작아질경우 
						{
							target_t[target_idx] = small_t; // 축소시킨값을 저장
							target_s[target_idx++] = st; // 축소시켜왔던 과정 연산을 저장
							break;
						}

						check_t = (int)sqrt(small_t); // 제곱이 될 때
						if (check_t * check_t == small_t)
						{
							target_t[target_idx] = check_t;
							target_s[target_idx++] = "*" + st;
						}

						if (small_t % 2 == 1) again = false; // 홀수일때 (더이상 2로 나누기가 불가능)
						else // 짝수일때
						{
							small_t /= 2; // 또 나눠줌
							st = "+" + st; // 연산 추가
						}
					}
				}
			} // t가 10000이상일때
			else 
			{// t가 10000보다 작을때
				target_t[target_idx] = t; // 바로 해당값을 집어넣어줌
				target_s[target_idx++] = "";
			}

		} // out이 아닐때

		if (target_idx != 0) bfs(); // 축소시킨 t가 없다면 밑에서 바로 -1 출력
		if (!candoit && !out) cout << -1;  // 축소시킨 t가 없거나  / 값을 만들어서 이미 출력한 상황이 아니라면

	}	// s와 t비교문

	return 0;
}

void bfs()
{
	int push_num;
	int test_num;
	int min_len = 0;
	string out_s = ""; // 출력할 연산 및 처음상태연산
	queue<pos>q; // 연산과정과 연산후 값을 가지는 구조체 큐를 만들어줌
	q.push(pos(out_s, s)); 

	while (!q.empty()) // 큐가 빌때까지
	{
		pos cur = q.front(); 
		q.pop();

		test_num = checking(cur.num); // test_num이 -1이라면 연산을 통해서 축소시킨t 또는 t를 만들 수 없음
		if (test_num != -1) // 연산을 통해 만들 수 있음
		{
			out_s = cur.s + target_s[test_num]; // 그동안 연산과정 + 축소시켰을때 했던 연산과정을 합침
			candoit = true; // 만들 수 있음 ( 큐를 빠져나와서 main에서 -1출력 방지 )
			min_len = out_s.size(); // 이보다 빠른 연산이 가능하다면 그 연산으로 출력해야줘함
		}
		
		if (min_len != 0 && cur.s.size() + 1 >= min_len) break;	// 같은 depth기 때문에 나머지들도 전부다 똑같음
	
		// 나누기
		push_num = 1;
		if (!visit[push_num])
		{
			visit[push_num] = true;
			out_s = cur.s + "/";
			q.push(pos(out_s, push_num));
		}
		// 더하기
		push_num = cur.num * 2;
		if (push_num <= 10000 && !visit[push_num])
		{
			visit[push_num] = true;
			out_s = cur.s + "+";
			q.push(pos(out_s, push_num));
		}
		// 곱하기
		push_num = cur.num * cur.num;
		if (push_num <= 10000 && !visit[push_num])
		{
			visit[push_num] = true;
			out_s = cur.s + "*";
			q.push(pos(out_s, push_num));
		}
	}

	if (!candoit) return; // 연산을 통해 만들 수 없다면 main에서 -1출력
	else cout << out_s; // 만들 수 있다면 연산과정 출력
}

int checking(int num)
{
	for (int i = 0; i < target_idx; i++) // 축소시킨t 또는 t 와 bfs를 통해서 만들어짐 숫자가 같은지 확인
		if (target_t[i] == num) return i; // 같으면 축소시킨 t와 그 연산과정을 저장하고있는 배열에 해당 인덱스를 넘겨줌

	return -1; // 없으면 -1을 리턴
}

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

문제

문제

출처

ICPC

도저히 모르겠습니다 ㅠㅠ 도와주세요 고수님들 ㅠㅠㅠ

so6275 5년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말