#include <stdio.h>
#include <iostream>
#include <queue>
#include <string.h>
#include <math.h>
using namespace std;
 
int N;
int relation[25][25];
vector<int> start_candidate;
int Min = 99999999;
 
void combination(int idx, int cnt)
{
    if(cnt == N/2)
    {
        int start = 0;
        int link = 0;
        vector<int> link_candidate;
        int visited[25] = {0};
        
        for(int i = 0; i < start_candidate.size(); i++)
        {
            for(int j = 0; j < start_candidate.size(); j++)
            {
                if(i == j)
                {
                    continue;
                }
                
                start += relation[start_candidate[i]][start_candidate[j]];
            }
        }
        
        for(int i = 0; i < start_candidate.size(); i++)
        {
            visited[start_candidate[i]] = 1;    
        }
        
        for(int i = 1; i <= N; i++)
        {
            if(visited[i] == 0)
            {
                link_candidate.push_back(i);
            }
        }
        
        for(int i = 0; i < link_candidate.size(); i++)
        {
            for(int j = 0; j < link_candidate.size(); j++)
            {
                if(i == j)
                {
                    continue;
                }
                
                link += relation[link_candidate[i]][link_candidate[j]];
            }
        }
        
        if(Min > abs(start-link))
        {
            Min = abs(start-link);
        }
        
        return;
    }
    
    for(int i = idx; i <= N; i++)
    {
        start_candidate.push_back(i);
        combination(i+1, cnt+1);
        start_candidate.pop_back();
    }
}
 
int main(void)
{
//    freopen("B14889_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= N; j++)
        {
            cin >> relation[i][j];
        }
    }
    
    combination(1, 0);
    
    cout << Min;
    
    return 0;
}
cs
저작자표시

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

[백준 1062] 가르침 (조합) (C/C++)  (0) 2020.03.24
[백준 1018] 체스판 다시 칠하기 (Brute Force) (C/C++)  (0) 2020.03.24
[백준 1251] 단어 나누기 (조합) (C/C++) (★)  (0) 2020.03.23
[백준 1041] 주사위 (조합) (C/C++)  (0) 2019.12.18
[백준 15683] 감시 (순열) (C/C++) (★★★)  (1) 2019.11.21
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <map>
using namespace std;
 
int N, K;
string word[55];
int alphabet[26];
int Max;
 
int count()
{
    int wordCnt = 0;
    
    for(int i = 1; i <= N; i++)
    {
        bool flag = true;
        
        for(int j = 0; j < word[i].size(); j++)
        {
            if(alphabet[word[i][j]-'a'] == 0)
            {
                flag = false;
                break;
            }
        }
        
        if(flag == true)
        {
            wordCnt++;        
        }
    }
    
    return wordCnt;
}
 
void combination(int idx, int cnt)
{
    if(cnt == K-5)
    {
        Max = max(Max, count());
        
        return;
    }
    
    for(int i = idx; i < 26; i++)
    {
        if(alphabet[i] == 1)
        {
            continue;
        }
        
        alphabet[i] = 1;
        combination(i+1, cnt+1);
        alphabet[i] = 0;
    }
}
 
int main(void)
{
//    freopen("B1062_input.txt", "r", stdin);
    
    cin >> N >> K;
    
    if(K <= 4)
    {
        for(int i = 1; i <= N; i++)
        {
            cin >> word[i];
        }
        
        cout << "0";
    }
    else
    {
        alphabet['a'-'a'] = 1;
        alphabet['c'-'a'] = 1;
        alphabet['i'-'a'] = 1;
        alphabet['n'-'a'] = 1;
        alphabet['t'-'a'] = 1;
        
        for(int i = 1; i <= N; i++)
        {
            cin >> word[i];
        }    
        
        combination(0, 0);
        
        cout << Max;
    }
    
    return 0;
}
cs
저작자표시

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

[백준 14889] 스타트와 링크 (조합) (C/C++)  (0) 2020.04.09
[백준 1018] 체스판 다시 칠하기 (Brute Force) (C/C++)  (0) 2020.03.24
[백준 1251] 단어 나누기 (조합) (C/C++) (★)  (0) 2020.03.23
[백준 1041] 주사위 (조합) (C/C++)  (0) 2019.12.18
[백준 15683] 감시 (순열) (C/C++) (★★★)  (1) 2019.11.21
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string>
#include <vector>
#include <stdlib.h>
using namespace std;
 
