글 읽기 - 그리디 알고리즘으로 풀었는데, 틀렸네요.

noxnia 4년 전 0

제가 세운 알고리즘은 다음과 같아요.

숫자가 1자리이거나 2자리인 경우 뒤의 수가 0인 경우엔 -1 출력

k 번 한도내 교환 실행하는 선택정렬 실행

k 가 홀수로 남은 경우, 중복된 숫자가 있는지 검사후 중복된 숫자가 없으면 아래 두 글자를 교환.

숫자 출력.

제 나름대로 생각으로는 틀림이 없다고 생각했는데 "틀렸네요" 나오네요.

#include <stdio.h>

int main()
{
	char n[8]; int k, s, d=0, i, j, t;
	scanf("%s%d",n, &k);
	if(n[1]==0||(n[2]==0&&n[1]=='0')) { puts("-1"); return 0; }
	for(i=0;n[i+1];i++)
	{
		for(s=i,j=i+1;n[j];j++) if(n[j]>=n[s]) s=j;
		if(n[s]==n[i]) continue;
		t=n[i]; n[i]=n[s]; n[s]=t;
		if(--k==0) break;
	}
	if(k&1)
	{
		for(i=1;n[i];i++) d|=(n[i-1]==n[i]); 
		if(!d) { t=n[i-1]; n[i-1]=n[i-2]; n[i-2]=t; }
	}
	puts(n);
}

noxnia 4년 전 6

1488 2

8841

이 나오겠지만,

4188 2

8814

가 나오겠네요.

이걸 해결 못 해서 이 방법은 안 되겠네요.

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

문제

문제

출처

ICPC

그리디 알고리즘으로 풀었는데, 틀렸네요.

noxnia 4년 전 0

noxnia 4년 전 6

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말