-
[SWEA] 4012 요리사문제 풀이 2020. 5. 13. 23:03
4012 요리사
풀이)
문제 자체는 어렵지 않았다.
dfs를 이용해 각 음식마다 어떤 식쟤료를 가질건지 결정한 다음, 시너지 계산하는 완전 탐색 문제였다.
그런데 처음에 시간초과 나길래 당황했다.
알고보니, n개의 식재료가 있다면 음식 1을 위해 n/2 개까지만 고르고 나머지 쟤료들은 음식 2를 위해 쓰면되는데
쓸데없이 식재료 n개의 나올 수 있는 모든 조합을 다 보고 있었다.
즉, 음식 1을 위해 n/2개만 고르면 되는데 1~n개까지 고르는 경우를 다 확인한 것이다.
(그리고 나서 n/2개씩일때만 계산하게 함)
다시 풀때는 n/2개만 고르고 나머지들은 자동적으로 다른 음식 2를 위해 쓰이게 풀어줬다.
코드)
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960#include <stdio.h>#include <vector>#include<algorithm>#include<cmath>using namespace std;#define INF 999999999;int n;int arr[16][16];int result;bool visited[16];void dfs(int idx,int depth) {if (depth == n/2) {vector <int> food[2];for (int i = 0; i < n; i++) {if (visited[i]) {food[0].push_back(i);}else {food[1].push_back(i);}}int cnt[2] = { 0 ,0 };for (int i = 0; i < n / 2; i++) {for (int j = 0; j < n / 2; j++) {if (i == j)continue;cnt[0] += arr[food[0][i]][food[0][j]];cnt[1] += arr[food[1][i]][food[1][j]];}}result = min(result, abs(cnt[0] - cnt[1]));return;}for (int i = idx; i < n; i++) {visited[i] = true;dfs(i + 1, depth + 1);visited[i] = false;}}int main() {//freopen("sample_input (1).txt", "r", stdin);int T = 0;scanf("%d", &T);for (int test_case = 1; test_case <= T; test_case++) {scanf("%d", &n);for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {scanf("%d", &arr[i][j]);}}result = INF;dfs(0, 0);printf("#%d %d\n", test_case, result);}return 0;}cs '문제 풀이' 카테고리의 다른 글
[프로그래머스] 여행경로 (0) 2020.05.15 [SWEA] 5656 벽돌깨기 (0) 2020.05.14 [SWEA] 5650 핀볼게임 (0) 2020.05.12 [SWEZ] 2383 점심 식사시간 (0) 2020.05.11 [SWEA] 2117. 홈 방범 서비스 (0) 2020.05.09