PS/DP(20)
-
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 -
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 -
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