글 읽기 - 2193 이친수 문제 질문 (궁금한 점)

parispoly137 5년 전 0

1시간 넘게 찾고 고민하다가 발견한 사실입니다.

이 문제를 Double 로 접근하고 DecimalFormat으로 소수점을 자르면

N이 79일 때부터 답이 틀립니다. (피보나치 수가 답이라 따로 계산해봤습니다.)

N을 90 이상으로 큰 수를 넣으니까 0이 계속해서 생겨나던데, 왜 이런건가요?

Double 을 long 으로 바꾸고 DecimalFormat을 빼니 답은 맞았습니다만, 궁금합니다.

p.s. 그리고 제가 짠 이 코드가 간결한 편인지, 더 간결하게 할 수 있는지도 가르쳐 주시면

감사하겠습니다! (항상 같은 방식인 것 같은데, 저와 다른 사람들도 있어서..)

import java.util.Scanner;
import java.text.DecimalFormat;
 
public class Main{
 
	public static double[][] dp;
 
	public static void main(String[] args){
		Scanner sc=new Scanner(System.in);
		int N=sc.nextInt();
 
		dp=new double[N+1][2];
		dp[1][1]=1.0;
 
		double sum=two(N,0)+two(N,1);
 
		DecimalFormat df = new DecimalFormat("#.#");
		String str = df.format(sum);
 
		System.out.print(str);
	}
	public static double two(int N, int L){
		if(N==1 && L==0) return 0;
		if(dp[N][L]>0) return dp[N][L];
		if(L==0){
			dp[N][L]=two(N-1,0)+two(N-1,1);
		} else {
			dp[N][L]=two(N-1,0);
		}
		return dp[N][L];
	}
}

djm03178 5년 전 0

http://thrillfighter.tistory.c... 을 읽어보세요.

parispoly137 5년 전 0

정확히 이해하지는 못했지만 요점은 '표현 가능한 자리수를 넘어가면 0 으로 표기한다. 이 때문에 double형을 사용하는 것이 효율적이다.' 아닌가요?

그런데 double 일 때 오류가 발생하고 오히려 더 낮은 범위인 long 을 사용하면 정답이 맞습니다.

위 링크에 있는 글과는 다른 쪽 문제인 것 같습니다..

djm03178 5년 전 1

아닙니다. 이 "표현 가능한 자리수"가 작기 때문에 그 이상의 자리수는 "정확하게" 표현이 불가능하다는 것이 그 글의 요점입니다.

double은 long보다 표현 가능한 "범위"는 넓지만 "유효숫자"가 적기 때문에 long이 나타낼 수 있는 모든 정수를 정확하게 나타내는 것이 불가능합니다. 쉽게 말해서, long과 double 모두 8바이트씩을 가지고 있는데 long은 오로지 가수부만 가지고 있는 거고, double은 지수부를 위해 이 중 일부를 할애해줘야 하기 때문에 정확성이 떨어지고 대신에 표현 가능한 범위를 늘어나는 것입니다.

djm03178 5년 전 1

저 글에서 double을 쓰는 것이 좋다는 건 float에 비해 낫다는 것이지, 8바이트 정수형이 나타낼 수 있는 값을 모두 나타내고도 남는다는 뜻이 아닙니다.

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

문제

문제

출처

ICPC

2193 이친수 문제 질문 (궁금한 점)

parispoly137 5년 전 0

djm03178 5년 전 0

parispoly137 5년 전 0

djm03178 5년 전 1

djm03178 5년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말