[백준] 1010번 : 다리 놓기 - JAVA [자바]
1010번: 다리 놓기
입력의 첫 줄에는 테스트 케이스의 개수 T가 주어진다. 그 다음 줄부터 각각의 테스트케이스에 대해 강의 서쪽과 동쪽에 있는 사이트의 개수 정수 N, M (0 < N ≤ M < 30)이 주어진다.
www.acmicpc.net
-
문제
문제만 제대로 이해한다면 쉽게 풀 수 있는 문제다.
- 알고리즘 [접근 방법]
문제는 매우 간단하다.
우선 문제에서 두 가지 포인트를 짚고 넘어가보자.
1. 한 사이트에는 한 개의 다리만 놓일 수 있다.
2. 서로 다른 다리가 겹치면 안된다.
즉, 위 그림처럼 첫 번째 같이 서로 겹치지 않게 다리를 놓는 경우 외엔 한 사이트에 두개의 다리가 놓이거나, 서로 다른 다리가 가로지르면 안된다.
그럼 무엇을 생각할 수 있을까?
일단 N ≤ M 에서 최대한 많은 다리를 놓기 위해서는 N개의 다리가 필요하고, M개에서 다리를 놓을 포인트를 정해야한다. M개 중 N개를 선택해야 한다는 뜻이다.
M개에서 N개를 선택.. 서로 중복되면 안된다..
바로 '조합 공식'이다!
흔히 서로 다른 n개에서 r개를 뽑는 것을 nCr 공식이라고 한다. 즉, 위에서 주어지는 N과 M은 M개에서 N개를 뽑는 것이기 때문에 mCn이 된다.
"중복 없이 뽑는 것은 이해하겠는데, 다리가 교차되면 어떻게 되나요..?"
이렇게 생각할 수도 있지만, 일단 결론부터 말하자면 상관 없다.
잘 생각해보자 조합은 순서를 고려하지 않는다.
예로들어 (1, 2, 3, 4, 5) 에서 (1, 3, 4) 를 뽑았다고 해보자. 이는 (3, 1, 4)이나, (3, 4, 1) 등 순서가 다르게 뽑혀도 조합은 뽑는 순서를 고려하지 않기 때문에 모두 1개의 경우로 보는 것이다.
아래 사진을 보자.
왼쪽의 경우는 놓을 수 없고, 오른쪽의 경우는 다리 놓기가 가능하다.
여기서 각 사이트에 연결된 포인트는 같은 걸 볼 수 있다.
왼쪽의 경우는 오른쪽 사이트에서 (3, 1, 4)가 뽑힌 것이고, 오른쪽의 경우는 (1, 3, 4)가 뽑혔다고 할 수 있다.
하지만, 조합의 경우는 이 둘 다 '하나의 경우'로 보기 때문에 결국 조합공식을 사용하면 서로 다른 다리가 겹치는 경우는 제외될 수 밖에 없다.
그럼 조합공식을 사용하는 것을 확인했으니, 조합공식을 어떻게 짜야하는지만 남았다. 이건 이미 한 번 필자가 다뤘던 내용이라 아래 포스팅을 보고 오면 좋을 것 같다.
[백준] 11050번 : 이항 계수 1 - JAVA [자바]
www.acmicpc.net/problem/11050 11050번: 이항 계수 1 첫째 줄에 \(N\)과 \(K\)가 주어진다. (1 ≤ \(N\) ≤ 10, 0 ≤ \(K\) ≤ \(N\)) www.acmicpc.net 문제 알고리즘 [접근 방법] 이항 계수(Binomial coefficie..
st-lab.tistory.com
여기서 조합공식에 대해 상세히 다루고 있기 때문에 꼭 보고오시길 바란다. 위 포스팅에서 '알고리즘 3' 을 쓸 것이다. 무슨말인가 하면, 조합공식은 아래와 같다.
하지만, 여기서 r, n, (n-r) 의 팩토리얼 값을 각각 구하는 것이 아닌, 조합의 성질을 이용하여 변형한 식을 이용하겠다는 것이다.
참고로 조합공식의 성질을 이용하는 부분은 아래 더보기를 통해 짧게 첨부하도록 하겠다.
[1번 성질]
이 공식은 워낙 유명한 공식이라 다 알 것이다. 만약 모른다 하더라도, 파스칼의 삼각형을 생각하면 바로 이해할 수 있다. 그리고 위 식을 좀 더 간단하게 쓴다면 아래와 같이 쓸 수 있다.
만약 n과 r의 이항계수를 구한다면 이렇게 나타내질 것이다.
위 점화식을 흔히 '파스칼의 법칙'이라 한다.
[2번 성질]
그리고 추가로 n과 r이 같거나, r=0 이라면 1이라는 것은 자명하다. 즉, 다음과 같은 식을 만족한다.
좀 더 간단하게 표현하면 다음과 같다.
위 두 성질을 이용하여 알고리즘을 짜보자면 다음과 같이 하나의 식으로 완성할 수 있다.
<알고리즘 2>
main {
print(combi(n, r));
}
int combi(int n, int r) {
// 2번 성질
if(n == r || r == 0) {
return 1;
}
// 1번 성질
return combi(n - 1, r - 1) + combi(n - 1, r);
}
위와 같이 각각의 팩토리얼을 구하는 방식이 아닌 하나의 식으로 재귀를 통해 완성할 수 있다.
즉, 아래의 성질 1번과
성질 2번
이 두가지를 이용하며, 메모이제이션(Memoization)을 이용하여 동적계획법으로 활용하면 이렇다.
즉, 다음과 같이 탐색과정을 코드를 짤 수 있다.
int[][] dp = new[30][30]; // 최대입력값이 29이므로
main() {
int T = input(); // 반복횟수
for(int i = 0; i < T; i++) {
int N = input();
int M = input();
// M개중 N개를 뽑는 경우이므로 nCr 에서 n = M, r = N이다.
print(combi(M, N));
}
}
int combi(int n, int r) {
// 이미 탐색했던 경우 바로 반환
if(dp[n][r] > 0) {
return dp[n][r];
}
// 2번 성질
if(n == r || r == 0) {
return dp[n][r] = 1;
}
// 1번 성질
return combi(n - 1, r - 1) + combi(n - 1, r);
}
이를 토대로 이제 출력과 몇 가지 소스만 만들어주면 된다. (사실 위 참고 링크를 보고 오셨다면 아마 금방 풀으셨을 것이다.)
만약 bottom-up 방식으로 풀이하고자 한다면 아래와 같이 활용하면 된다.
main() {
int[][] dp = new int[30][30];
// 2번 성질 (n == r, r == 0)
for (int i = 0; i < 30; i++) {
dp[i][i] = 1;
dp[i][0] = 1;
}
for (int i = 2; i < 30; i++) {
for (int j = 1; j < 30; j++) {
// 1번 성질
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
}
}
int T = input(); // 테스트케이스
for(int i = 0; i < T; i++) {
// M개중 N개를 뽑는 경우이므로 nCr 에서 n = M, r = N이다.
int N = input(); // N = r
int M = input(); // M = n
print(dp[M][N]);
}
}
- 4가지 방법을 사용하여 풀이한다.
BufferedReader와 Scanner을 사용하여 각 입력방식에 따른 성능 차이를 볼 것이다. 그리고, 각 입력에 따라 재귀 방식과 반복문 방식을 사용하여 각 알고리즘의 차이도 보려 한다.
출력은 모두 StringBuilder 로 통일하여 입력방법만 달리하여 풀이하겠다.
1. Scanner + 재귀
2. Scanner + 반복문
3. BufferedReader + 재귀
4. BufferedReader + 반복문
- 풀이
- 방법 1 : [Scanner + 재귀]
import java.util.Scanner;
public class Main {
static int[][] dp = new int[30][30];
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int T = in.nextInt();
StringBuilder sb = new StringBuilder();
for(int i = 0; i < T; i++) {
// M개중 N개를 뽑는 경우이므로 nCr 에서 n = M, r = N이다.
int N = in.nextInt(); // N = r
int M = in.nextInt(); // M = n
sb.append(combi(M, N)).append('\n');
}
System.out.println(sb);
}
static int combi(int n, int r) {
// 이미 풀린 경우 바로 반환
if(dp[n][r] > 0) {
return dp[n][r];
}
// 2번 성질
if(n == r || r == 0) {
return dp[n][r] = 1;
}
// 1번 성질
return dp[n][r] = combi(n - 1, r - 1) + combi(n - 1, r);
}
}
가장 기본적인 방법이라 할 수 있겠다.
- 방법 2 : [Scanner + 반복문]
재귀 방식이 아닌 반복문, 즉 bottom-up 방식으로 풀어내는 방식이다. 다만 테스트 케이스가 한 개가 아니기에 사전에 미리 모든 경우의 수를 구해놓는 방식을 선택했다.
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int[][] dp = new int[30][30];
// 2번 성질 (n == r, r == 0)
for (int i = 0; i < 30; i++) {
dp[i][i] = 1;
dp[i][0] = 1;
}
for (int i = 2; i < 30; i++) {
for (int j = 1; j < 30; j++) {
// 1번 성질
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
}
}
int T = in.nextInt();
StringBuilder sb = new StringBuilder();
for(int i = 0; i < T; i++) {
// M개중 N개를 뽑는 경우이므로 nCr 에서 n = M, r = N이다.
int N = in.nextInt(); // N = r
int M = in.nextInt(); // M = n
sb.append(dp[M][N]).append('\n');
}
System.out.println(sb);
}
}
- 방법 3 : [BufferedReader + 재귀]
방법 1에서 입력 방식을 Scanner 대신 BufferedReader 을 사용하여 풀이하는 방법이다. 단, BufferedReader 는 문자열을 한 줄로 읽기 때문에 N과 M을 구분하기 위해 공백을 기준으로 문자열을 분리해주어야하니 StringTokenizer 을 사용하여 풀도록 하겠다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main {
static int[][] dp = new int[30][30];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
StringTokenizer st;
StringBuilder sb = new StringBuilder();
for(int i = 0; i < T; i++) {
st = new StringTokenizer(br.readLine(), " ");
// M개중 N개를 뽑는 경우이므로 nCr 에서 n = M, r = N이다.
int N = Integer.parseInt(st.nextToken()); // N = r
int M = Integer.parseInt(st.nextToken()); // M = n
sb.append(combi(M, N)).append('\n');
}
System.out.println(sb);
}
static int combi(int n, int r) {
// 이미 풀린 경우 바로 반환
if(dp[n][r] > 0) {
return dp[n][r];
}
// 2번 성질
if(n == r || r == 0) {
return dp[n][r] = 1;
}
// 1번 성질
return dp[n][r] = combi(n - 1, r - 1) + combi(n - 1, r);
}
}
- 방법 4 : [BufferedReader + 반복문]
BufferedReader을 사용하면서 반복문으로 풀이하는 방법이다. 알고리즘은 크게 달라질 것이 없기 때문에 그리 어렵지는 않을 것이다.
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[][] dp = new int[30][30];
// 2번 성질 (n == r, r == 0)
for (int i = 0; i < 30; i++) {
dp[i][i] = 1;
dp[i][0] = 1;
}
for (int i = 2; i < 30; i++) {
for (int j = 1; j < 30; j++) {
// 1번 성질
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
}
}
int T = Integer.parseInt(br.readLine());
StringTokenizer st;
StringBuilder sb = new StringBuilder();
for(int i = 0; i < T; i++) {
st = new StringTokenizer(br.readLine(), " ");
// M개중 N개를 뽑는 경우이므로 nCr 에서 n = M, r = N이다.
int N = Integer.parseInt(st.nextToken()); // N = r
int M = Integer.parseInt(st.nextToken()); // M = n
sb.append(dp[M][N]).append('\n');
}
System.out.println(sb);
}
}
- 성능
채점 번호 : 25405680 - 방법 4 : BufferedReader + 반복문
채점 번호 : 25405668 - 방법 3 : BufferedReader + 재귀
채점 번호 : 25405660 - 방법 2 : Scanner + 반복문
채점 번호 : 25405654 - 방법 1 : Scanner + 재귀
입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다. 알고리즘 차이는 거의 없는듯...
- 정리
조합 공식과 조합을 활용할 줄만 안다면 이 번 문제는 딱히 어려운 점은 없었을 것이다. 만약 하나하나 팩토리얼 값을 구한다면 20!만 되어도 long범위를 넘어가기 떄문에 BigInteger 클래스를 사용해야하는 번거로움이 있기에.. 어지간해서는 위와같이 조합공식을 활용하는 것이 좋다.
'JAVA - 백준 [BAEK JOON] > 정수론 및 조합론' 카테고리의 다른 글
| [백준] 1934번 : 최소공배수 - JAVA [자바] (0) | 2021.01.17 |
|---|---|
| [백준] 2004번 : 조합 0의 개수 - JAVA [자바] (14) | 2020.11.07 |
| [백준] 1676번 : 팩토리얼 0의 개수 - JAVA [자바] (27) | 2020.11.05 |
| [백준] 9375번 : 패션왕 신해빈 - JAVA [자바] (9) | 2020.11.04 |
| [백준] 11051번 : 이항 계수 2 - JAVA [자바] (12) | 2020.10.30 |