dp(20)
-
BOJ 17428 : K번째 괄호 문자열
https://www.acmicpc.net/problem/17428 17428번: K번째 괄호 문자열 첫째 줄에 K번째 괄호 문자열을 출력한다. K번째 괄호 문자열이 없는 경우에는 -1을 출력한다. www.acmicpc.net 걍 dp문제인데 재밌다. dp[i][j] = 길이가 i이고, 완성되지 않은 괄호쌍이 j개일 때 만들 수 있는 괄호쌍 갯수 dp[i][j] = dp[i+1][j+1] ('('를 넣을 때) + dp[i+1][j-1] (')'를 넣을 때) 문자열 구하는건 간단하다. "'('를 넣을 때"와 "')'를 넣을 때"를 분리해서 K번째 문자열을 구해주면 된다. 코드
2021.08.14 -
BOJ 6171 : 땅따먹기
https://www.acmicpc.net/problem/6171 Naive한 dp로 먼저 생각해보자. dp[i] = i번째 땅까지 샀을 때의 비용의 최솟값 dp[i] = min(dp[j-1]+max(w[k])*max(h[k])) (0
2021.08.08 -
BOJ 1066 : 에이한수
https://www.acmicpc.net/problem/1066 1066번: 에이한수 첫째 줄에 N자리이면서 진짜A한수의 개수를 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net 관찰이 재밌고 어려운 문제이다. 내가 문제 풀 당시에 관찰한 것은 -진짜 A한수에서 A의 자릿수가 비내림차순하게 만드려면 무조건 수열로 분할했을때 모든 수열이 비내림차순이여야 되는것이다. -A한수는 A+1한수이다. (if A 찐A한수는 등차수열 그룹의 갯수의 최솟값이 A인 A한수다. -A>9일때 답은 0이다. 이를 이용해 dp로 풀면 dp[i][j][k][d] = i번째 자릿수 차례, 등차수열 그룹 수가 j, i번째 자릿수가 k, 이전수가 속한 그룹의 등차가 d일때 갯수 라고 정의하..
2021.08.03 -
BOJ 22348 : 헬기 착륙장
22348번: 헬기 착륙장 (acmicpc.net) 22348번: 헬기 착륙장 각 테스트 케이스에 대해, 한 줄에 하나씩, 빨강 페인트 a통과 파랑 페인트 b통만을 이용해 만들 수 있는 서로 다른 헬기 착륙장의 수를 109 + 7로 나눈 나머지를 출력한다. www.acmicpc.net dp[i][j] = i개의 동심원, j개의 빨간 페인트를 이용했을 때 만들 수 있는 동심원 갯수 라고 두면 점화식은 이렇다 dp[i][j] += dp[i-1][j-i] (헤당 동심원에 빨간색 원을 만들 때) dp[i][j] += dp[i-1][j] (헤당 동심원에 파란색 원을 만들 때) 이때 우리는 만들 수 있는 모든 헬기 착륙장의 갯수를 만들어야 하므로, i
2021.07.31 -
BOJ 1056 : 수
https://www.acmicpc.net/problem/1056 1056번: 수 1부터 시작해서 N을 만들려고 한다. 사용할 수 있는 연산은 아래와 같이 총 3가지이다. 이때, N을 만드는데 사용하는 연산의 최소 횟수를 구하는 프로그램을 작성하시오. 현재 수를 1 증가시킴 (현 www.acmicpc.net 누가 봐도 DP를 이용하는 것이다. dp[i] = i를 만드는데의 최소 연산 수 . a^k
2021.07.29 -
BOJ 2618 : 경찰차
BOJ 2618 : 경찰차 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5≤N≤1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1≤W≤1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄까지 www.acmicpc.net 아주 왤논 dp. 쫄고 있었는데 의외로 쉬워서 놀랐다. 환상의 듀엣 문제(먼저 보고 오는 걸 추천.)와 비슷한 느낌으로 dp를 해보자. dp[i][j] = i번째 사건을 1번 경찰차가, j번째 사건을 2번 경찰차가 담당할때 최적해. dist(i, j) = i번째 사건과 j번째 사건 사이의 유클리드 거리. nxt = 다음 사건. 이라고 정의한다면 dp[i][nxt] = min(dp[i][j] + dist(j, nxt), dp..
2021.04.30