dp(20)
-
BOJ 11570 : 환상의 듀엣
BOJ 11570 : 환상의 듀엣 11570번: 환상의 듀엣 상덕이와 희원이는 소문난 환상의 듀엣으로, 노래방에 가서 노래를 자주 부르곤 한다. 어느 날 상덕이는 백준이에게 선물 받은 악보를 가져왔다. 악보에는 그 노래를 표현하는데 필요한 음의 높 www.acmicpc.net dp로 풀 수 있다. dp[i][j] = i번째 음을 이가, j번째 음을 이가 불렀을때 최적해 A_i = i번째 음을 부를때 비용 nxt = 불러야 할 음 이라고 정의할 때, dp[i][nxt] = min(dp[i][j] + |A_nxt - A_j|, dp[i][nxt]) dp[nxt][j] = min(dp[i][j] + |A_nxt - A_i|, dp[nxt][j]) 코드 djayy035/dj035_PS 코드저장소. Contrib..
2021.04.30 -
BOJ 14728 : 벼락치기
www.acmicpc.net/problem/14728 14728번: 벼락치기 ChAOS(Chung-ang Algorithm Organization and Study) 회장이 되어 일이 많아진 준석이는 시험기간에도 일 때문에 공부를 하지 못하다가 시험 전 날이 되어버리고 말았다. 다행히도 친절하신 교수님께서 아래와 www.acmicpc.net 이 문제는 설명할 필요가 없다. 그냥 배낭 dp문제이다. 그러니까 그냥 하면 된다. #include #define MEM 300009 #define sanic ios_base::sync_with_stdio(0) #define x first #define y second using namespace std; typedef long long ll; const ll MOD..
2021.01.10 -
백준 연습 #1
DP 위주로 2시간 동안 연습한 세트이다. 1. 카드 구매하기2 (Silver 1) www.acmicpc.net/problem/16194 16194번: 카드 구매하기 2 첫째 줄에 민규가 구매하려고 하는 카드의 개수 N이 주어진다. (1 ≤ N ≤ 1,000) 둘째 줄에는 Pi가 P1부터 PN까지 순서대로 주어진다. (1 ≤ Pi ≤ 10,000) www.acmicpc.net 그냥 쉬운 DP 문제. dp[i]=min(dp[i],dp[j]+su[i-j]); #include #define MEM 1009 #define sanic ios_base::sync_with_stdio(0) using namespace std; typedef long long ll; ll n; ll su[MEM], dp[MEM]; ma..
2020.10.02 -
BOJ 2688 : 줄어들지 않아
https://www.acmicpc.net/problem/2688 2688번: 줄어들지 않아 문제 어떤 숫자가 줄어들지 않는다는 것은 그 숫자의 각 자리 수보다 그 왼쪽 자리 수가 작거나 같을 때 이다. 예를 들어, 1234는 줄어들지 않는다. 줄어들지 않는 4자리 수를 예를 들어 보면 0011, www.acmicpc.net 그냥 누가 봐도 DP로 전처리를 하고 각 입력에 대응하면 된다. dp[i][j] = "길이가 i, 마지막 자리의 수가 j일 때 경우의 수" 경우를 따져 보자. 1번째 경우 : i=1일 때 dp[i][j] = 1 2번째 경우 : i>1일 때 dp[i][j] = Σ dp[i-1][k] (0
2020.08.17 -
BOJ 17623 : 괄호
https://www.acmicpc.net/problem/17623 17623번: 괄호 6개의 문자 ‘(’, ‘)’, ‘{’, ‘}’, ‘[’, ‘]’ 로 이루어진 올바른 괄호 문자열 W에 대하여 정수의 ‘괄호값’을 지정하는 함수 val(W)가 정의되어 있다. 먼저 올바른 괄호 문자열부터 정의해 www.acmicpc.net 이 문제는 재귀적인 느낌(?)이 있기에 DP로 해결 가능하다. dp[i] = "N=i일때 dmap(X)의 최솟값" 이때 우리는 두 가지 경우를 생각할 수 있다. 첫번째 경우 : 이전 문자열에서 괄호를 감싸는 경우 i가 2,3,5의 배수일 때 처리해주면 된다. 두번째 경우 : 이전 문자열에 갖다 붙일 경우 min(dp[i]+dp[n-i]) & (1
2020.08.17 -
BOJ 3056 : 007
https://www.acmicpc.net/problem/3056 모든 경우의 수를 찾는데 백트래킹으로 하면 시간 많이 걸리니 Bit DP를 돌리자(?). 계산 조심하면 AC. #include #define MEM 20 #define sanic ios_base::sync_with_stdio(0) #define pb push_back using namespace std; typedef long long ll; typedef pair pii; const ll INF = 1e9+7; ll n,ans; double mp[MEM][MEM]; double dp[1
2020.08.13