#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 map[500][500];
int visited[500][500];
int Max;
int N, M;
 
int dx[4] = {-1, 1, 0, 0}; // 상하좌우
int dy[4] = {0, 0, -1, 1}; // 상하좌우 
 
int safe(int x, int y)
{
    if(x >= 0 && y >= 0 && x < N && y < M)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void check(int i, int j)
{
    if(safe(i+1, j+2) == 1)
    {
        int val = map[i][j] + map[i][j+1] + map[i][j+2] + map[i+1][j+1]; // ㅜ 
        
        if(val > Max)
        {
            Max = val;
        }    
    } 
    
    if(safe(i-1, j+2) == 1)
    {
        int val = map[i][j] + map[i][j+1] + map[i][j+2] + map[i-1][j+1]; // ㅗ 
        
        if(val > Max)
        {
            Max = val;
        }    
    } 
    
    if(safe(i+2, j-1) == 1)
    {
        int val = map[i][j] + map[i+1][j] + map[i+2][j] + map[i+1][j-1]; // ㅓ 
        
        if(val > Max)
        {
            Max = val;
        }    
    }
    
    if(safe(i+2, j+1) == 1)
    {
        int val = map[i][j] + map[i+1][j] + map[i+2][j] + map[i+1][j+1]; // ㅏ 
        
        if(val > Max)
        {
            Max = val;
        }    
    }
}
 
void DFS(int sum, int x, int y, int cnt)
{
    if(cnt == 4)
    {
        if(sum > Max)
        {
            Max = sum;
        }
        
        return;
    }
    
    for(int i = 0; i < 4; i++)
    {
        int xpos = x+dx[i];
        int ypos = y+dy[i];
        
        if(safe(xpos, ypos) == 1 && visited[xpos][ypos] == 0)
        {
            visited[xpos][ypos] = 1;
            DFS(sum + map[xpos][ypos], xpos, ypos, cnt+1);
            visited[xpos][ypos] = 0;
        }
    }
}
 
int main(void)
{
//    freopen("B14500_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]);
        }
    }
    
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < M; j++)
        {
            visited[i][j] = 1;
            DFS(map[i][j], i, j, 1);
            check(i, j);
            visited[i][j] = 0;
        }
    }
        
    printf("%d", Max);
    
    return 0;
}
 cs
저작자표시 (새창열림)

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

[백준 2667] 단지번호 붙이기 (DFS) (C/C++)  (0) 2020.01.26
[백준 10451] 순열 사이클 (DFS) (C/C++)  (0) 2020.01.26
[백준 13023] ABCDE (DFS) (C/C++)  (0) 2019.12.08
[백준 10971] 외판원 순회2 (DFS) (C/C++) (★)  (0) 2019.11.19
[백준 2210] 숫자판 점프 (DFS) (C/C++)  (1) 2019.11.18

1.

#include <stdio.h>
#include <iostream>
using namespace std;
 
int city[15][15];
int visited[15];
int N;
int Min = 99999999;
 
int check()
{
    for(int i = 1; i < N; i++)
    {
        if(visited[i] == 0)
        {
            return 0;
        }
    }
    
    return 1;
}
 
void DFS(int sum, int cur)
{
    // 1번 ~ N-1번 도시를 모두 방문한 경우
    if(check() == 1)
    {
        // 0번 마을까지의 경로가 존재한다면 
        if(city[cur][0] != 0)
        {
            sum += city[cur][0];
        
            if(sum < Min)
            {
                Min = sum;
            }    
        }
        
        return;
    }
    
    for(int i = 1; i < N; i++)
    {
        if(city[cur][i] != 0 && visited[i] == 0)
        {
            visited[i] = 1;
            DFS(sum + city[cur][i], i);
            visited[i] = 0;
        }
    }
}
 
int main(void)
{
//    freopen("B10971_input.txt", "r", stdin);
    
    scanf("%d", &N);
    
    // 0번 ~ N-1번 도시 
    for(int i = 0; i < N; i++)
    {
        for(int j = 0; j < N; j++)
        {
            scanf("%d", &city[i][j]);
        }
    }
    
    // 0 →1 →2 →3 →4 →0  시작점이 0인 최소비용 루트가 있다고 가정해보자. 이 때 'A원'의 비용이 들었다면, 
    // 2 →3 →4 →0 →1 →2  시작점이 2인 최소비용 루트는 시작점과 관계없이 'A원'의 비용이 든다. 
    DFS(0, 0);    
    
    cout << Min;
    
    return 0;
}
 cs

 

