Rocknz 's Blog

ICPC 문제 중 쿠폰 이라는 문제가 있다. 확률에 대한 개념이 별로 없어서 안 건들일려고 했는데, 해답을 보니.. 재밌는 문제인것 같다.문제는 이렇다. 한 치킨집에서 1~N개 종류의 쿠폰을 나눠주는데, 1부터 N 까지 모든 종류의 쿠폰을 한장씩 모으면 황금 치킨을 준다. 한번 먹을때마다 임의의 쿠폰을 1개씩 받는다고 하면, 내가 황금 치킨을 먹기 위해서는 평균적으로 몇번의 주문을 시켜야하나?우선, 각각 쿠폰을 받을 확률이 1/N 이라고 생각했을 때, 식을 전개해보면,처음에는 아무 쿠폰이나 받아도됨 -> 처음받은걸 또받음 -> 처음 받은걸 또받음 |-> 처음받은것 말고 나머지를 받음 |->처음받은것 말고 나머지를 받음 -> 두번째 받은거나 첫번째 받은걸 받음. |-> 첫번째나 두번째받은것 말고 나머지를 ..

ICPC문제를 풀다보면, 결과 값이 중간에 커지기 때문에 modulo값을 구하는 문제가 많이 있다.modulo값들은 덧셈,곱셈,뺄셈에서는(A(% p) + B(% p)) % p = (A + B)(% p)(A(% p) - B(% p) + p) % p = (A - B)(% p) (A(% p) * B(% p)) %p = (A * B)(% p) 이런식으로 A,B 값을 modulo p를 한 값을 가지고 있으면 (덧셈, 곱셈, 뺄셈) 값을 구할 수 있다.하지만 나누기의 경우(A(% p) / B(% p)) % p != (A / B)(% p)이다. 그렇기 때문에 계산 전 값을 가지고 있어야하고, 그 값이 Integer를 넘는다면.. 큰수 계산을 해야한다면... 굉장히 힘들 것이다. 그렇기 때문에 Fermat's litt..