int row, col;
char map[55][55];
int Min = 99999999;
 
int main(void)
{
//    freopen("B1018_input.txt", "r", stdin);
    
    cin >> row >> col;
    
    for(int i = 0; i < row; i++)
    {
        string input;
        cin >> input;
        
        for(int j = 0; j < col; j++)
        {
            map[i][j] = input[j];
        }
    }
    
    for(int i = 0; i+7 < row; i++)
    {
        for(int j = 0; j+7 < col; j++)
        {
            for(int cnt = 0; cnt < 2; cnt++)
            {
                // 칠해야하는 정사각형의 갯수 
                int paint = 0;
                
                // 왼쪽 위가 B 
                if(cnt == 0)
                {
                    // 행, 열의 첫번째 색깔 저장 
                    char row_paint = 'B';
                    char col_paint = 'B';
                    
                    for(int k = i; k < i+8; k++)
                    {
                        for(int m = j; m < j+8; m++)
                        {
                            if(map[k][m] != col_paint)
                            {
                                paint++;
                            }
                            
                            // 열이 바뀔떄마다 색깔 변경 
                            if(col_paint == 'B')
                            {
                                col_paint = 'W'; 
                            }
                            else
                            {
                                col_paint = 'B';
                            }
                        }
                        
                        // 행이 바뀔때마다 색깔 변경 
                        if(row_paint == 'B')
                        {
                            row_paint = 'W';
                            col_paint = 'W';
                        }
                        else
                        {
                            row_paint = 'B';
                            col_paint = 'B';
                        }
                    }    
                }    
                // 왼쪽 위가 W
                else
                {
                    // 행, 열의 첫번째 색깔 저장 
                    char row_paint = 'W';
                    char col_paint = 'W';
                    
                    for(int k = i; k < i+8; k++)
                    {
                        for(int m = j; m < j+8; m++)
                        {
                            if(map[k][m] != col_paint)
                            {
                                paint++;
                            }
                            
                            if(col_paint == 'B')
                            {
                                col_paint = 'W';
                            }
                            else
                            {
                                col_paint = 'B';
                            }
                        }
                        
                        if(row_paint == 'B')
                        {
                            row_paint = 'W';
                            col_paint = 'W';
                        }
                        else
                        {
                            row_paint = 'B';
                            col_paint = 'B';
                        }
                    }    
                }
                
                Min = min(Min, paint);
            }
        }
    }
    
    cout << Min;
    
    return 0;
}
cs
저작자표시

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

[백준 14889] 스타트와 링크 (조합) (C/C++)  (0) 2020.04.09
[백준 1062] 가르침 (조합) (C/C++)  (0) 2020.03.24
[백준 1251] 단어 나누기 (조합) (C/C++) (★)  (0) 2020.03.23
[백준 1041] 주사위 (조합) (C/C++)  (0) 2019.12.18
[백준 15683] 감시 (순열) (C/C++) (★★★)  (1) 2019.11.21
#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
using namespace std;
 
string word;
string Min;
int divideIdx[2];
 
void combination(int idx, int cnt)
{
    if(cnt == 2)
    {
        string first = word.substr(0, divideIdx[0]+1);
        string second = word.substr(divideIdx[0]+1, divideIdx[1]-divideIdx[0]);
        string third = word.substr(divideIdx[1]+1);
        
        reverse(first.begin(), first.end());
        reverse(second.begin(), second.end());
        reverse(third.begin(), third.end());
        
        string temp = first;
        temp += second;
        temp += third;
        
        if(Min > temp)
        {
            Min = temp;
        }
        
        return;
    }
    
    for(int i = idx; i < word.size()-1; i++)
    {
        divideIdx[cnt] = i;
        combination(i+1, cnt+1);
    }
}
 
int main(void)
{
//    freopen("B1251_input.txt", "r", stdin);
    
    cin >> word;
    
    for(int i = 0; i < word.size(); i++)
    {
        Min += "z";
    }
    
    combination(0, 0);
    
    cout << Min;
    
    return 0;
}
cs
저작자표시

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

