반응형 백준 썸네일형 리스트형 [BOJ 2399] 거리의 차이 2399번 (거리의 차이) 이 문제는 단순히 이중 반복문을 이용하여 (x[0] ,x[0]~x[n]) , (x[1], x[0]~x[n]), ... (x[n], x[0]~x[n]) 이렇게 총 n^2개의 모든 쌍을 구하는 방식으로 구할 수 있다. 하지만 이 방식은 시간복잡도가 O(n^2)이기 때문에 n이 커지면 시간이 오래 걸리게 되고, 또 이 문제의 분류가 "정렬" 이기 때문에 정렬을 이용하여 문제를 풀어보았다. 정렬을 이용한 풀이에는 아주 유용한 "수학적인 아이디어"가 이용된다. 1. 우선 정렬을 통해서 n개의 점을 좌표가 오름차순이 되도록 정렬을 한다. 2. 특정한 x[i]를 생각해보면, 모든 n^2개의 쌍 중에서, x[i]는 총 2n번 등장하게 된다. (x[1] ~ x[n] , x[i]) : n개 / .. [BOJ 11051] 이항 계수 2 11051번 (이항 계수 2) Try 1) 단순히 이항 계수의 식인 nCk = n! / k!(n-k)! 을 이용하여 해결하기 (idea) N과 K를 입력받았을 때, 1부터 N까지 곱하고, 그 후 1 ~ K까지 나누고, 1 ~ N-K까지 나눈다. 하지만 이 경우, 가장 큰 범위의 정수형 타입인 long long 타입이라고 하더라도, N이 큰 수면 오버플로우(Overflow)가 발생해서 정확한 수가 저장 되지 않는다. 따라서, 이 방법은 올바른 답을 도출해낼 수 없다. Try 2) 이항 계수 공식 nCk = n-1Ck-1 + n-1Ck 을 이용하고, Try 1)의 문제점을 해결하기 위해 (a+b)%mod = a%mod + b%mod 성질 이용하기. (idea) 이항 계수 공식인 nCk = n-1Ck-1 + .. 이전 1 2 3 4 다음
