#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
#include <stdio.h>
 
int height[7];
int input[9];
int flag;
 
void combination(int sum, int cnt, int idx)
{        
    if(cnt == 7)
    {        
        if(sum == 100)
        {
            flag = 1;
            return;
        }
        else
        {
            return;
        }
    }
    
    for(int i = idx; i < 9; i++)
    {
        height[cnt] = input[i];
        combination(sum + height[cnt], cnt+1, i+1);
        if(flag == 1)
        {
            return;
        }
    }
}
 
int main(void)
{
//    freopen("B2309_input.txt", "r", stdin);
    
    for(int i = 0; i < 9; i++)
    {
        scanf("%d", &input[i]);
    }
    
    combination(0, 0, 0);
    
    // 버블 정렬 -> 오름차순 출력을 위해 
    for(int i = 6; i > 0; i--)
    {
        for(int j = 0; j < i; j++)
        {
            if(height[j] > height[j+1])
            {
                int temp = height[j];
                height[j] = height[j+1];
                height[j+1] = temp;
            }
        }
    }
    
    for(int i = 0; i < 7; i++)
    {
        printf("%d\n", height[i]);
    }
    
    return 0;
}
cs
저작자표시 (새창열림)

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

[백준 15661] 링크와 스타트 (조합) (C/C++) (★★)  (0) 2019.11.18
[백준 15686] 치킨배달 (조합) (C/C++)  (0) 2019.11.18
[백준 2529] 부등호 (순열) (C/C++)  (0) 2019.11.18
[백준 15666] N과 M(12) (중복조합) (C/C++)  (0) 2019.11.18
[백준 15665] N과 M(11) (중복순열) (C/C++)  (0) 2019.11.18
#include <stdio.h>
#include <iostream>
#include <string>
#include <math.h>
using namespace std;
 
int num[10];
int visited[10];
 
char sign[9];
int signNum;
 
string Max = "-1";
string Min = "9999999999";
 
int check(int idx)
{
    if(sign[idx] == '<')
    {
        if(num[idx] < num[idx+1])
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }
    else if(sign[idx] == '>')
    {
        if(num[idx] > num[idx+1])
        {
            return 1;
        }
        else
        {
            return 0;
        }
    }
}
 
void permutation(int cnt)
{
    if(cnt == signNum+1)
    {
        for(int i = 0; i < cnt-1; i++)
        {
            if(check(i) == 0)
            {
                return;
            }
        }
        
        string val;
        
        for(int i = 0; i < cnt; i++)
        {
            val += to_string(num[i]);
        }
        
        if(val > Max)
        {
            Max = val;    
        }
        
        if(val < Min)
        {
            Min = val;
        }
        
        return;
    }
    
    for(int i = 0; i <= 9; i++)
    {
        if(visited[i] == 0)
        {
            num[cnt] = i;
            visited[i] = 1;
            permutation(cnt+1);
            visited[i] = 0;    
        }
    }
}
 
int main(void)
{
//    freopen("B2529_input.txt", "r", stdin);
    
    scanf("%d", &signNum);
    for(int i = 0; i < signNum; i++)
    {
        scanf(" %c", &sign[i]);
    }
    
    permutation(0);
 
    cout << Max << endl;
    cout << Min << endl;
    
    return 0;
}
cs
저작자표시 (새창열림)

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

[백준 15686] 치킨배달 (조합) (C/C++)  (0) 2019.11.18
[백준 2309] 일곱 난쟁이 (조합) (C/C++)  (1) 2019.11.18
[백준 15666] N과 M(12) (중복조합) (C/C++)  (0) 2019.11.18
[백준 15665] N과 M(11) (중복순열) (C/C++)  (0) 2019.11.18
[백준 15664] N과 M(10) (조합) (C/C++)  (0) 2019.11.18
#include <stdio.h>
 
int arr[100];
int input[100];
int n, k;
 