[백준 1062] 가르침 (조합) (C/C++)  (0) 2020.03.24
[백준 1018] 체스판 다시 칠하기 (Brute Force) (C/C++)  (0) 2020.03.24
[백준 1041] 주사위 (조합) (C/C++)  (0) 2019.12.18
[백준 15683] 감시 (순열) (C/C++) (★★★)  (1) 2019.11.21
[백준 15684] 사다리 조작 (조합) (C/C++) (★★★)  (2) 2019.11.20
#include <stdio.h>
#include <iostream>
#include <set>
#include <map>
#include <queue>
#include <vector>
#include <string>
#include <math.h>
#include <algorithm>
using namespace std;
 
int N; 
int dice[7];
long long Min1 = 9999;
long long Min2 = 9999;
long long Min3 = 9999;
int check2[7];
int check3[7];
 
void Min_1()
{
    for(int i = 1; i <= 6; i++)
    {
        if(dice[i] < Min1)
        {
            Min1 = dice[i];
        }
    }
}
 
void Min_2(long long sum, int idx, int cnt)
{
    if(cnt == 2) 
    {
        if(sum < Min2)
        {
            Min2 = sum;
        }
        
        return;
    }
    
    for(int i = idx; i <= 6; i++)
    {
        if(check2[abs(7-i)] == 1)
        {
            continue;
        }
        
        check2[i] = 1;
        Min_2(sum+dice[i], i+1, cnt+1);
        check2[i] = 0;
    }
} 
 
void Min_3(int sum, int idx, int cnt)
{
    if(cnt == 3) 
    {
        if(sum < Min3)
        {
            Min3 = sum;
        }
        
        return;
    }
    
    for(int i = idx; i <= 6; i++)
    {
        if(check3[abs(7-i)] == 1)
        {
            continue;
        }
        
        check3[i] = 1;
        Min_3(sum+dice[i], i+1, cnt+1);
        check3[i] = 0;
    }
} 
 
int main(void)
{
//    freopen("B1041_input.txt", "r", stdin);
    
    cin >> N;
    
    for(int i = 1; i <= 6; i++)
    {
        cin >> dice[i]; // (1,6) (2,5) (3,4) 평행 
    }
    
    if(N == 1)
    {
        sort(dice+1, dice+7);
        
        long long sum = 0;
        for(int i = 1; i <= 5; i++)
        {
            sum += dice[i];
        }
        
        cout << sum;
    }
    else
    {
        Min_1();
        Min_2(0, 1, 0);    
        Min_3(0, 1, 0);
 
        long long Min1_Sum = Min1 * (N-2) * (N-1) * 4 + Min1 * (N-2) * (N-2);
        long long Min2_Sum = Min2 * (N-1) * 4 + Min2 * (N-2) * 4;
        long long Min3_Sum = Min3 * 4;
    
        cout << Min1_Sum + Min2_Sum + Min3_Sum;   
    }
    
    return 0;
}
cs
저작자표시

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

[백준 1018] 체스판 다시 칠하기 (Brute Force) (C/C++)  (0) 2020.03.24
[백준 1251] 단어 나누기 (조합) (C/C++) (★)  (0) 2020.03.23
[백준 15683] 감시 (순열) (C/C++) (★★★)  (1) 2019.11.21
[백준 15684] 사다리 조작 (조합) (C/C++) (★★★)  (2) 2019.11.20
[백준 15686] 연산자 끼워넣기(2) (순열) (C/C++)  (0) 2019.11.20
#include <stdio.h>
#include <iostream>
using namespace std;
 
int map[10][10];
int direct[10];
int N, M;
int Min = 99999999;
 
int cctv[10];
int cctvCnt;
pair<int, int> cctvPos[10];
 
int dx[4] = {-1, 1, 0, 0}; // 상하좌우
int dy[4] = {0, 0, -1, 1}; // 상하좌우 
 
void copy(int mapCopy[10][10])
{
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            mapCopy[i][j] = map[i][j];
        }
    }
}
 
void back_up(int mapCopy[10][10])
{
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            map[i][j] = mapCopy[i][j];
        }
    }
}
 
int safe(int x, int y)
{
    if(x >= 0 && y >= 0 && x < N && y < M)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
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;
}
 
