블로그 옮겼습니다
BOJ 14276번 도로 건설 본문
우선 A번 집에서 다른 집으로 도로 건설한다고 하면 A+1번 도시에는 0~k개의 도로를 건설할 수가 있고
A+2번 집에도 0~k 개의 도로를 건설할 수가 있고...... 정말 많은 경우의 수가 있고 반복문이 중첩이 되기때문에
구현도 복잡하다. 그렇기 때문에 애초에 부분 문제를 이렇게 세우면 이 문제를 풀기가 힘들어진다.
그럼 부분문제를 어떻게 바꿔야 할까?
dp[u][v][k][mask] : u번 집에서 v번 집부터 건설할지 봐줘야하며, k개의 도로를 건설해야하고 현재 집을 포함하여
K+1개의 집과 인접한 도로의 수의 짝홀정보 일 때 앞으로 도로를 건설하는 방법의 수
라고 부분문제를 정의하여 현재 u번 집에서 이어줄 집 번호를 부분문제에 명시하여 순서를 강제할 수가 있게된다.
그럼 매 순간 u번 집과 v번 집사이에 도로를 '하나 더' 건설할지 말지만 결정하면 된다. 그럼 하나의 부분문제를
구하는데 걸리는 시간복잡도는 O(1) 이 되는 것이다.
도로를 건설한다면 go(u,v,k-1, nextmask) 이며(nextmask는 적절히 XOR하여 바꿔주면됨)
더이상 v에는 건설하지 않고 u에서 이어줄지 봐줄 집을 다음 집으로 넘어간다면 go(u,v+1,k,mask) 가 된다.
그리고 현재 u에서 다음 K개 노드까지만 봐주면되기 때문에 v-u > K 가 되는 순간 go(u+1,u+2,k,mask)
와 같은 식으로 해주며, u를 다음 노드로 넘어간다면 더이상 u는 인접한 도로의 수가 변할 수 없게 된다.
왜냐하면 현재 보는 집보다 번호가 큰 집으로만 도로를 이을 수 있게 강제했기 때문이다. 그렇기 때문에
u를 다음 집으로 옮겨줄 때 u에 인접한 도로의 수가 홀수개라면 조건을 만족할 수 없으므로 0을 반환한다.
나머지는 그냥 u나 v가 N이 되었을 때에 대한 기저를 잘 해주고 나머지는 위에서 말한것처럼 mask 가 0인지
확인하고 그런걸 잘 하면된다.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 | #include <bits/stdc++.h> using namespace std; typedef long long ll; const int mod = 1e9+7; const int inf = 0x3c3c3c3c; const long long infl = 0x3c3c3c3c3c3c3c3c; int N,M,K; ll dp[33][33][33][1<<9]; ll go(int u, int v, int k, int mask){ if(u == N || k == 0) return mask == 0 && k==0; if(v==N || v-u > K) { if(mask&1) return 0; return go(u+1,u+2,k,mask>>1); } ll& cache = dp[u][v][k][mask]; if(cache != -1) return cache; cache = 0; cache = (cache + go(u,v+1,k,mask)) % mod; int nextmask = mask^(1<<(v-u)); nextmask^=1; cache = (cache + go(u,v,k-1,nextmask)) % mod; return cache; } int main() { memset(dp,-1,sizeof(dp)); scanf("%d%d%d",&N,&M,&K); printf("%lld",go(0,1,M,0)); return 0; } | cs |
'Algorithm > Problem Solving' 카테고리의 다른 글
Codeground) 윤목의 달인 (0) | 2017.05.26 |
---|---|
Topcoder SRM 522 Div1(Medium) CorrectMultiplication (0) | 2017.05.20 |
Hackerrank) Tree Pruning (0) | 2017.05.11 |
CSacademy Round #29 (Div. 2 only) D. Water Bottles (0) | 2017.05.11 |
Topcoder SRM 514 Div1(Medium) MagicalGirlLevelTwoDivOne (0) | 2017.05.10 |