#include <stdio.h>
#include <iostream>
using namespace std;
 
int bead[15];
int N;
int firstN;
int Max;
 
void shift(int idx)
{
    for(int i = idx; i <= N-1; i++)
    {
        bead[i] = bead[i+1];
    }    
    
    N--;
} 
 
void back_up(int idx, int value)
{
    for(int i = N+1; i > idx; i--)
    {
        bead[i] = bead[i-1];
    }
    bead[idx] = value;
    
    N++;
}
 
void permutation(int energy, int cnt)
{
    if(cnt == firstN-2 + 1)
    {    
        if(energy > Max)
        {
            Max = energy;
        }
 
        return;
    }
    
    for(int i = 2; i <= N-1; i++)
    {
        int choiceIdx = i;
        int choiceValue = bead[i];
        int tempEnergy = bead[choiceIdx-1] * bead[choiceIdx+1];
        
        shift(choiceIdx);
        permutation(energy + tempEnergy, cnt+1);
        back_up(choiceIdx, choiceValue);
    }
}
 
int main(void)
{
//    freopen("B16198_input.txt", "r", stdin);
    
    scanf("%d", &N);    
    firstN = N;
    
    for(int i = 1; i <= N; i++)
    {
        scanf("%d", &bead[i]); 
    }
    
    permutation(0, 1);
    
    cout << Max;
 
    return 0;
} 
cs
저작자표시

'Baekjoon > BruteForce' 카테고리의 다른 글

[백준 15684] 사다리 조작 (조합) (C/C++) (★★★)  (2) 2019.11.20
[백준 15686] 연산자 끼워넣기(2) (순열) (C/C++)  (0) 2019.11.20
[백준 14502] 연구소 (조합) (C/C++) (★★)  (0) 2019.11.20
[백준 14888] 연산자 끼워넣기 (순열) (C/C++)  (0) 2019.11.20
[백준 14501] 퇴사 (조합) (C/C++) (★)  (0) 2019.11.20
#include <stdio.h>
#include <iostream>
#include <queue>
using namespace std;
 
int map[10][10];
int mapCopy[10][10];
int N, M;
int Max;
 
pair<int, int> wall[100];
pair<int, int> virus[100];
int wallCnt, virusCnt;
 
queue<pair<int, int>> q;
int visited[10][10];
 
int dx[4] = {-1, 1, 0, 0}; // 상하좌우 
int dy[4] = {0, 0, -1, 1}; // 상하좌우
 
void copy()
{
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            mapCopy[i][j] = map[i][j];
        }
    }    
}
 
void init()
{
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            visited[i][j] = 0;
            map[i][j] = mapCopy[i][j];
        }
    }
}
 
int zeroCount()
{
    int cnt = 0;
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            if(map[i][j] == 0)
            {
                cnt++;
            }        
        }
    }
    
    return cnt;
}
 
int safe(int x, int y)
{
    if(x >= 0 && y >= 0 && x < N && y < M)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
// BFS
void spread_virus(int x, int y)
{
    visited[x][y] = 1;
    q.push({x, y});
    
    while(!q.empty())
    {
        int x = q.front().first;
        int y = q.front().second;
        q.pop();
        
        for(int i = 0; i < 4; i++)
        {
            int xpos = x+dx[i];
            int ypos = y+dy[i];
            
            if(map[xpos][ypos] != 1 && safe(xpos, ypos) == 1 && visited[xpos][ypos] == 0)
            {
                visited[xpos][ypos] = 1;
                q.push({xpos, ypos});
                map[xpos][ypos] = 2;
            }
        }    
    }
}
 
// DFS + 조합 
void make_wall(int idx, int cnt)
{
    if(cnt == 3)
    {
        copy();
        
        for(int i = 0; i < virusCnt; i++)
        {
            spread_virus(virus[i].first, virus[i].second);
        }
        
        int val = zeroCount();
        
        if(val > Max)
        {
            Max = val;
        }
        
        init();
        
        return;
    }    
    
    for(int i = idx; i < wallCnt; i++)
    {
        map[wall[i].first][wall[i].second] = 1;
        make_wall(i+1, cnt+1);
        map[wall[i].first][wall[i].second] = 0;
    }
}
 
void simulation()
{
    make_wall(0, 0);
}
 
int main(void)
{
//    freopen("B14502_input.txt", "r", stdin);
    
    scanf("%d %d", &N, &M);
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            scanf("%d", &map[i][j]);
            mapCopy[i][j] = map[i][j];
            
            if(map[i][j] == 0)
            {
                wall[wallCnt].first = i;
                wall[wallCnt++].second = j;
            }
            else if(map[i][j] == 2)
            {
                virus[virusCnt].first = i;
                virus[virusCnt++].second = j;
            }
        }
    }
    
    simulation();
    
    cout << Max;
    
    return 0;
} 
cs
저작자표시