void cctv1(int x, int y, int dir)
{
    while(1)
    {
        int xpos = x+dx[dir];
        int ypos = y+dy[dir];
            
        if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 6)
        {
            map[xpos][ypos] = 7;
            x = xpos;
            y = ypos;
        }
        else
        {
            break;
        }
    }    
} 
 
void cctv2(int x, int y, int dir)
{    
    if(dir == 0 || dir == 1) // 상하 
    {
        for(int i = 0; i < 2; i++)
        {
            int tempx = x;
            int tempy = y;
            
            while(1)
            {
                int xpos = tempx+dx[i];
                int ypos = tempy+dy[i];
                
                if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 6)
                {
                    map[xpos][ypos] = 7;
                    tempx = xpos;
                    tempy = ypos;
                }    
                else
                {
                    break;
                }
            }    
        }
    }
    else if(dir == 2 || dir == 3) // 좌우 
    {
        for(int i = 2; i < 4; i++)
        {
            int tempx = x;
            int tempy = y;
            
            while(1)
            {
                int xpos = tempx+dx[i];
                int ypos = tempy+dy[i];
                
                if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 6)
                {
                    map[xpos][ypos] = 7;
                    tempx = xpos;
                    tempy = ypos;
                }    
                else
                {
                    break;
                }
            }    
        }
    }
} 
 
void cctv3(int x, int y, int dir)
{
    if(dir == 0) // ㄴ모양 
    {
        int dx[2] = {-1, 0}; // 상우 
        int dy[2] = {0, 1};  // 상우
         
        for(int i = 0; i < 2; i++)
        {
            int tempx = x;
            int tempy = y;
            
            while(1)
            {
                int xpos = tempx+dx[i];
                int ypos = tempy+dy[i];
                
                if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 6)
                {
                    map[xpos][ypos] = 7;
                    tempx = xpos;
                    tempy = ypos;
                }    
                else
                {
                    break;
                }
            }    
        }
    }
    else if(dir == 1) //「 모양 
    {
        int dx[2] = {0, 1};  // 우하 
        int dy[2] = {1, 0};  // 우하 
        
        for(int i = 0; i < 2; i++)
        {
            int tempx = x;
            int tempy = y;
            
            while(1)
            {
                int xpos = tempx+dx[i];
                int ypos = tempy+dy[i];
                
                if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 6)
                {
                    map[xpos][ypos] = 7;
                    tempx = xpos;
                    tempy = ypos;
                }    
                else
                {
                    break;
                }
            }    
        }
    }
    else if(dir == 2) // ㄱ모양 
    {
        int dx[2] = {0, 1};  // 좌하 
        int dy[2] = {-1, 0}; // 좌하 
        
        for(int i = 0; i < 2; i++)
        {
            int tempx = x;
            int tempy = y;
            
            while(1)
            {
                int xpos = tempx+dx[i];
                int ypos = tempy+dy[i];
                
                if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 6)
                {
                    map[xpos][ypos] = 7;
                    tempx = xpos;
                    tempy = ypos;
                }    
                else
                {
                    break;
                }
            }    
        }
    }
    else if(dir == 3) // 」모양 
    {
        int dx[2] = {-1, 0}; // 상좌 
        int dy[2] = {0, -1}; // 상좌 
        
        for(int i = 0; i < 2; i++)
        {
            int tempx = x;
            int tempy = y;
            
            while(1)
            {
                int xpos = tempx+dx[i];
                int ypos = tempy+dy[i];
                
                if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 6)
                {
                    map[xpos][ypos] = 7;
                    tempx = xpos;
                    tempy = ypos;
                }    
                else
                {
                    break;
                }
            }    
        }
    }
} 
 
