글 읽기 - 반례가 없는 것 같은데 왜 틀렸다고 뜨는지 모르겠습니다..

bje5774 2년 전 0

dp로 안 풀고 반복문으로 조합 써서 풀었는데 틀렸습니다 라고 뜨네요ㅜㅜ 반례 알려주시면 감사하겠습니다 !!

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc= new Scanner(System.in);
		int n= sc.nextInt();
		long leg[]= new long[n];
		for(int i=0; i<n; i++) {
			int west=sc.nextInt();
			int east=sc.nextInt();
			long result=1;
			
			int count=0;
			for(int j=0; j<west; j++) {
				result=result*(east-j);
			}
			
			long divide=1;
			
			for(int k=1; k<=west; k++) {
				divide=divide*k;
			}
			if(east==0||west==0) {
				leg[i]=0;
				}
			else {
				leg[i]=result/divide;
			}
		}
		for(int i=0; i<n; i++) {
			System.out.println(leg[i]);
		}
		sc.close();
	}

}

stylecoke 2년 전 0

조합을 사용하여 문제를 풀게되면 곱셈 과정에서 long타입의 범위를 넘어갈 수 있습니다.

(아래는 반례입니다.)

1
15 30

stylecoke 2년 전 2

따라서 조합을 사용하실거면 타입을 long대신 BigInteger를 사용하시는 것을 추천합니다.

	public static void main(String[] args) {
		Scanner sc= new Scanner(System.in);
		int n= sc.nextInt();
		BigInteger leg[] = new BigInteger[n];
		for(int i=0; i<n; i++) {
			int west = sc.nextInt();
			int east = sc.nextInt();
			BigInteger result = BigInteger.ONE;
			
			int count=0;
			for(int j=0; j<west; j++) {
				result=result.multiply(new BigInteger(String.valueOf(east-j)));
			}
			
			BigInteger divide = BigInteger.ONE;
			
			for(int k=1; k<=west; k++) {
				divide = divide.multiply(new BigInteger(String.valueOf(k)));
			}
			if(east==0||west==0) {
				leg[i]=BigInteger.ZERO;
			}
			else {
				leg[i]=result.divide(divide);
			}
		}
		for(int i=0; i<n; i++) {
			System.out.println(leg[i].toString());
		}
		sc.close();
	}

bje5774 1년 전 0

감사합니다..

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

문제

문제

출처

ICPC

반례가 없는 것 같은데 왜 틀렸다고 뜨는지 모르겠습니다..

bje5774 2년 전 0

stylecoke 2년 전 0

stylecoke 2년 전 2

bje5774 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말