글 읽기 - 1398 동전문제 몇달동안 고민하다가 못풀겠습니다

rupitere 8년 전 0

여러가지 방법으로 시도했지만 다 틀렸습니다.

재귀로 풀었더니 시간초과가 뜨고

이번에는 다른방법으로 풀었습니다.

자리를 두자리씩 나누어서

2자리의 십진수로 최소의 동전의 갯수를 구하게 만들었습니다.

만약 길이가 홀수라면 앞에숫자는 그냥 동전의 갯수에 더하고 나머지를 두개씩 세도록 만들었습니다.

맞다고 생각하는데 계속 틀렸습니다.가 뜨네요

어떤 예외가 있을까요?

#include <stdio.h>
 
 
 
 
 
int main(){
	
	
	int length = 0;
	int index =0;
	int i,j,k;
	int count = 0;
	int flag =0;
	
	int num;
	
	scanf("%d",&num);
	
	char arr[num][16];
	
	for(i=0;i<num;i++){
		scanf("%s",arr[i]);	
	}
	
	
	for(i=0;i<num;i++){
		while(1){
		if(arr[i][length]=='\0') break;
		length++;
		}
	
		//printf("length %d\n",length); 
		while(index<length){
		if(length%2!=0 && flag ==0){
			flag = 1;
			count += arr[i][index] -'0';
			index++;
			continue;
		}
		
		int front = (arr[i][index] -'0') * 10;
		int behind = arr[i][index+1]-'0';
		int sum = front + behind;
		
		
	
	
	
	return 0;
}

movie_jo 8년 전 0

일단 차값이 10^15 보다 작거나 같은 자연수입니다

int는 최대

2147483647 까지 되고

저 값은

1000000000000000 까지 받아서 다 수용할수 없어요

결론 : long long 쓰세요

yukariko 8년 전 1

위에 godvie_jo 님 말씀대로 char형의 배열로 받지말고 long long 형으로 받으면 int처럼 사용할 수 있습니다.

그리고 이 문제는 동전 DP 문제를 응용해야하기때문에 동전 DP문제를 먼저 해결해보신 다음에 고민하는것을 추천합니다.

rupitere 8년 전 0

long long 을 이용하여 dp로 풀었다가 시간초과가 나서 다른방식으로 풀어봤습니다.

char형으로 받은후

25는 100 자리 씩으로 증가함으로 두자리씩 만의 예외처리만 정확히 해준다면 답이 나올 것 같아서 저렇게 코드를

구성해봤습니다.

혹시 저기서 다른 예외가 있을까 싶은데...

제 생각에는 없다고 생각이 되어서요ㅠㅠ

dp로 푸는게 맞다면 그렇게 풀어보겠습니다.

답변 감사합니다.

yukariko 8년 전 2

아마 생각하시는건 틀리지않았다고 생각합니다

1 10 25 / 100 1000 2500 / 10000 100000 250000 / ...

을 잘생각해보면 답을 찾으실지도

dp를 구하는 과정에서 틀렸을수도있구요

rupitere 8년 전 0

dp말고 저 방법으로 풀었네요 ㅎㅎㅎㅎㅎㅎㅎㅎㅎ 친절한 답변 감사합니다.

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

문제

문제

출처

ICPC

1398 동전문제 몇달동안 고민하다가 못풀겠습니다

rupitere 8년 전 0

movie_jo 8년 전 0

yukariko 8년 전 1

rupitere 8년 전 0

yukariko 8년 전 2

rupitere 8년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말