글 읽기 - 왜 틀렸는지 모르겠습니다.

p_ce1052 2년 전 0

제가 문제를 잘못 이해한건지....구현을 잘못한건지...테케도 많이 넣어봤는데 내면 1%에서 바로 틀리네요

(1) s=t라면 0출력

(2) s>t라면 s를 감소시키는 방법이 1로 가는 것 뿐이고 1에서 두배 연산과 제곱 연산만 써야하므로 t는 2의 제곱수여야 함. t가 2의 제곱수라면 그리디하게 최단경로 출력. 그렇지 않으면 -1출력

(3) s<t라면 /를 쓰지 않고 답을 만들어본다. 답을 만들 수 없으면 1로 만들고 (2)번 경우로 이동한다.

답을 만들 수 있으면 (2)번 경우와 dp로 구한 최단경로를 비교하여 더 짧은 경로 출력. 두 경로의 길이가 같다면 사전순으로 앞서는것 출력.

어디가 틀렸나요?

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<ll,ll>dp;
map<ll,ll>parent;
string aa,bb;
bool pos = 1;
void solve(ll s,ll t){
	if((t&(t-1))==0){
		if(s!=1) aa.push_back('/');
		s = 1;
		while(s!=t){
			if(s*s<=t && s!=1){
				aa.push_back('*');
				s*=s;
			}
			else{
				aa.push_back('+');
				s*=2;
			}
		}
	}
	else pos = 0;
}
int main(){
	ll s,t;
	cin>>s>>t;
	if(s==t) cout<<0;
	else{
		if(s>t){
			solve(s,t);
			if(!pos) cout<<-1;
			else cout<<aa;
		}
		else{
			queue<ll>q;
			dp[s] = 0;
			q.push(s);
			while(!q.empty()){
				ll cur = q.front();
				q.pop();
				if(cur>=t) continue;
				if(dp.find(cur*2)==dp.end()){
					dp[cur*2] = dp[cur]+1;
					parent[cur*2] = cur;
					q.push(cur*2);
				}
				if(dp.find(cur*cur)==dp.end()){
					dp[cur*cur] = dp[cur]+1;
					parent[cur*cur] = cur;
					q.push(cur*cur);
				}
			}
			if(dp.find(t)==dp.end()){
				solve(s,t);
				if(!pos) cout<<-1;
				else cout<<aa;
			}
			else{
				solve(s,t);
				while(s!=t){
					ll p = parent[t];
					if(p*p==t) bb.push_back('*');
					else bb.push_back('+');
					t = p;
				}
				reverse(bb.begin(),bb.end());
				if(!pos) cout<<bb;
				else if(aa.size()<bb.size()) cout<<aa;
				else if(aa.size()>bb.size()) cout<<bb;
				else{
					set<string>st;
					st.insert(aa);
					st.insert(bb);
					cout<<*st.begin();
				}
			}
		}
	}
}

sjyfantasy 2년 전 0

'-' 연산이 없네요.

p_ce1052 2년 전 0

s = s- s 이 연산을 수행하면 0이될텐데 0에서 빠져나오는 방법이 없지 않나요? T는 절대 0이 아니구요. 제가 뭘 잘못 이해햤을까요

sjyfantasy 2년 전 0

문제 제한사항 제대로 못 봐서 착각했네요.

-는 없어도 될 듯하네요.

주석이 없어서 글을 토대로 코드를 읽어보는데

if else if else를 나눌 필요가 없어보입니다.

하나로 합쳐도 될 것 같고...

else는 사실 로직이 이해가 안되요.

mym0404 2년 전 0

저같은 경우도 맞왜틀이였는데 마지막에 실제로 s를 정답으로 도출된 연산들을 다 해봤을때 t가 되는가 를 판단하여 통과했습니다.

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

문제

문제

출처

ICPC

왜 틀렸는지 모르겠습니다.

p_ce1052 2년 전 0

sjyfantasy 2년 전 0

p_ce1052 2년 전 0

sjyfantasy 2년 전 0

mym0404 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말