[JAVA] 백준 1010 : 다리놓기

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

1010번: 다리 놓기

진짜 열받는 문제다.

왜 자바는 정수 최대가 long뿐일까

long넘어가면 BigInteger로 풀어줘야하고, 그럼 단순사칙연산조차 함수로 해줘야한다.

매번 구글링하다 그냥 이번에 주요 함수 정리하자 맘먹고 해버렸다.

https://2hiidevdang.tistory.com/27

[JAVA] BigInteger 함수 정리

---

import java.util.*;
import java.util.stream.*;
import java.math.BigInteger;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt();
		int[] N = new int[T];
		int[] M = new int[T];
		BigInteger[] rst = new BigInteger[T];
		
		//input
		for(int i = 0; i<T; i++) {
			N[i] = sc.nextInt();
			M[i] = sc.nextInt();
			if (M[i] > N[i]) {
				int temp = M[i];
				M[i] = N[i];
				N[i] = temp;
			}
		}
		
		//combination
		for (int i  = 0; i<T; i++) {
			if(N[i] == M[i]) {
				rst[i] = new BigInteger("1");
			}else {
				BigInteger n = new BigInteger(String.valueOf(N[i]));
				BigInteger m = new BigInteger(String.valueOf(M[i]));
//				BigInteger top = factorial(n);
				rst[i] = factorial(n).divide(factorial(m)).divide(factorial(n.subtract(m)));
				
			}
			
		}
		
		//output
		for (int i  = 0; i<T; i++) {
			System.out.println(rst[i]);
			
		}
		
	}
	
	public static BigInteger factorial (BigInteger n) {
		BigInteger one = new BigInteger("1");
		if (!n.equals(one)) {
			return n.multiply(factorial(n.subtract(one)));
		} else {
			return one;
		}
	}

}

사용된 알고리즘 보니까 다이나믹 프로그래밍 이다.

많이 풀어보지는 않았는데, '다이나믹 프로그래밍'을 써야하는 문제는 8할정도는 BigInteger로 유도되는 것 같다. 진짜 귀찮아 죽겠다. 다른 방법이 있나ㅠ

다이나믹 프로그래밍: 문제를 여러 하위 문제로 나눠 해결하는 알고리즘 설계 기법

= 재귀함수 쓰셈?

동치인가.

---

문제는 단순히 '조합을 풀어라'라서 쓸것도 없지만, 시간초과때문에 그지같았다.

느낌상 BigInteger남발하면 또 메모리 초과날거같아서 최대한 int로 이끌 수 있는 놈들은 int로 써봤다. 

중간중간 조건문들은 

1. 조합의 n이 r보다 더 작을경우 swap

2. n == r 일때는 1로 받기

하려고 썼다. 근데 2번은 굳이 조건문으로 안써도 뭔가 더 간단하게 할수도 있지않을까.