안녕하세요. 오늘은 백준의 1010. 다리놓기 문제를 풀어보겠습니다.
1. 문제 링크
https://www.acmicpc.net/problem/1010
2-1. 문제 풀이 - 1차 (틀린 문제풀이)
✔️ 풀이 착안
문제를 찬찬히 읽어본 후, 중/고등학생 때 흔히 풀었던 경우의 수 문제와 비슷하다는 생각이 들었습니다. "1) 30명의 학생 중 3명의 임원을 뽑는 경우"와 "2) 30명의 학생 중 회장, 부회장, 서기를 뽑는 경우"의 차이점을 다들 아실겁니다. 1번은 30C3으로 구하면 되고, 2번은 30P3으로 구하면 되는데요, 이 문제는 두 가지 경우 중 1) 30명의 학생 중 3명의 임원을 뽑는(조합 이용) 방식으로 풀면 되겠다는 생각이 들었습니다.
✔️ 착안한 풀이 일반화
일반화한 식은 다음과 같았습니다.
따라서 n부터 (n-a+1)까지를 곱해서 분자를 만들고, a부터 1까지 곱한 분모값을 나누는 방식으로 로직을 구성하였습니다.
✔️ 틀린 이유
틀리고 난 후 예외 테스트케이스를 찾을 수 있었습니다. 제가 구성한 로직에서 N = 23, M = 17인 경우 -2777이 출력되었습니다. 확인 결과 분자를 만들 때(n부터 (n-a+1)까지 곱할 때) 변수를 long으로 선언했음에도 숫자가 너무 커서 long범위를 초과해버렸습니다.
2-2. 문제 풀이 - 2차
✔️ 문제 착안 - 조합 성질 이용
이번엔 조합의 특징을 이용해 dp로 문제를 풀었습니다.
조합은 아래와 같은 성질이 있습니다.
이 성질을 해석해보면 dp[n+1][r+1] = dp[n][r] + dp[n][r+1] 이며, 결론적으로
dp[n][r] = dp[n-1][r-1] + dp[n-1][r]
이라는 사실을 알 수 있습니다.
✔️ dp 구현
위의 성질을 이용하면 동적계획법을 이용한 문제 풀이가 가능합니다.
3-1. 1차 코드 (틀림)
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
int T = Integer.parseInt(br.readLine());
for (int i = 0; i < T; i++) {
st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
long result1 = multiply(M, N);
long result2 = multiply(N, N);
System.out.println(result1 / result2);
}
}
private static long multiply(int start, int count) {
long result = 1;
while (count > 0) {
result *= start - count + 1;
count--;
}
return result;
}
}3-2. 2차 코드 (맞음)
import java.io.*;
import java.util.*;
public class Main {
private static int[][] dp = new int[30][30];
private static void makeDp() {
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 <= i; j++) {
dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
}
}
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
StringBuilder sb = new StringBuilder();
makeDp();
int T = Integer.parseInt(br.readLine());
for (int i = 0; i < T; i++) {
st = new StringTokenizer(br.readLine(), " ");
int N = Integer.parseInt(st.nextToken());
int M = Integer.parseInt(st.nextToken());
sb.append(dp[M][N]).append('\n');
}
System.out.println(sb);
}
}4. 느낀점
동적계획법 문제는 문제 속의 규칙을 찾고, 규칙을 통해 "일반화"시키는 과정이 중요하다는 사실을 알게 되었습니다. 그리고 곱셈의 위력을 다시한 번 느꼈습니다. 첫 번째 풀이에서, 곱하다 보면 int자료형 범위는 당연히 넘을 것 같아 long을 이용한건데 long까지도 넘을 줄은 정말 몰랐습니다.. 앞으로는 조금만 더 생각해보면서 문제의 규칙을 찾아보고자 노력해야겠다는 생각이 들었습니다.
[참고한 곳]
https://mathbang.net/111
https://st-lab.tistory.com/194