void combination(int cnt, int idx)
{    
    if(cnt == k)
    {
        for(int i = 0; i < k; i++)
        {
            printf("%d ", arr[i]);
        }
        printf("\n");
        return;
    }
    
    // 중복값 유무 확인 
    int used[10000] = {0};
    
    for(int i = idx; i < n; i++)
    {
        if(used[input[i]] == 0)
        {
            used[input[i]] = 1;
            arr[cnt] = input[i]; 
            combination(cnt+1, i);
        }
    }
}
 
int main(void)
{
    scanf("%d %d", &n, &k);
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &input[i]);
    }
    
    // input 버블정렬 -> 사전순으로 출력하기 위해서 
    for(int i = n-1; i > 0; i--)
    {
        for(int j = 0; j < i; j++)
        {
            if(input[j] > input[j+1])
            {
                int temp = input[j];
                input[j] = input[j+1];
                input[j+1] = temp;
            }
        }
    }
    
    combination(0, 0);
        
    return 0;
}
 
cs
저작자표시 (새창열림)

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

[백준 2309] 일곱 난쟁이 (조합) (C/C++)  (1) 2019.11.18
[백준 2529] 부등호 (순열) (C/C++)  (0) 2019.11.18
[백준 15665] N과 M(11) (중복순열) (C/C++)  (0) 2019.11.18
[백준 15664] N과 M(10) (조합) (C/C++)  (0) 2019.11.18
[백준 15663] N과 M(9) (순열) (C/C++)  (0) 2019.11.18
#include <stdio.h>
 
int arr[100];
int input[100];
int n, k;
 
void combination(int cnt, int idx)
{    
    if(cnt == k)
    {
        for(int i = 0; i < k; i++)
        {
            printf("%d ", arr[i]);
        }
        printf("\n");
        return;
    }
    
    // 중복값 유무 확인 
    int used[10000] = {0};
    
    for(int i = idx; i < n; i++)
    {
        if(used[input[i]] == 0)
        {
            used[input[i]] = 1;
            arr[cnt] = input[i]; 
            combination(cnt+1, i+1);
            arr[cnt] = 0;    
        }
    }
}
 
int main(void)
{
    scanf("%d %d", &n, &k);
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &input[i]);
    }
    
    // input 버블정렬 -> 사전순으로 출력하기 위해서 
    for(int i = n-1; i > 0; i--)
    {
        for(int j = 0; j < i; j++)
        {
            if(input[j] > input[j+1])
            {
                int temp = input[j];
                input[j] = input[j+1];
                input[j+1] = temp;
            }
        }
    }
    
    combination(0, 0);
        
    return 0;
}
 
cs
저작자표시 (새창열림)

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

[백준 2309] 일곱 난쟁이 (조합) (C/C++)  (1) 2019.11.18
[백준 2529] 부등호 (순열) (C/C++)  (0) 2019.11.18
[백준 15666] N과 M(12) (중복조합) (C/C++)  (0) 2019.11.18
[백준 15664] N과 M(10) (조합) (C/C++)  (0) 2019.11.18
[백준 15663] N과 M(9) (순열) (C/C++)  (0) 2019.11.18
#include <stdio.h>
 
int arr[100];
int input[100];
int n, k;
 
void combination(int cnt, int idx)
{    
    if(cnt == k)
    {
        for(int i = 0; i < k; i++)
        {
            printf("%d ", arr[i]);
        }
        printf("\n");
        return;
    }
    
    // 중복값 유무 확인 
    int used[10000] = {0};
    
    for(int i = idx; i < n; i++)
    {
        if(used[input[i]] == 0)
        {
            used[input[i]] = 1;
            arr[cnt] = input[i]; 
            combination(cnt+1, i+1);
        }
    }
}
 