void cctv4(int x, int y, int dir)
{
    if(dir == 0) // ㅗ모양 
    {
        int dx[3] = {-1, 0, 0}; // 상좌우 
        int dy[3] = {0, -1, 1}; // 상좌우 
        
        for(int i = 0; i < 3; i++)
        {
            int tempx = x;
            int tempy = y;
            
            while(1)
            {
                int xpos = tempx+dx[i];
                int ypos = tempy+dy[i];
                
                if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 6)
                {
                    map[xpos][ypos] = 7;
                    tempx = xpos;
                    tempy = ypos;
                }    
                else
                {
                    break;
                }
            }    
        }
    }
    else if(dir == 1) // ㅏ모양 
    {
        int dx[3] = {-1, 1, 0}; // 상하우 
        int dy[3] = {0, 0, 1};  // 상하우 
        
        for(int i = 0; i < 3; i++)
        {
            int tempx = x;
            int tempy = y;
            
            while(1)
            {
                int xpos = tempx+dx[i];
                int ypos = tempy+dy[i];
                
                if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 6)
                {
                    map[xpos][ypos] = 7;
                    tempx = xpos;
                    tempy = ypos;
                }    
                else
                {
                    break;
                }
            }    
        }
    }
    else if(dir == 2) // ㅜ모양 
    {
        int dx[3] = {0, 0, 1};  // 좌우하 
        int dy[3] = {-1, 1, 0}; // 좌우하 
        
        for(int i = 0; i < 3; i++)
        {
            int tempx = x;
            int tempy = y;
            
            while(1)
            {
                int xpos = tempx+dx[i];
                int ypos = tempy+dy[i];
                
                if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 6)
                {
                    map[xpos][ypos] = 7;
                    tempx = xpos;
                    tempy = ypos;
                }    
                else
                {
                    break;
                }
            }        
        }
    }
    else if(dir == 3) // ㅓ모양 
    {
        int dx[3] = {-1, 1, 0}; // 상하좌 
        int dy[3] = {0, 0, -1};  // 상하좌 
        
        for(int i = 0; i < 3; i++)
        {
            int tempx = x;
            int tempy = y;
            
            while(1)
            {
                int xpos = tempx+dx[i];
                int ypos = tempy+dy[i];
                
                if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 6)
                {
                    map[xpos][ypos] = 7;
                    tempx = xpos;
                    tempy = ypos;
                }    
                else
                {
                    break;
                }
            }    
        }
    }
} 
 
void cctv5(int x, int y, int dir)
{
    for(int i = 0; i < 4; i++)
    {
        int tempx = x;
        int tempy = y;
        
        while(1)
        {
            int xpos = tempx+dx[i];
            int ypos = tempy+dy[i];
            
            if(safe(xpos, ypos) == 1 && map[xpos][ypos] != 6)
            {
                map[xpos][ypos] = 7;
                tempx = xpos;
                tempy = ypos;
            }    
            else
            {
                break;
            }
        }    
    }
}
 
void execute_cctv(int cnt)
{
    if(cctv[cnt] == 1)
    {
        cctv1(cctvPos[cnt].first, cctvPos[cnt].second, direct[cnt]);
    }
    else if(cctv[cnt] == 2)
    {
        cctv2(cctvPos[cnt].first, cctvPos[cnt].second, direct[cnt]);
    }
    else if(cctv[cnt] == 3)
    {
        cctv3(cctvPos[cnt].first, cctvPos[cnt].second, direct[cnt]);
    }
    else if(cctv[cnt] == 4)
    {
        cctv4(cctvPos[cnt].first, cctvPos[cnt].second, direct[cnt]);
    }
    else if(cctv[cnt] == 5)
    {
        cctv5(cctvPos[cnt].first, cctvPos[cnt].second, direct[cnt]);
    }
}
 
void permutation(int cnt)
{
    if(cnt == cctvCnt)
    {    
        // print
//        for(int i = 0; i < N; i++)
//        {
//            for(int j = 0; j < M; j++)
//            {
//                cout << map[i][j] << " ";
//            }
//            cout << endl;
//        }
//        cout << endl;
        
        int val = zeroCount();
        
        if(val < Min)
        {
            Min = val;
            // print
//            cout << Min << endl;
//            for(int i = 0; i < N; i++)
//            {
//                for(int j = 0; j < M; j++)
//                {
//                    cout << map[i][j] << " ";
//                }
//                cout << endl;
//            }
//            cout << endl;
        }
        
        return;
    }
    
    // 방향에 대한 중복순열 (0 ~ 4 // 0, 90, 180, 270) 
    for(int i = 0; i < 4; i++)
    { 
        int mapCopy[10][10];
        copy(mapCopy);
        
        direct[cnt] = i;
        execute_cctv(cnt);
        permutation(cnt+1);
    
        back_up(mapCopy);
    }
}
 
