-
[백준] #1102 발전소 - (DP)Algorithm/알고리즘 백준 풀이 2020. 3. 14. 06:28
#include <iostream> #include <cstring> #define MAX 16+1 #define INF 987654321 using namespace std; int N, P; int arr[MAX][MAX]; //dp[x][y] => 현재 y상태에서 발전소 x번에서 시작할때의 최소비용 int dp[MAX][1 << MAX]; int state = 1 << MAX; string str; //주어지는 변수의 2진수형태에서 1의 개수를 파악 int count1(int n) { int cnt = 0; while(n) { cnt += n & 1; n >>= 1; } return cnt; } int func(int idx, int currState) { //currState의 1의 개수가 P-1개 이상 => P개의 발전소켜짐 => 0리턴 //state의 초기값 맨 앞에 1이 기본적으로 추가가되므로 if (count1(currState) -1 >= P) return 0; int &ref = dp[idx][currState]; if (ref != -1) return ref; ref = INF; for (int i=0; i<N; ++i) { //꺼져있는 발전소를 킨후 상태 갱신 if ( (currState & (1<<i)) == 0) { int nextState = (currState | (1<<i)); for (int j=0; j<N; ++j) { //i번째 발전소를 키고, 그다음 켜져있는 발전소를 기준으로 함수 재귀호출 if (nextState & (1<<j)) ref = min(ref, func(j, nextState) + arr[idx][i]); } } } return ref; } int main() { cin >> N; for (int i=0; i<N; ++i) { for (int j=0; j<N; ++j) { cin >> arr[i][j]; } } cin >> str; for (int i=0; i<str.length(); ++i) { if (str[i] == 'Y') state |= (1<<i); } cin >> P; //켜야할 목표 발전소개수가 0개인 경우 if (P == 0) { cout << 0; return 0; } memset(dp, -1, sizeof(dp)); ////////////////////func//////////////////////// //최종 최소비용값 int result = INF; for (int i=0; i<N; ++i) { //켜져있는 발전소를 기준으로 dp함수 호출 if (str[i] == 'Y') { result = min(result, func(i, state)); } } //켜져있는 발전소가 없는경우 => 불가능 if (result == INF) cout << -1; else cout << result; }
문제
https://www.acmicpc.net/problem/1102
목표
N개의 발전소와 발전소간 다른발전소를 키기위한 비용이 주어질때 P개의 발전소를 모두 키기위한 최소비용구하기
(단, 켜져있는 발전소에서만 꺼져있는발전소를 킬수 있다.)
풀이
dp사용, 비트를 사용하여 발전소의 상태정보를 저장한다.
dp[MAX][1<<MAX] => y상태에서 x에서 시작하여 다른 발전소P개 이상을 키기위한 최소비용
1. 초기상태에서 켜져있는 발전소를 상대로 한번씩 함수를 돌려본후 최소값을 구한다.
2. (초기상태에서 켜져있는 발전소를 하나 고른후) 꺼져있는 발전소를 찾는다.
3. 꺼져있는 발전소를 키고, 다시 켜져있는 발전소를 찾아 2,3번 과정을 반복하며 dp값을 만든다.
코드
'Algorithm > 알고리즘 백준 풀이' 카테고리의 다른 글
[백준] #11062 카드게임 - (DP) (0) 2020.03.11 [백준] #14003 가장 긴 증가하는 부분수열5 - (DP) (0) 2020.03.02 [백준] #11049 행렬 곱셈 순서 - (DP) (0) 2020.03.02 [백준] #19115 가장 큰 정사각형 - (DP) (0) 2020.03.02 [백준] #9252 LCS2(Longest Common Subsequence) - (DP) (0) 2020.03.02