int main(void)
{
    scanf("%d %d", &n, &k);
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &input[i]);
    }
    
    // input 버블정렬 -> 사전순으로 출력하기 위해서 
    for(int i = n-1; i > 0; i--)
    {
        for(int j = 0; j < i; j++)
        {
            if(input[j] > input[j+1])
            {
                int temp = input[j];
                input[j] = input[j+1];
                input[j+1] = temp;
            }
        }
    }
    
    combination(0, 0);
        
    return 0;
}
 
 cs
저작자표시 (새창열림)

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

[백준 2309] 일곱 난쟁이 (조합) (C/C++)  (1) 2019.11.18
[백준 2529] 부등호 (순열) (C/C++)  (0) 2019.11.18
[백준 15666] N과 M(12) (중복조합) (C/C++)  (0) 2019.11.18
[백준 15665] N과 M(11) (중복순열) (C/C++)  (0) 2019.11.18
[백준 15663] N과 M(9) (순열) (C/C++)  (0) 2019.11.18
#include <stdio.h>
 
int arr[100];
int input[100];
int visited[100];
int n, k;
 
void permutation(int cnt)
{
    if(cnt == k)
    {
        for(int i = 0; i < k; i++)
        {
            printf("%d ",arr[i]);
        }
        printf("\n");
        return;
    }
    
    // 중복값 유무 확인 
    int used[10000] = {0};
    
    for(int i = 0; i < n; i++)
    {    
        if(visited[i] == 0 && used[input[i]] == 0)
        {
            used[input[i]] = 1;
            arr[cnt] = input[i];
            visited[i] = 1;
            permutation(cnt+1);
            visited[i] = 0;
        }
    }
}
 
int main(void)
{
    scanf("%d %d", &n, &k);
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &input[i]);
    }
    
    // input 버블정렬 -> 사전순으로 출력하기 위해서 
    for(int i = n-1; i > 0; i--)
    {
        for(int j = 0; j < i; j++)
        {
            if(input[j] > input[j+1])
            {
                int temp = input[j];
                input[j] = input[j+1];
                input[j+1] = temp;
            }
        }
    }
    
    permutation(0);
        
    return 0;
}
 
 cs
저작자표시 (새창열림)

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

[백준 2309] 일곱 난쟁이 (조합) (C/C++)  (1) 2019.11.18
[백준 2529] 부등호 (순열) (C/C++)  (0) 2019.11.18
[백준 15666] N과 M(12) (중복조합) (C/C++)  (0) 2019.11.18
[백준 15665] N과 M(11) (중복순열) (C/C++)  (0) 2019.11.18
[백준 15664] N과 M(10) (조합) (C/C++)  (0) 2019.11.18
#include <vector>
#include <iostream>
#include <math.h>
using namespace std;
 
vector<int> input;
int result[3];
int answer;
 
bool is_prime()
{
    int n = result[0]+result[1]+result[2];
    
    for(int i = 2; i <= sqrt(n); i++)
    {
        if(n % i == 0)
        {
            return false;
        }
    }
    
    return true;
}
 
void DFS(int idx, int cnt)
{
    if(cnt == 3)
    {
        if(is_prime())
        {
            answer++;
        }
        
        return;
    }
    
    for(int i = idx; i < input.size(); i++)
    {
        result[cnt] = input[i];
        DFS(i+1, cnt+1);
    }
}
 
int solution(vector<int> nums) 
{
    input = nums;
    
    DFS(0, 0);
 
    return answer;
}
cs
저작자표시 (새창열림)

'Programmers > Level 2' 카테고리의 다른 글

[프로그래머스 2] 오픈채팅방 (C/C++) (★)  (0) 2020.01.04
[프로그래머스 2] 폰켓몬 (C/C++)  (0) 2020.01.04
[프로그래머스 2] 영어 끝말잇기 (C/C++)  (1) 2019.10.28
[프로그래머스 2] JadenCase 문자열 만들기 (C/C++)  (0) 2019.10.28
[프로그래머스 2] 행렬의 곱셈 (C/C++)  (1) 2019.10.28

+ Recent posts

티스토리툴바