'Baekjoon > BruteForce' 카테고리의 다른 글

[백준 15686] 연산자 끼워넣기(2) (순열) (C/C++)  (0) 2019.11.20
[백준 16198] 에너지 모으기 (순열) (C/C++) (★★)  (0) 2019.11.20
[백준 14888] 연산자 끼워넣기 (순열) (C/C++)  (0) 2019.11.20
[백준 14501] 퇴사 (조합) (C/C++) (★)  (0) 2019.11.20
[백준 2422] 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 (조합) (C/C++) (★)  (1) 2019.11.19
#include <stdio.h>
#include <iostream>
using namespace std;
 
int num[15];
int oper[15];
int choice[15];
int visited[15];
int operCnt;
int N;
int pluss, minuss, multi, divide;
long long Max = -1000000005;
long long Min = 1000000005;
 
long long cal()
{
    long long val = num[0];
    
    for(int i = 1; i <= N-1; i++)
    {
        if(choice[i] == 1)
        {
            val += num[i];
        }
        else if(choice[i] == 2)
        {
            val -= num[i];
        }
        else if(choice[i] == 3)
        {
            val *= num[i];
        }
        else if(choice[i] == 4)
        {
            if(val >= 0)
            {
                val /= num[i];    
            }
            else 
            {
                int temp = -val;
                temp /= num[i];
                
                val = -temp;
            }
        }
    }
    
    return val;
}
 
void permutation(int cnt)
{
    if(cnt == N)
    {
        long long val = cal();
        
        if(val > Max)
        {
            Max = val;
        }
        
        if(val < Min)
        {
            Min = val;
        }
        
        return;
    }
    
    // 연산 중복 제거 
    int used[5] = {0};
    
    for(int i = 1; i <= operCnt; i++)
    {
        if(visited[i] == 0 && used[oper[i]] == 0)
        {
            used[oper[i]] = 1;
            visited[i] = 1;
            choice[cnt] = oper[i];
            permutation(cnt+1);
            visited[i] = 0;
        }    
    }
}
 
int main(void)
{
//    freopen("B14888_input.txt", "r", stdin);
    
    scanf("%d", &N);
    
    for(int i = 0; i < N; i++)
    {
        scanf("%d", &num[i]);
    }
    
    scanf("%d %d %d %d", &pluss, &minuss, &multi, &divide);
    
    // oper에 1(+), 2(-), 3(*), 4(/) 담아줌 -> 이걸로 순열 적용 
    for(int i = 0; i < pluss; i++)
    {
        oper[++operCnt] = 1;
    }
    for(int i = 0; i < minuss; i++)
    {
        oper[++operCnt] = 2;
    }
    for(int i = 0; i < multi; i++)
    {
        oper[++operCnt] = 3;
    }
    for(int i = 0; i < divide; i++)
    {
        oper[++operCnt] = 4;
    }
    
    permutation(1);
    
    cout << Max << "\n";
    cout << Min << "\n";
 
    return 0;
} 
cs
저작자표시

'Baekjoon > BruteForce' 카테고리의 다른 글

[백준 16198] 에너지 모으기 (순열) (C/C++) (★★)  (0) 2019.11.20
[백준 14502] 연구소 (조합) (C/C++) (★★)  (0) 2019.11.20
[백준 14501] 퇴사 (조합) (C/C++) (★)  (0) 2019.11.20
[백준 2422] 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 (조합) (C/C++) (★)  (1) 2019.11.19
[백준 3980] 선발 명단 (순열) (C/C++) (★)  (0) 2019.11.18
#include <stdio.h>
#include <iostream>
using namespace std;
 
int choice[20];
int time[20];
int money[20];
int N;
int Max;
 
void combination(int moneySum, int timeSum)
{
    if(timeSum > N+1)
    {
        return;
    }
    
    if(moneySum > Max)
    {
        Max = moneySum;
    }
    
    for(int i = timeSum; i <= N; i++)
    {
        if(i + time[i] <= N+1)
        {
            combination(moneySum + money[i], i + time[i]);
        }
    }    
}
 
