PS/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 20984 : Growing Vegetables is Fun 4
BOJ 20984 : Growing Vegetables is Fun 4 20984번: Growing Vegetables is Fun 4 Bitaro likes gardening. He is now growing plants called Biba-herbs in the garden. There are N Biba-herbs in the garden, planted in a line from the west to the east. The Biba-herbs are numbered from 1 to N from the west to the east. Now, the height of the B www.acmicpc.net Prefix-sum을 이용해 풀 수 있다. ldp_i : 1~i번째 배추까지 증가 상태를..
2021.05.11