글 읽기 - 혹시 데이터에 문제가 있나요 ??? ...

wowoto9772 7년 전 0

다음은 AC 받은 cpp 코드 입니다.

#include <cstdio>
#include <iostream>
 
using namespace std;
using ll = unsigned long long;
 
ll t[36];
 
int main(){
 
    int n;
    cin >> n;
 
    t[0] = 1LL;
 
    for(int i=1; i<=n; i++){
        for(int j=0; j<i; j++){
            t[i] += t[j] * t[i-1-j];
        }
    }
 
    cout << t[n] << endl;
 
}

wowoto9772 7년 전 0

다음은 WA받은 자바 코드 입니다.

import java.math.BigInteger;
import java.util.Scanner;
 
public class Main {
 
    public static void main(String[] args) {
         
        Scanner s = new Scanner(System.in);
         
        int n = s.nextInt();
        BigInteger t[] = new BigInteger[n+1];
        t[0] = BigInteger.ONE;
        for(int i=1; i<=n; i++){
            t[i] = BigInteger.ZERO;
            for(int j=0; j<i; j++){
                t[i] = t[i].add(t[j].multiply(t[i-1-j]));
            }
        }
        System.out.println(t[n].toString());
         
    }
 
}

wowoto9772 7년 전 0

저는 이 두 코드가 같다고 생각하는데,

왜 WA를 받은 걸까요 ......

납득이 안갑니다 ㅠㅠ

codeonwort 7년 전 0

1. n = 0에서 35까지 돌려본 결과 C++ 코드와 Java 코드의 출력이 같습니다.

2. 자바 코드를 아래와 같이 고쳐봤는데 런타임 에러가 났습니다. (배열 out of bounds로 추정)

3. 배열 크기를 36을 100으로 바꿨더니 통과하였습니다.

그런데 이 코드는 n = 36에서 오버플로우가 일어나 음수가 출력됩니다. 만약 n >= 36인 데이터가 있다면 오답이 떠야 하는데.. 되게 신비한 현상이네요.

import java.math.BigInteger;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner s = new Scanner(System.in);

        int n = s.nextInt();
        long t[] = new long[36];
        t[0] = 1;
        for(int i=1; i<=n; i++){
            t[i] = 0;
            for(int j=0; j<i; j++){
                t[i] += t[j] * t[i-1-j];
            }
        }
        System.out.println(t[n]);

    }

}

wowoto9772 7년 전 0

그쵸 ...

저도 씨플플로 낸 코드가 틀렸는데,

혹시나 해서 늘려봤더니 맞더라구요 ...

오버 플로우가 나는 데이터가 있다는 이야긴거같은데.. ㅠ

codeonwort 7년 전 0

배열 크기가 39 이하면 런타임 에러, 40 이상이면 정상 통과하는 것을 확인했습니다. BigInteger 배열 크기도 40으로 잡으면 통과하네요.

그런데 왜 배열 크기를 n+1로 잡으면 오답인지 모르겠어요.

import java.math.BigInteger;
import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner s = new Scanner(System.in);

        int n = s.nextInt();
        BigInteger t[] = new BigInteger[40];
        t[0] = BigInteger.ONE;
        for(int i=1; i<=n; i++){
            t[i] = BigInteger.ZERO;
            for(int j=0; j<i; j++){
                t[i] = t[i].add(t[j].multiply(t[i-1-j]));
            }
        }
        System.out.println(t[n].toString());

    }

}

codeonwort 7년 전 1

n > 35인 입력이 있었고, 그 때의 답이 오버플로우가 발생한 값이었습니다.

이 답이 BigInteger를 써서 제대로 계산한 값과 달라서 오답이였던 것으로 밝혀졌습니다.

재채점되서 질문자님 코드도 제 코드도 모두 통과됐네요.. ㅋㅋ

wowoto9772 7년 전 0

해피엔드!

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

문제

문제

출처

ICPC

혹시 데이터에 문제가 있나요 ??? ...

wowoto9772 7년 전 0

wowoto9772 7년 전 0

wowoto9772 7년 전 0

codeonwort 7년 전 0

wowoto9772 7년 전 0

codeonwort 7년 전 0

codeonwort 7년 전 1

wowoto9772 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말