문제 링크 그림을 그리면서 관찰을 해보자. 먼저 n번째 원판들이 1->3으로 갈 때 옮기는 횟수는 n=1일 경우 3, n>1일 경우 2^(n+1)임을 알 수 있다. 그렇다면 이를 n번째 원판들까지 있다고 할 때 옮기는 총 횟수를 식으로 나타내보자. 2^(n+1)+2^n+2^(n-1).....+2^3+3 = 2^(n+1)+2^n+2^(n-1).....+2^3+2^2+2^1+2^0-4 = 2^(n+1)+2^n+2^(n-1).....+2^3+2^2+2^1+2^0+1-5 = 2^(n+2)-5 가 된다. 이제 이걸 계산해주면 되는데, 아주 큰 수를 계산한 나머지를 요구한다. 큰 수 계산, 거듭제곱 계산에는 Python이 더 유리하므로 파이썬으로 풀었다. C++로 한다면, n의 최대가 10^6이므로 그냥 O(n)으..

https://www.acmicpc.net/problem/2500 2500번: 복불복 첫째 줄에 3개의 정수 N, K, T가 빈칸을 사이에 두고 주어진다. N은 회전판을 돌리는 횟수를 나타내고, K는 게임을 하는 사람에게 처음 주어지는 조약돌의 개수를 나타낸다. T는 회전판에 그려져 있 www.acmicpc.net 상당히 어렵고 재밌는 발상의 문제이다. 회전판을 한 번 돌렸을 때 i개의 돌을 가져갈 때의 가능한 경우의 수를 C_i라고 하면 C_0 + C_1*x + C_2*x^2 + ........ C_k*x^k 라는 다항식을 만들 수 있다. 이때 x^i에서의 i는 쓴 돌의 갯수라고 생각하면 이해가 편하다. 그렇다면 N번 회전판을 돌렸을때는 이렇게 표현할 수 있다. (C_0 + C_1*x + C_2*x^2..

BOJ 2487 : 섞기 수열 2487번: 섞기 수열 A1, A2, …, AN으로 표시된 N 개의 카드를 정해진 방법으로 섞고자 한다. 그 섞는 방법은 1에서 N까지의 숫자로 이루어진 수열로 표시된다. 이 수열을 섞기 수열이라 하자. 섞기는 현재 가지고 있는 www.acmicpc.net 간단한 문제이다. 우리는 이 섞기를 반복하다보면, 어떤 특정한 원소끼리 값이 순환된다는 걸 알 수 있다. 이를 이용하면 답이 LCM(순환하는 그룹들의 순환 주기)라는 걸 알 수 있다. Union-find를 통해 각 순환되는 그룹 원소 갯수(=그룹들의 순환 주기)를 구해주고, LCM을 적용하면 된다. 코드 djayy035/dj035_PS 코드저장소. Contribute to djayy035/dj035_PS developme..

https://www.acmicpc.net/problem/9735 9735번: 삼차 방정식 풀기 문제 삼차 방정식 Ax3 + Bx2 + Cx + D = 0 의 모든 실수 해를 찾는 프로그램을 작성하시오. 입력으로 주어지는 방정식은 정수 해를 적어도 한 개 갖는다. A, B, C, D는 -2,000,000보다 크거나 같고, 2,000,000보 www.acmicpc.net 풀면서 욕 뒤지게 해먹은 문제 수학(상)에 나오는 3차방정식대로 풀 수 있다. 먼저 문제를 관찰하면 한개의 정수해는 존재하고, 정수해의 범위가 정해졌으니 그 정보를 이용해서 정수해를 찾는다. 정수해를 a라고 하면 방정식은 이런 형태를 띤다. (x-a)(bx^2+cx+d)=0 이때 저 나머지 이차방정식은 판별식과 근의 공식을 사용하자. 나머..

문제에서 2 또는 5로 나누어 떨어지지 않는 정수만 주어진다 했으니 비둘기집 원리에 의해 항상 답이 존재함을 알 수 있다. 우리는 1을 붙이지 않고 나머지의 성질을 이용하여 풀 수 있다. => (a+b)%MOD = a%MOD + b%MOD => (a*b)%MOD = ((a%MOD)*(b%MOD))%MOD 이를 이용해 배수를 하나의 식을 통해 확인할 수 있다. => a = (a*10+1)%n a가 0일 때까지 저 식을 계산해준다. 답은 저 식을 계산해준 횟수이다. #include #define MEM 500 #define sanic ios_base::sync_with_stdio(0) using namespace std; typedef long long ll; const ll MOD = 1e9+7; ll t..