int main(void)
{
//    freopen("B15683_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]);
                
            if(map[i][j] != 0 && map[i][j] != 6)
            {
                cctv[cctvCnt] = map[i][j];
                cctvPos[cctvCnt].first = i;
                cctvPos[cctvCnt++].second = j;
            }
        }
    } 
    
    permutation(0);
    
    printf("%d", Min);
    
    return 0;
} 
cs
저작자표시

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

[백준 1251] 단어 나누기 (조합) (C/C++) (★)  (0) 2020.03.23
[백준 1041] 주사위 (조합) (C/C++)  (0) 2019.12.18
[백준 15684] 사다리 조작 (조합) (C/C++) (★★★)  (2) 2019.11.20
[백준 15686] 연산자 끼워넣기(2) (순열) (C/C++)  (0) 2019.11.20
[백준 16198] 에너지 모으기 (순열) (C/C++) (★★)  (0) 2019.11.20
#include <stdio.h>
#include <iostream>
using namespace std;
 
int visited[35][15];
int row, col, num;
int flag;
int Min = 9999999;
 
pair<int, int> candidate[400];
int candidateCnt;
 
int check()
{
    for(int i = 1; i <= col; i++)
    {
        int x = 1;
        int y = i;
        
        while(1)
        {
            if(visited[x][y] == 0 && visited[x][y-1] == 0)
            {
                x++;
            }
            else if(visited[x][y] == 1)
            {
                x++;
                y++;
            }
            else if(visited[x][y-1] == 1)
            {
                x++;
                y--;
            }
            
            if(x == row+1)
            {
                break;
            }
        }
        
        if(y != i)
        {
            return 0;
        }
    }    
    
    return 1;
}
 
void combination(int idx, int cnt)
{
    if(cnt > 3)
    {
        return;
    }
    
    if(check() == 1)
    {
        if(cnt < Min)
        {
            Min = cnt;
        }
        
        return;
    }
    
    for(int i = idx; i < candidateCnt; i++)
    {
        int x = candidate[i].first;
        int y = candidate[i].second;
        
        if(visited[x][y-1] == 1 || visited[x][y+1] == 1 || visited[x][y] == 1)
        {
            continue;
        }
        else
        {
            visited[x][y] = 1;
            combination(i+1, cnt+1);
            visited[x][y] = 0;
        }
    }
}
 
int main(void)
{
//    freopen("B15684_input.txt", "r", stdin);
    
    scanf("%d %d %d", &col, &num, &row);
    
    for(int i = 1; i <= num; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        visited[a][b] = 1;
    }
    
    for(int i = 1; i <= row; i++)
    {
        for(int j = 1; j <= col; j++)
        {
            if(visited[i][j] == 0)
            {
                candidate[candidateCnt].first = i;
                candidate[candidateCnt++].second = j;
            }
        }
    }
    
    combination(0, 0);
    
    if(Min > 3)
    {
        cout << -1;
    }
    else
    {
        cout << Min;
    }
    
    return 0;
}
cs
저작자표시

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

[백준 1041] 주사위 (조합) (C/C++)  (0) 2019.12.18
[백준 15683] 감시 (순열) (C/C++) (★★★)  (1) 2019.11.21
[백준 15686] 연산자 끼워넣기(2) (순열) (C/C++)  (0) 2019.11.20
[백준 16198] 에너지 모으기 (순열) (C/C++) (★★)  (0) 2019.11.20
[백준 14502] 연구소 (조합) (C/C++) (★★)  (0) 2019.11.20
#include <stdio.h>
#include <iostream>
using namespace std;
 
// 백준문제 14888과 동일, oper의 크기와 visited의 크기만 늘려주면 됨 
int num[15];
int oper[50];
int choice[15];
int visited[50];
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("B15686_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' 카테고리의 다른 글

[백준 15683] 감시 (순열) (C/C++) (★★★)  (1) 2019.11.21
[백준 15684] 사다리 조작 (조합) (C/C++) (★★★)  (2) 2019.11.20
[백준 16198] 에너지 모으기 (순열) (C/C++) (★★)  (0) 2019.11.20
[백준 14502] 연구소 (조합) (C/C++) (★★)  (0) 2019.11.20
[백준 14888] 연산자 끼워넣기 (순열) (C/C++)  (0) 2019.11.20

+ Recent posts

티스토리툴바