글 읽기 - c언어// 왜 틀린지 모르겠어요

saiam12 1년 전 0

예시코드는 다 맞는데 무언가 반례가 있는거 같습니다. 근데 반례가 뭔지 몰라서 혹시 찾아주시면 감사하겠습니다.

#include<stdio.h>
#include<math.h>

int main(){
	int n,k,i,j,s=0,m=0,max=0,b,total=0;
	scanf("%d %d",&n,&k);
	char a[n]; 
	scanf("%s",&a);
	for (i=0;i<n;i++){
		a[i]-='0';//자리별로 나누어주는것 만약 n=4이고 1924를 입력하였으면 a[0]=1,a[1]=9,a[2]=2,a[3]=4
	}
	j=pow(10,n-k-1);// n=4이고 k=2이면 위의 예시에서 9에 10을 곱해주고 4에 1을 곱해주기 위해 필요
	for (s=n-k;s>=1;s--){//n=4,k=2라면 십의 자리와 일의 자리를 정해주기 위해 필요
 		for (i=m;i<=n-s;i++){
			if (max<a[i]){
				max=a[i];
				b=i;
			}
		}
		m=b+1;
		total+=max*j;
		max=-1;
		j/=10;
	}
	printf("%d",total);
}

nahwasa 1년 전 0

1 ≤ K < N ≤ 500,000

이므로

j=pow(10,n-k-1);

에서 n-k-1은 최대 499998이 될 수 있습니다.

따라서 j가 제대로 표현될 수 없습니다.

saiam12 1년 전 1

10^2이라고 2자리가 아니고 3자리 인것처럼 10^499998이면 499999자리가 맞지 않나요?

nahwasa 1년 전 0

int형인 j에 10^499998 이라는 큰 수가 들어갈수가 없습니닷.

nahwasa 1년 전 0

int형은 2^31-1 까지 표현이 가능해용.

saiam12 1년 전 0

문제점을 찾은 거같은데 맞는지 봐주시길바랍니다.

지금 char형이 127까지만 저장되어서 그 이상되는건 저장할 수 없고int형이 21억인가?이므로 기껏해야 10자리여서 n=500000이고 k=1인 상황에서는 표현할 수 없는것이고 이를 해결할려면 문자을 붙이는 작업을 해주면 될 것같은데 제가 생각하는게 맞나요?

saiam12 1년 전 0

아 네네 이제 확인했네요 감사합니다

saiam12 1년 전 0

뭐 어찌어찌해서 코드작성해서 맞았습니다를 받긴 했는데

if (max==9){
break;
}

위코드가 없으니 시간초과가 나더군요.

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<math.h>

int main(){
	int n,k,i,j,s=0,m=0,max=0,b,total=0;
	scanf("%d %d",&n,&k);
	char a[n],c[n-k]; 
	scanf("%s",&a);
	for (i=0;i<n;i++){
		a[i]-='0';
	}
	for (s=n-k;s>=1;s--){
 		for (i=m;i<=n-s;i++){
			if (max<a[i]){
				max=a[i];
				b=i;
			}
			if (max==9){
				break;
			}// 이코드가 없으니 시간초과가 납니다.
		}
		m=b+1;
		sprintf(c,"%d",max);
		max=-1;
		printf("%s",c);
	}
}

saiam12 1년 전 1

혹시나 안되시는 분들을 위하여 예시를 하나 더 준비했는데

120 4
123813982189081241941284818948189498149184164271641274261231231235325345778658569776756577456452412414242343892482398389

이걸 입력하시면

83982189081241941284818948189498149184164271641274261231231235325345778658569776756577456452412414242343892482398389

위와 같은 결과가 출력되어야합니다.

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

문제

문제

출처

ICPC

c언어// 왜 틀린지 모르겠어요

saiam12 1년 전 0

nahwasa 1년 전 0

saiam12 1년 전 1

nahwasa 1년 전 0

nahwasa 1년 전 0

saiam12 1년 전 0

saiam12 1년 전 0

saiam12 1년 전 0

saiam12 1년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말