[백준/BOJ] 1010번 : 다리 놓기 (JAVA / 자바)

안녕하세요~ 코딩하는 코알못 코메인입니다.

 

 

https://www.acmicpc.net/problem/1010

1010번: 다리 놓기

---

- 문제 -

 

난이도 실버 5 문제이다.

자바에서 입력방식은 scanner와 bufferedreader가 있다.

자바를 초반에 접하면 처음에 배우는 입력은 scanner이다. scanner가 bufferedreader보다 편하지만 속도가 느리다.

bufferedreader는 무조건 문자열로 받아오기때문에 정수형이나 실수형 변수에 저장하기 위해서는 입력과 형변환을 해줘야한다.

더 자세한 내용은 아래 글 참고 하면 좋다.

https://comain.tistory.com/3

(JAVA / 자바) Scanner 와 Bufferedreader

 

풀이 방법

조합공식 nCr을 사용하자. nCr이란 간단하게 말하면 n부터 (n-1) (n -2) ... r개만큼 다 곱한다음, 1부터 (1+1)(1+2)... r개만큼 다 곱한 것을 나눠주는 것이다.

예를 들어 보자. n= 5, r = 3이면 5C3인데 계산은 5*(5-1)*(5-2) / 1*(1+1)*(1+2) 보면 알겠지만 r이 3이기 때문에 3개씩만 계산해주면 된다. 저렇게 계산하면 5*4*3 = 60, 1*2*3 = 6, 60 / 6 = 10, 즉 5C3은 10이 된다. 

이제 이걸 문제 푸는데 넣어주면 되는데 입력 값을 보면 N M이 입력되면 N이 더 작은 수가 온다. 하지만 조합공식에서는 nCr에서 n이 r보다 커야한다. 그냥 바로 NCM을 해버리면 답이 나오질 않는다. 그러니 잘 생각해서 공식을 짤때 MCN으로 연산이 되게 짜준다.

이번 문제를 풀면서 조심해야 할 부분이 있는데 그것은 자료형이다. 정수형이 int가 오게되면 연산 과정에서 범위를 넘어서 버린다. long형도 마찬가지로 나누기 전 곱하는 과정에서 넘어버릴 것이다. 그렇기에 위 방식대로 곱하고 나누려서 BigInteger를 사용해야한다.

하지만 어짜피 곱하고 나누는 과정은 꼭 다 곱하고 나눌 필요는 없다 그저 어느 수를 곱하고 어느 수를 나눌지만 맞는다면 순서는 상관 없는 것이다. 그러니 하나를 곱하면 하나를 나눠주면 long으로도 충분히 처리가 된다. 일단 방식은 둘다 올려줄테니 보시고, 참고하길 바란다.

코드로 보자.

 

---

-풀이-

BigInteger 사용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.math.BigInteger;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		for(int i = 0; i < T; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			BigInteger N = new BigInteger(st.nextToken());
			BigInteger M = new BigInteger(st.nextToken());
            //result는 연산값을 저장해줄 것인데 처음에 곱하기때문에 1로 선언해준다.
			BigInteger result = new BigInteger("1");
			
            //N번 반복하는 반복문을 만들어준다. N.intValue는 int형인 j와 크기 비교를 하기 위해 int로 형변환 시켜줬다.
			for(int j = 0; j < N.intValue(); j++) {
                //BigInteger 연산
				result = result.multiply(M.subtract(BigInteger.valueOf(j)));
			}
			for(int j = 1; j <= N.intValue(); j++) {
				result = result.divide(BigInteger.valueOf(j));
			}
			System.out.println(result);
		}
	}

}

 

long사용

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		
		for(int i = 0; i < T; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			long N = Long.parseLong(st.nextToken());
			long M = Long.parseLong(st.nextToken());
			//result는 연산값을 저장해줄 것인데 처음에 곱하기때문에 1로 선언해준다.
			long result = 1;
			
			//곱하고 나누기를 반복할때마다 처리해준다.
			//나누기 처음 값은 1이지만 반복문은 j가 0부터 시작하기 때문에 +1을 해준다.
			for(int j = 0; j < N; j++) {
				result *= (M - j);
				result /= (j + 1);
			}
			System.out.println(result);
		}
	}

}

 

---

-결과-

BigInteger 사용한 방법

long 사용한 방법

---

아직 코딩 공부가 부족한 필자라 설명과 풀이 방법이 많이 미흡할 수 있다. 코딩 고수분들은 보시고 문제점이 있다면 댓글로 말해주시면 감사한 마음으로 참고 수정 하겠습니다.