int main(void)
{
//    freopen("B14501_input.txt", "r", stdin);
    
    scanf("%d", &N);
    
    for(int i = 1; i <= N; i++)
    {
        scanf("%d %d", &time[i], &money[i]);
    }
    
    combination(0, 1);
 
    cout << Max;
    
    return 0;
}
cs
저작자표시

'Baekjoon > BruteForce' 카테고리의 다른 글

[백준 14502] 연구소 (조합) (C/C++) (★★)  (0) 2019.11.20
[백준 14888] 연산자 끼워넣기 (순열) (C/C++)  (0) 2019.11.20
[백준 2422] 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 (조합) (C/C++) (★)  (1) 2019.11.19
[백준 3980] 선발 명단 (순열) (C/C++) (★)  (0) 2019.11.18
[백준 15661] 링크와 스타트 (조합) (C/C++) (★★)  (0) 2019.11.18
#include <stdio.h>
#include <iostream>
using namespace std;
 
int choice[5];
int same[300][300];
int N, M;
int ans;
 
int check(int num, int cnt)
{
    for(int i = 0; i < cnt; i++)
    {
        if(same[choice[i]][num] == 1)
        {
            return 0;
        }
    }
    
    return 1;
}
 
void combination(int idx, int cnt)
{
    if(cnt == 4)
    {
        ans++;
        
        return;
    }
    
    for(int i = idx; i <= N; i++)
    {
        choice[cnt] = i;
        
        // 선택한 수가 조건에 위배되지않는지 확인 
        if(check(choice[cnt], cnt) == 1)
        {
            combination(i+1, cnt+1);
        }
    }    
}
 
int main(void)
{
//    freopen("B2422_input.txt", "r", stdin);
    
    scanf("%d %d", &N, &M);
    
    for(int i = 1; i <= M; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        same[a][b] = 1;
        same[b][a] = 1;
    }
    
    combination(1, 1);
    
    printf("%d", ans);
    
    return 0;
}
cs
저작자표시

'Baekjoon > BruteForce' 카테고리의 다른 글

[백준 14888] 연산자 끼워넣기 (순열) (C/C++)  (0) 2019.11.20
[백준 14501] 퇴사 (조합) (C/C++) (★)  (0) 2019.11.20
[백준 3980] 선발 명단 (순열) (C/C++) (★)  (0) 2019.11.18
[백준 15661] 링크와 스타트 (조합) (C/C++) (★★)  (0) 2019.11.18
[백준 15686] 치킨배달 (조합) (C/C++)  (0) 2019.11.18
#include <stdio.h>
#include <iostream>
using namespace std;
 
typedef struct node
{
    int pos[20];
}node;
 
int N;
int visited[20];
int Max;
node player[20];
 
void permutation(int sum, int cnt)
{
    if(cnt == 12)
    {
        if(sum > Max)
        {
            Max = sum;
        }
        
        return;
    }
    
    for(int i = 1; i <= 11; i++)
    {
        if(visited[i] == 0 && player[cnt].pos[i] != 0)
        {
            visited[i] = 1;
            permutation(sum + player[cnt].pos[i], cnt+1);
            visited[i] = 0;    
        }
    }
}
 
int main(void)
{
//    freopen("B3980_input.txt", "r", stdin);
    
    scanf("%d", &N);
    
    for(int T = 1; T <= N; T++)
    {
        for(int i = 1; i <= 11; i++)
        {
            for(int j = 1; j <= 11; j++)
            {
                cin >> player[i].pos[j];
            }
        }
        
        Max = 0;
        for(int i = 0; i < 20; i++)
        {
            visited[i] = 0;
        }
        
        permutation(0, 1);
        
        printf("%d\n", Max);
    }
    
    return 0;
}
cs
저작자표시

'Baekjoon > BruteForce' 카테고리의 다른 글

[백준 14501] 퇴사 (조합) (C/C++) (★)  (0) 2019.11.20
[백준 2422] 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 (조합) (C/C++) (★)  (1) 2019.11.19
[백준 15661] 링크와 스타트 (조합) (C/C++) (★★)  (0) 2019.11.18
[백준 15686] 치킨배달 (조합) (C/C++)  (0) 2019.11.18
[백준 2309] 일곱 난쟁이 (조합) (C/C++)  (1) 2019.11.18
#include <stdio.h>
#include <iostream>
#include <math.h>
using namespace std;
 
