#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
#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 map[401][401];
int N, relation, chk;
 
void floyd()
{
    for(int k = 1; k <= N; k++)
    {
        for(int i = 1; i <= N; i++)
        {
            for(int j = 1; j <= N; j++)
            {
                if(map[i][j] == 0)
                {
                    if(map[i][k] + map[k][j] == -2)
                    {
                        map[i][j] = -1;
                    }
                    else if(map[i][k] + map[k][j] == 2)
                    {
                        map[i][j] = 1;
                    }
                }
            }
        }
    }
}
 
int main(void)
{
//    freopen("B1613_input.txt", "r", stdin);
    
    scanf("%d %d", &N, &relation);
    
    for(int i = 1; i <= relation; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        
        map[a][b] = -1;
        map[b][a] = 1;
    }
    
    floyd();
    
    scanf("%d", &chk);
    
    for(int i = 1; i <= chk; i++)
    {
        int a, b;
        scanf("%d %d", &a, &b);
        
        printf("%d\n", map[a][b]);
    }
        
    return 0;
}
cs
저작자표시

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

[백준 1507] 궁금한 민호 (Floyd-Warshall) (C/C++) (★★)  (0) 2020.02.08
[백준 5567] 결혼식 (Floyd-Warshall) (C/C++)  (0) 2020.02.07
[백준 11404] 플로이드 (Floyd-Warshall) (C/C++)  (0) 2020.02.07
[백준 2644] 촌수계산 (BFS/Floyd-Warshall) (C/C++)  (0) 2019.12.04
[백준 11403] 경로찾기 (Floyd-Warshall) (C/C++)  (0) 2019.11.20
#include <stdio.h>
#include <iostream>
using namespace std;
 
int map[110][110];
int N;
 
void floyd()
{
    for(int k = 1; k <= N; k++)
    {
        for(int i = 1; i <= N; i++)
        {
            for(int j = 1; j <= N; j++)
            {
                if(map[i][k] + map[k][j] == 2)
                {
                    map[i][j] = 1;
                }
            }
        }
    }
}
 
int main(void)
{
//    freopen("B11403_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]);
        }
    }
    
    floyd();
    
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= N; j++)
        {
            printf("%d ", map[i][j]);
        }
        printf("\n");
    }
}
cs
저작자표시

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

[백준 1507] 궁금한 민호 (Floyd-Warshall) (C/C++) (★★)  (0) 2020.02.08
[백준 5567] 결혼식 (Floyd-Warshall) (C/C++)  (0) 2020.02.07
[백준 11404] 플로이드 (Floyd-Warshall) (C/C++)  (0) 2020.02.07
[백준 2644] 촌수계산 (BFS/Floyd-Warshall) (C/C++)  (0) 2019.12.04
[백준 1613] 역사 (Floyd-Warshall) (C/C++) (★)  (0) 2019.11.20
#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

+ Recent posts

티스토리툴바