간단하게 nCk -> n!/k!(n-k)! 같은 방식으로 문제를 풀 수 없다. 문제의 N과 K가 매우 크기 때문에 기존의 팩토리얼 알고리즘은 시간/공간 복잡도를 초과한다. 하지만 문제에서는 nCk 값을 1,000,000,007로 나누라고 했으므로 나머지를 구하는 소수(P)가 주어졌다. 그러면 페르마의 소정리를 적용할 수 있다. 자세한 것은 생략하지만, 조합 공식을 곱셈 형태로 변형할 수 있다. ∴ nCk​ % P = n! x ((n−k)!k!)^P−2 % P 여기서도 n, k, n-k의 팩토리얼을 그대로 구할 수 없기 때문에, 나머지 연산을 적용한 팩토리얼을 구하기 위해서 나머지 연산의 분배법칙 중 곱셈에 대한 분배법칙을 사용하면 된다! (A x B) % P = ((A % P) x (B % P)) % P..

이 문제의 분류는 "분할 정복을 이용한 거듭제곱" 이다. 즉, 어떤 수를 매우 큰 횟수로 거듭제곱 한다면, 시간복잡도를 줄이는 방법을 묻는 문제인 것이다. 예를 들어, 2를 32번 제곱한다는 것은 -> (2^16)^2, 즉 2의 16승을 한 번 제곱한 값과 같다. 그러면 32번의 연산에서 -> 17번의 연산으로 감소한다! 더 나아가서 ((2^8)^2)^2) 는 10번의 연산만 요구한다. (((2^4)^2)^2)^2)는 단 7번의 연산만 요구한다! def reduce_pow(a, b, c): if (b == 1): return a % c X = reduce_pow(a, b//2, c) if (b % 2 == 0): # 짝수라면 return X * X % c else: # 홀수라면 return a * X *..

어차피 체스판에 놓일 퀸들은 다 다른 행, 다른 열에 있어야 한다. 그리고 서로의 대각선에 위치해 있어도 안 된다. 맨 위에 행의 1번째 열부터 확인한다. 2번째 행에 되는 열(3번째 열)이 있으면, 3번째 행으로 내려간다. 이 상황은 3번째 행에 되는 열이 없다. 그럼 다시 2번째 행으로 올라간다. 2번째 행으로 올라가서 다음 열(4번째 열)을 확인한다. 3번째 행으로 가서 되는 열이 있는지(2번째 열) 확인한다. 이 상황은 4번째 행에 되는 열이 없다. 그럼 다시 1번째 행의 2번째 열부터 시작하는 것이다. 1번째 행의 2번째 열을 확인한다. 2번째 행에서 되는 열(4번째 열)이 있는지 확인한다. 3번째 행에 되는 열(1번째 열)이 있는지 확인한다. 4번째 행에 되는 열(3번째 열)이 있는지 확인한다..

재귀함수는 너무 어렵다.. 이전 15649번 문제도 한참 해맸는데, 조금만 응용하니까 더 헷갈린다. 처음 직접 풀었던 풀이 -> 그냥 이전 풀이처럼 모든 가능한 경우의 수를 다 때려박고 바로 출력하는 대신, 수열을 강제로 정렬하고 set으로 중복을 제거하고, 다시 출력했다. 딱 봐도 N, M이 커지면 커질 수록 시간 복잡도에서 손해를 볼 것이 분명하다.. N, M = map(int, input().split()) seq = [] seq_list = [] # 문제의 조건을 만족하는 수열들이 담길 리스트 def dfs(): if (len(seq) == M): seq_list.append(sorted(seq)) # 수열을 강제로 정렬한다음 리스트에 넣는다. return for i in range(1, N + ..

먼저 문제의 입력이 20억까지이므로 그냥 조합을 직접 계산하면 시간초과, 메모리 초과 가 난다. 끝자리가 0이라는 것은 2와 5의 곱으로 이루어져 있다는 것이다. 예를 들어 10 = 2 x 5이다. 나아가 끝자리 0이 2개라면, 2와 5의 곱이 2쌍이라는 것이다. 즉, 100 = 2 x 2 x 5 x 5이다. 따라서 "어떤 수의 끝자리 0의 개수는 그 수의 인수 2와 5의 개수 중에서 최소값이다." 라는 사실을 가지고 문제를 풀면 된다. 문제는 조합의 0의 개수니까 == N! 의 인수 2와 5의 개수 - ( (N - M)!의 인수 2와 5의 개수 + M!의 인수 2와 5의 개수)의 최소값을 찾으면 된다. def count_two(n): count = 0 i = 2 divisor = 2 while (div..

같은 종류의 의상은 하나씩만 착용할 수 있으며, 알몸이 아니어야 하므로 꼭 1종류 이상의 의상은 착용해야 한다. 예를 들어, 3종류의 의상이 있으면 1종류만 착용해도 되고, 2종류를 착용해도 되고, 3종류를 착용해도 되지만 0종류를 착용하는건 안된다. 그렇다면 다음과 같은 식을 세울 수 있다. (a종류의 의상 수 + 1) x (b종류의 의상 수 + 1) x (c종류의 의상 수 + 1) ...... - 1 여기서 각 종류수에 +1을 해준 이유는 그 종류의 의상을 착용하지 않아도 되는 경우를 추가했기 때문이고 마지막에 -1을 해준 이유는 모든 의상을 착용하지 않은 경우는 제외해야 하기 때문이다. 의상의 종류는 같은데 이름이 다른 의상이 여러개일 수 있으므로 [의상의 종류]를 키, [의상의 이름들을 담은 리스..

잘 생각해보자. N개의 주어진 수가 각각 A, B, C 라고 하자. 이때, 문제에 따르면 A, B, C를 이렇게 M으로 표현할 수 있다. A = M x a(미지수인 몫) + R(항상 일정한 나머지) B = M x b + R C = M x c + R 여기서 R을 제거하기 위해 A에서 B를, B에서 C를 뺀다고 하면 다음과 같은 식이 성립한다. A - B = M(a - b) B - C = M(b - c) 그렇다면 M은 A-B 와 B-C의 공약수이다. 이런 원리로, A~Z까지 입력받은 모든 수에 대해(오름차순), M은 B - A, C - B, ...... Z - Y의 공약수들이다. 즉, 이웃한 것끼리 뺀 수들의 최대공약수의, 1을 제외한 모든 약수가 M이 될 수 있는 것이다. from math import g..

[이 문제의 핵심] == 을 사용할 때는 주의하자! 컴퓨터는 모든 실수를 정확하게 저장하지 않는다. import math T = int(input()) for _ in range(T): x1, y1, r1, x2, y2, r2 = map(int, input().split()) if (x1 == x2 and y1 == y2 and r1 == r2): # 같은 좌표에서 같은 반지름이면 원이 겹친다. print(-1) continue if (r2 > r1): # r2는 항상 r1보다 작게끔 한다. (x1, y1, r1, x2, y2, r2) = (x2, y2, r2, x1, y1, r1) 경우의 수를 쉽게 생각하기 위해, 두 번째 좌표의 반지름 r2는 r1보다 무조건 작도록 하였다. xy_distance_po..