문제 링크 이는 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/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 토글링을 해서 ..

https://www.acmicpc.net/problem/9520 이 문제를 풀기 전 KOI 2003 경찰차 문제를 풀고 오는 것을 추천한다. 우리는 이 문제를 좀 바꾸어 생각해보면, 1부터 N까지의 자연수를 순서대로 앞 또는 뒤에 수를 추가하는 방식으로 수열을 만들고, 이를 순서로 해서 모든 도시를 방문할 때 비용의 최솟값을 구하는 문제이다. 이는 dp로 해결할 수 있다. dp[i][j] = 수열의 가장 왼쪽에 i가 있고, 가장 오른쪽에 j가 있을 때 최소 비용 dp[max(i,j)+1][j] = min(dp[max(i,j)+1][j], dp[i][j]+cost[i][max(i,j)+1]) dp[i][max(i,j)+1] = min(dp[i][max(i,j)+1], dp[i][j]+cost[j][max..

https://www.acmicpc.net/problem/5573 여학 때 풀지 못해서 업솔빙을 한 문제이다. 우리는 K번 후 각 위치에 대해 몇 번 방문했느냐에 따라 다음 방향이 달라짐을 관찰 할 수 있다. 이를 dp로 구하면 된다. dp[i][j] = (i,j)를 몇 번 지나갔는가? dp[1][1]은 초기 위치에서 몇 번 지나갔는가를 물으므로 k-1일테고, 식은 dp[i+1][j] = dp[i][j]/2 + (dp[i][j]%2(i,j에서의 초기 방향이랑 다른가) & !a[i][j](초기방향이 아래))(오른쪽으로 갈 때) dp[i][j+1] = dp[i][j]/2 + (dp[i][j]%2(i,j에서의 초기 방향이랑 다른가) & a[i][j](초기방향이 오른쪽))(아래로 갈 때) . 이를 구하고 답을 ..

https://www.acmicpc.net/problem/1023 1023번: 괄호 문자열 괄호 문자열은 다음과 같이 정의 한다. 빈 문자열은 괄호 문자열이다. S가 괄호 문자열일 때, (S)도 괄호 문자열이다. S와 T가 괄호 문자열이라면, ST도 괄호 문자열이다. 모든 괄호 문자열은 위의 www.acmicpc.net 를 먼저 풀고 오는걸 추천한다. 17428번: K번째 괄호 문자열 첫째 줄에 K번째 괄호 문자열을 출력한다. K번째 괄호 문자열이 없는 경우에는 -1을 출력한다. www.acmicpc.net dp[a][b][c] = 크기 a, b='('갯수 - ')'갯수, b c라고 할때, 만들 수 있는 괄호 ㄴㄴ 문자열의 갯수 b