문제 링크 그림을 그리면서 관찰을 해보자. 먼저 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..

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 이때 저 나머지 이차방정식은 판별식과 근의 공식을 사용하자. 나머..