문제 링크 http://icpc.me/15824 15824번: 너 봄에는 캡사이신이 맛있단다 한 줄에 모든 조합의 주헌고통지수 합을 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 풀이 수학 문제다. 각 수가 최댓값, 최솟값이 될 수 있는 경우의 수를 각각 잘 계산하면 된다. 정렬된 배열 arr에서 arr[i]가 최댓값이 될 수 있는 경우의 수는 arr[0]~arr[i-1]의 모든 조합의 수인 2^i 같고, arr[i]가 최솟값이 될 경우의 수는 arr[i+1]~arr[n-1]까지의 모든 조합의 수인 2^(n-i-1)이다. cf) 2^n을 미리 구해 놓을때 mod를 하지 않으면 시간 초과를 받을 수 있다. 파이썬에서 큰수 연산 곱하기의 시간복잡도가 O(n^1.585)라고 ..

문제 링크 http://icpc.me/1011 1011번: Fly me to the Alpha Centauri 우현이는 어린 시절, 지구 외의 다른 행성에서도 인류들이 살아갈 수 있는 미래가 오리라 믿었다. 그리고 그가 지구라는 세상에 발을 내려 놓은 지 23년이 지난 지금, 세계 최연소 ASNA 우주 비행 www.acmicpc.net 풀이 규칙을 찾으면 되는 문제다. 어떤 거리만큼 가장 짧은 거리로 가려면 한 번에 많은 거리를 움직여야 한다. 한 번에 움직이는 거리가 최대가 되는 상황을 잘 구하면 된다. 만약 한번에 k만큼 움직인다면, k만큼 움직이기 위해서는 1 2 3 4 .. k k-1 k-2 .. 1 이런 식으로 움직여야 할 것이다. 이때 1 + 2 + 3 + 4 + .. + k + k-1 + k..