글 읽기 - 정말정말 뭐가 틀린건지 모르겠습니다. 반례 아무리생각해도없는데..

jinsu0709 5년 전 0

그리디 알고리즘을 이용했습니다.

string으로 입력받아 same이라는 int값으로 비교하는데 어차피 아스키 값으로 변환되도 크고 작음은 같으니까 무시했습니다.

1. 한자리수, 두자리수(뒷자리가 0인) 과감히 -1출력

2. 최대값이 완성되면 같은숫자가있으면 서로교환, 없으면 맨 뒷자리교환

3. 8799와 같이 9987이 답인데 9978과 같이 나올 수 있는 경우의 수를 checknum함수를 통해 제거

-> 같은 숫자가 있는경우 제일 큰값중 두개있는값을 same에 인덱스값을 sameidx에 저장 후 checknum에서 판단

생각해야될게 더있을까요?.. 왜틀렸는지 모르겠습니다.. ㅠㅠ

#include <iostream>
#include <string>
using namespace std;

string s; int n;
void swap(int a,int b)
{
	char temp=s[a];
	s[a]=s[b];
	s[b]=temp;
}

bool checknum(int a,int b)
{//같은값있을때 나보다작은게 뒤에있으면 안됌
	for(int i=a+1;i<b;i++)
	{
		if(s[a]>s[i]){ return true; } 
	}
	return false;
}

int main() {
	cin>>s>>n;
	int cnt=0,maxnum,maxidx;
	int same=0,sameidx=0;
	int len=s.length();
	int check=0,find=0;
	if(len==1 ||(len==2 && s[1]=='0')){ cout<<-1; return 0; }
	for(int i=0;i<len;i++)
	{
		for(int j=i+1;j<len;j++)
		{
			if(s[i]==s[j])
			{
				if(same<s[i])
				{ 
					same=s[i]; 
					sameidx=i;
				}
			}
		}
	}
	for(int t=0;t<n;t++)
	{
		//값이 9면 제일크므로 다음으로넘어감
		for(int i=0;i<len;i++)
		{
			if(s[i]=='9'){ continue; }
			else if(i==len-1 || find==1)
			{//끝까지 오게되면 같은숫자바꾸거나 맨뒤2개바꿈
				if(same){ break; }
				else{ swap(len-1,len-2); }
				//최대값찾음
				find=1; break;
			}
			else
			{
				maxnum=s[i+1];
				maxidx=i+1;
				//큰값 찾기
				for(int j=i+2;j<len;j++)
				{
					if(maxnum<=s[j])
					{ 
						maxnum=s[j]; 
						maxidx=j;
						if(maxnum==same  && n-t!=1)
						{//횟수가 1번남았을때 이 규칙을 쓰면 안됌
							if(checknum(i,maxidx)){ break; }
						}
					}
				}
			}
			//값바꾸기
			if(s[i]<s[maxidx]){ swap(i,maxidx); break; }
		}
	}
	cout<<s;
}

tjdwo5313 4년 전 4

반례 몇 개 들어드리겠습니다.

----------------------------

input

52676 2

answer(정답)

76652

output(글쓴이)

72566

----------------------------

input

40069 3

answer

96400

output

96040

----------------------------

input

10042 2

answer

42010

output

41002

----------------------------

input

740792 2

answer

970742

output

970472

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

문제

문제

출처

ICPC

정말정말 뭐가 틀린건지 모르겠습니다. 반례 아무리생각해도없는데..

jinsu0709 5년 전 0

tjdwo5313 4년 전 4

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말