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

문제 링크 이는 dp로 풀 수 있다. dp(i,j) = i개의 디스플레이로 만들어졌으면서, m으로 나눈 나머지를 j인 수 중 최대인 수 라고 정의하면 dp(i, (10*j+k)%m) = max(10*dp(i-1,j)+k) (0

https://www.acmicpc.net/problem/19568 이 문제를 풀기 전, 약 팔기 문제를 먼저 풀고 오는 것을 추천한다. 약 팔기 아이디어를 2D로 확장시킨 문제이다. (15,15)를 중심으로 1, 15, 15^2, 15^3을 상하좌우로 한 줄에 펼쳐놓으면 50000 이상까지 찾을 수 있다. 코드

https://www.acmicpc.net/problem/12935 위 그림 같이 풀면 된다. 10000까지 돌려본 결과 노드의 갯수가 딱 500개로 맞추어지므로 이는 항상 성립한다. n,m+1을 브루트포스하여 구하고, 이를 저 그래프에 맞게 출력하면 된다. 딱 500개로 맞추어지는게 좀 신기한 문제였다. 코드

https://www.acmicpc.net/problem/2315 dp로 풀 수 있다. dp[i][j][k] = i부터 j까지의 가로등을 모두 끄고 현재 위치가 (k==0 ? 앞 : 뒤)일때의 전력의 최솟값 cur : 현 위치, w : 시간당 전력소비량 dp[i-1][j][k] = min(dp[i-1][j][k], dp[i][j][k]+(cur-a[i-1].x)*w) (왼쪽으로 가서 끌 때) dp[i][j+1][k] = min(dp[i][j+1][k], dp[i][j][k]+(a[j+1].x-cur)*w) (오른쪽으로 가서 끌 때) w는 prefix sum을 통해 구할 수 있다. 이건 자력으로 풀었는데, 지금 보면 이걸 어떻게 자력으로 풀었나 싶을 정도로 어렵다고 생각한다. 코드

https://www.acmicpc.net/problem/1126 dp로 풀 수 있다. dp[i][j] = i번째 블럭을 쓰고, 두 탑의 높이 차가 j일때 최대 높이 dp[i+1][j] = max(dp[i+1][j], dp[i][j]) (블럭을 사용 안할 때) dp[i+1][j+h] = max(dp[i+1][j+h], dp[i][j]+h) (블럭을 쌓아서 높이 차이를 크게 할 때) dp[i+1][|j-h|] = max(dp[i+1][|j-h|], dp[i][j]+max(j-h,0)) (블럭을 쌓아서 높이 차이를 작게 할 때) 어려워서 풀이를 보고 풀었는데 좀 많이 안해본 기술이 BOJ다른 분 코드에 있었다. -차피 dp테이블을 채울 때 첫 인자는 현재와 다음밖에 쓰지 않기 때문에 mod2 토글링을 해서 ..