2.

#include <stdio.h>
#include <iostream>
using namespace std;
 
int city[15][15];
int visited[15];
int N;
int Min = 99999999;
 
int check()
{
    for(int i = 1; i <= N; i++)
    {
        if(visited[i] == 0)
        {
            return 0;
        }
    }
    
    return 1;
}
 
void DFS(int sum, int start, int arrive)
{
    if(check() == 1)
    {
        // 출발점으로 돌아올때 0이 아닌 조건을 추가해주는것이 중요 
        if(city[start][arrive] != 0)
        {
            sum += city[start][arrive];
        
            if(sum < Min)
            {
                Min = sum;
            }    
        }
        
        return;
    }
    
    for(int i = 1; i <= N; i++)
    {
        if(city[start][i] != 0 && visited[i] == 0)
        {
            visited[i] = 1;
            DFS(sum + city[start][i], i, arrive);
            visited[i] = 0;
        }
    }
}
 
int main(void)
{
//    freopen("B10971_input.txt", "r", stdin);
    
    scanf("%d", &N);
    
    for(int i = 1; i <= N; i++)
    {
        for(int j = 1; j <= N; j++)
        {
            scanf("%d", &city[i][j]);
        }
    }
    
    for(int i = 1; i <= N; i++)
    {        
        visited[i] = 1;
        DFS(0, i, i);    
        visited[i] = 0;
    }
    
    cout << Min;
    
    return 0;
}
 cs
저작자표시 (새창열림)

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

[백준 2667] 단지번호 붙이기 (DFS) (C/C++)  (0) 2020.01.26
[백준 10451] 순열 사이클 (DFS) (C/C++)  (0) 2020.01.26
[백준 13023] ABCDE (DFS) (C/C++)  (0) 2019.12.08
[백준 14500] 테트로미노 (DFS) (C/C++) (★)  (0) 2019.11.19
[백준 2210] 숫자판 점프 (DFS) (C/C++)  (1) 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;
 
int map[10][10];
int choice[10];
int visited[1000000];
int ans;
 
int dx[4] = {-1, 1, 0, 0}; // 상하좌우 
int dy[4] = {0, 0, -1, 1}; // 상하좌우
 
int safe(int x, int y)
{
    if(x >= 0 && y >= 0 && x < 5 && y < 5)
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
 
void DFS(int x, int y, int cnt)
{    
    if(cnt == 7)
    {
        int val = choice[0]*100000 + choice[1]*10000 + choice[2]*1000 + choice[3]*100 + choice[4]*10 + choice[5]*1;
        
        if(visited[val] == 0)
        {
            visited[val] = 1;
            ans++;
        }
        
        return;
    }
    
    for(int i = 0; i < 4; i++)
    {
        int xpos = x+dx[i];
        int ypos = y+dy[i];
        
        if(safe(xpos, ypos) == 1)
        {
            choice[cnt] = map[xpos][ypos];
            DFS(xpos, ypos, cnt+1);    
        }
    }
}
 
int main(void)
{
//    freopen("B2210_input.txt", "r", stdin);
    
    for(int i = 0; i < 5; i++)
    {
        for(int j = 0; j < 5; j++)
        {
            scanf("%d", &map[i][j]);
        }
    }
    
    for(int i = 0; i < 5; i++)
    {
        for(int j = 0; j < 5; j++)
        {
            DFS(i, j, 0);
        }
    }
    
    cout << ans;
    
    return 0;
}
cs
저작자표시 (새창열림)

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

[백준 2667] 단지번호 붙이기 (DFS) (C/C++)  (0) 2020.01.26
[백준 10451] 순열 사이클 (DFS) (C/C++)  (0) 2020.01.26
[백준 13023] ABCDE (DFS) (C/C++)  (0) 2019.12.08
[백준 14500] 테트로미노 (DFS) (C/C++) (★)  (0) 2019.11.19
[백준 10971] 외판원 순회2 (DFS) (C/C++) (★)  (0) 2019.11.19
#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

+ Recent posts

티스토리툴바