글 읽기 - 가능한 모든 입력 범위에서 출력이 맞는데 틀렸습니다

yhkee0404 4년 전 0

제가 두 코드를 제출하였는데, 하나는 맞았고 하나는 틀렸습니다.

그런데 이 두 코드는 가능한 모든 입력 범위에서 같은 출력을 냅니다.

가능한 모든 입력 범위는 양의 정수 n (1 ≤ n ≤ 100,000)입니다.

왜 틀렸을까요?

실제로 제가 제출한 두 코드와 채점 결과를 다음에서도 확인하실 수 있습니다.

https://www.acmicpc.net/status...

#include <cstdio>
#include <climits>

#define MOD 16769023

int main ( void ) {
	long i = 0 ;
	
	long n = 0 ;
	scanf ( "%ld" , & n ) ;

	long long num_prev [ 3 ] = { 0 } ;
	long long num_next [ 3 ] = { 0 , 1 , 1 } ;
	for ( i = 1 ; i < n ; i ++ ) {
		int j = 0 ;
		for ( j = 0 ; j < 3 ; j ++ ) {
			num_prev [ j ] = num_next [ j ] ;
		}
		unsigned long long sum = 0 ;
		sum = num_prev [ 1 ] + num_prev [ 2 ] ;
		if ( sum > LLONG_MAX ) {
			num_next [ 0 ] = sum % MOD ;
		} else {
			num_next [ 0 ] = sum ;
		}
		num_next [ 1 ] = num_prev [ 0 ] ;
		num_next [ 2 ] = num_prev [ 0 ] ;
	}
	unsigned long long sum = 0 ;
	for ( i = 0 ; i < 3 ; i ++ ) {
		sum += num_next [ i ] ;
		if ( sum > LLONG_MAX ) {
			sum %= MOD ;
		}
	}
	if ( sum >= MOD ) {
		printf ( "%llu" , sum % MOD ) ;
	} else {
		printf ( "%llu" , sum ) ;
	}
	return 0 ;
}
/*
실제 제출한 코드에는 이 주석이 없습니다.
다만 다음 코드는 제가 실제 제출하여 맞은 코드로서,
가능한 모든 입력 범위에서 위의 틀린 코드와 출력이 같습니다.
가능한 모든 입력 범위는 양의 정수 n (1 ≤ n ≤ 100,000)입니다.
#include <cstdio>
#include <climits>

#define MOD 16769023

int main ( void ) {
    long i = 0 ;
    
    long n = 0 ;
    scanf ( "%ld" , & n ) ;

    long num_prev [ 3 ] = { 0 } ;
    long num_next [ 3 ] = { 0 , 1 , 1 } ;
    for ( i = 1 ; i < n ; i ++ ) {
        int j = 0 ;
        for ( j = 0 ; j < 3 ; j ++ ) {
            num_prev [ j ] = num_next [ j ] ;
        }
        long sum = 0 ;
        sum = num_prev [ 1 ] + num_prev [ 2 ] ;

        num_next [ 0 ] = sum % MOD ;
        num_next [ 1 ] = num_prev [ 0 ] ;
        num_next [ 2 ] = num_prev [ 0 ] ;
    }
    long sum = 0 ;
    for ( i = 0 ; i < 3 ; i ++ ) {
        sum += num_next [ i ] ;
        sum %= MOD ;
    }
    if ( sum >= MOD ) {
        sum %= MOD ;
    }
    printf ( "%ld" , sum ) ;

    return 0 ;
}
*/

clrmt 4년 전 1

LLONG_MAX가 뭔진 모르지만 이걸 초과할 수 있을까요? 저걸 MOD로 고치니 맞다고 뜹니다.

yhkee0404 4년 전 0

감사합니다, clrmt님 덕분에 LLONG_MAX의 값을 다른 값으로 바꾸어 보면서해결할 수 있었어요.

LLONG_MAX는 2^63 - 1 인데, 그 절반 정도 되는 2^62 - 1 로 바꾸니 맞다고 뜨고, 2^62 로 바꾸니 틀렸다고 떴습니다.

문제는 20번째 라인인 sum = num_prev [ 1 ] + num_prev [ 2 ] ; 에서

( unsigned long long ) = ( long long ) + ( long long ) 였습니다.

그래서 두 ( long long ) 의 합이 LLONG_MAX 보다 큰 값이 될 때 overflow가 발생했어요.

이를 ( unsigned long long ) = ( unsigned long long ) + ( long long ) 으로 형변환 해 주고 더하니까,

이제는 LLONG_MAX의 값을 다른 값으로 안 바꾸고도, 원래의 LLONG_MAX인 2^63 - 1 에서도 맞았습니다.

제 컴파일러에서는 웬일인지 overflow가 발생하지 않아서 출력이 같았네요..

감사합니다!

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

문제

문제

출처

ICPC

가능한 모든 입력 범위에서 출력이 맞는데 틀렸습니다

yhkee0404 4년 전 0

clrmt 4년 전 1

yhkee0404 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말