백준 12785번 C++, Python3 풀이

문제

 

시간 제한	메모리 제한	solved.ac 티어
1초	128MB	실버 1

---

풀이

 어제 오늘 장염에 걸려 제대로 문제를 풀지 못했다가, 오늘 기운이 좀 생긴 김에 랜덤 실버 문제를 후딱 풀어냈다. 이 문제는 사실 예전에 풀려고 했다가 실패하고, 어디서 틀렸는지 감을 잡지 못해 그대로 잊은 문제였는데, 랜덤으로 뽑았다가 이 문제가 나왔다.

 

 조합을 계산하는 방법은 여러가지가 있다. 해당 글에서 두가지 방법을 사용했었다. https://codejin.tistory.com/172

백준 1010번 C++ 풀이

그중에서 두번째 풀이를 사용했다. 당시에는 완전무결하게 동작하는 줄 알았고, 이 문제를 시도했을때도 그렇게 풀이했다. 하지만 계속해서 틀렸고, 왜 틀렸는지 알지 못해 넘긴 문제였다. 아래는 내가 실패한 코드이다.

실패한 풀이

#include <bits/stdc++.h>
using namespace std;
#define mod 1000007

int w, h, x, y;

int comb(int a, int b) { // a+bCa % mod
	int n = a + b;
	int r = min(a, b);

	int result = 1;
	int temp = 1;

	for (int i = n; i > n - r; i--) {
		result *= i;
		result /= temp++;
		result %= mod;
	}
	return result % mod;
}	

int sol() {
	int h2t = comb(x - 1, y - 1);
	int t2s = comb(w - x, h - y);
	return (h2t * t2s) % mod;
}

int main () {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> w >> h >> x >> y;
	cout << sol();
}

 

 해당 방식이 이 문제에서 통하지 않는 이유는 오늘 디버깅하면서 알았는데, 수가 커지면서 result / temp++ 부분이 제대로 동작하지 않은 것이다. 원래 해당 코드가 동작하던 이유는 result / temp의 나머지가 존재하지 않았기 때문인데, 이번 문제에서는 나머지가 발생하여 나눗셈이 제대로 동작하지 못했기 때문이었다.

 

 왜그런가 하고 생각해보았다. 모듈러 연산은 나눗셈에서는 적용되지 않는다. 모듈러 연산에서 나눗셈을 할때는 모듈러 역원과 같은 다른 개념을 도입해야하는데, 이를 간과했다. 정확히는 당시에 이러한 개념을 몰랐다고 하는게 맞을 것이다. result가 1000007보다 커지면서 모듈러 연산이 적용되는데, 이때 result의 값이 아예 바뀌면서 result / temp에서 나머지가 발생하고, 이는 제대로 연산이 되지 않게 된다. 그래서 dp를 이용한 연산으로 바꾸어 적용했다.

C++ 코드

#include <bits/stdc++.h>
using namespace std;
#define mod 1000007

int w, h, x, y;

int memo[500][500];

int comb(int n, int r) {
    if (memo[n][r]) {
		return memo[n][r] % mod;
	}
    else{
        memo[n][r] = ((comb(n - 1, r - 1) % mod) + (comb(n - 1, r) % mod)) % mod;
        return memo[n][r];
    }
}
void sol() {
	for(int i = 0; i < 500; i++) {
        memo[i][0] = memo[i][i] = 1;
    }
	int t2s = comb(w + h - x - y, min(w - x, h - y));
	int h2t = comb(x + y - 2, min(x - 1, y - 1));
	long long ans = (1LL * h2t * t2s) % mod;
	cout << ans;
}

int main () {
	cin.tie(nullptr)->sync_with_stdio(false);
	cin >> w >> h >> x >> y;
	sol();
}

 

 또한, 파이썬에는 조합의 개수를 구해주는 함수를 기본적으로 제공한다. 진짜 주 ps 언어를 파이썬으로 옮겨야 하나 싶은 현타가 아주 잠시 온다.

Python3 코드

import sys
import math

def input() : return sys.stdin.readline().strip()

w, h = map(int, input().split())
x, y = map(int, input().split())

mod = 1000007
h2t = math.comb(x + y - 2, min(x, y) - 1)
t2s = math.comb(w + h - x - y, min(w - x, h - y))
print(((h2t * t2s)) % mod)