코포 버추얼을 돌렸다. -Codeforces Round #377 (Div. 2) 푼 BOJ 목록 -7-세그먼트 디스플레이 -색깔 하노이 탑 음... 아직 부족한 것 같다. 내일은 시간이 더욱 부족하니까 1버추얼과 백준 1문제 하는 걸 목표로 하자.

문제 링크 그림을 그리면서 관찰을 해보자. 먼저 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을 통해 구할 수 있다. 이건 자력으로 풀었는데, 지금 보면 이걸 어떻게 자력으로 풀었나 싶을 정도로 어렵다고 생각한다. 코드