int map[30][30];
int N;
int Min = 9999999;
 
void combination(int start[], int visited[], int idx, int cnt, int std)
{
    if(cnt == std + 1)
    {
        int startSum = 0;
        int linkSum = 0;
        
        int link[20];
        int linkCnt = 0;
        
        for(int i = 1; i <= N; i++)
        {
            if(visited[i] == 0)
            {
                link[++linkCnt] = i;
            }
        }
        
        for(int i = 1; i < cnt; i++)
        {
            for(int j = 1; j < cnt; j++)
            {
                startSum += map[start[i]][start[j]];
            }
        }
        
        for(int i = 1; i <= linkCnt; i++)
        {
            for(int j = 1; j <= linkCnt; j++)
            {
                linkSum += map[link[i]][link[j]];
            }
        }
        
        if(abs(startSum-linkSum) < Min)
        {
            Min = abs(startSum-linkSum);
        }
        
        return;
    }
    
    for(int i = idx; i <= N; i++)
    {
        start[cnt] = i;
        visited[i] = 1;
        combination(start, visited, i+1, cnt+1, std);
        visited[i] = 0;
    }
}
 
int main(void)
{
//    freopen("B15661_input.txt", "r", stdin);
    
    scanf("%d", &N);
    
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= N; j++)
        {
            scanf("%d", &map[i][j]);
        }
    }
    
    // 팀원이 최소 1명 ~ N/2명 
    for(int i = 1; i <= N/2; i++)
    {
        int start[20] = {0};
        int visited[20] = {0};
        combination(start, visited, 1, 1, i);    
    }
    
    cout << Min;
    
    return 0;
}
cs
저작자표시

'Baekjoon > BruteForce' 카테고리의 다른 글

[백준 2422] 한윤정이 이탈리아에 가서 아이스크림을 사먹는데 (조합) (C/C++) (★)  (1) 2019.11.19
[백준 3980] 선발 명단 (순열) (C/C++) (★)  (0) 2019.11.18
[백준 15686] 치킨배달 (조합) (C/C++)  (0) 2019.11.18
[백준 2309] 일곱 난쟁이 (조합) (C/C++)  (1) 2019.11.18
[백준 2529] 부등호 (순열) (C/C++)  (0) 2019.11.18
#include <stdio.h>
#include <vector>
#include <math.h>
#include <iostream>
using namespace std;
 
int map[60][60];
int N, M;
vector<pair<int, int>> chicken;
vector<pair<int, int>> house;
vector<pair<int, int>> choice;
int Min = 9999999;
 
int check(pair<int, int> house, vector<pair<int, int>> choice)
{
    int dMin = 9999999;
    
    for(int i = 0; i < choice.size(); i++)
    {
        int d = abs(house.first - choice[i].first) + abs(house.second - choice[i].second);
        
        if(d < dMin)
        {
            dMin = d;
        }
    }
    
    return dMin;
}
 
void combination(int idx, int cnt)
{
    if(cnt == M)
    {
        int sum = 0;
        
        for(int i = 0; i < house.size(); i++)
        {
            sum += check(house[i], choice);    
        }
        
        if(sum < Min)
        {
            Min = sum;
        }
        
        return;
    }
    
    for(int i = idx; i < chicken.size(); i++)
    {
        choice.push_back({chicken[i].first, chicken[i].second});
        combination(i+1, cnt+1);
        choice.pop_back();
    }
}
 
int main(void)
{
//    freopen("B15686_input.txt", "r", stdin);
    
    scanf("%d %d", &N, &M);
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            cin >> map[i][j];
            
            if(map[i][j] == 1)
            {
                house.push_back({i, j});
            }
            else if(map[i][j] == 2)
            {
                chicken.push_back({i, j});
            }
        }
    }
    
    combination(0, 0);
    
    printf("%d", Min);
    
    return 0;
}
cs
저작자표시

'Baekjoon > BruteForce' 카테고리의 다른 글

[백준 3980] 선발 명단 (순열) (C/C++) (★)  (0) 2019.11.18
[백준 15661] 링크와 스타트 (조합) (C/C++) (★★)  (0) 2019.11.18
[백준 2309] 일곱 난쟁이 (조합) (C/C++)  (1) 2019.11.18
[백준 2529] 부등호 (순열) (C/C++)  (0) 2019.11.18
[백준 15666] N과 M(12) (중복조합) (C/C++)  (0) 2019.11.18

+ Recent posts

티스토리툴바