Shining...

기본적으로 풀기 어려우면 무조건 부분집합 돌려서 각 값을 대입해서 최대 최소값 구하고 본다. 그러면 중간이라도 간다.

#include <stdio.h>

int data[]={1,2,3,4};
int flag[]={0,0,0,0};

void powerset(int n,int depth)
{
    if(n==depth){
        int i;
        printf("{");
        for(i=0;i<n;i++){
            if(flag[i]==1)printf("%d ",data[i]);
        }
        printf("}\n");
        return;
    }
    flag[depth]=1;
    powerset(n,depth+1);
    flag[depth]=0;
    powerset(n,depth+1);
}

int main()
{
    powerset(sizeof(data)/sizeof(int),0);
    return 0;    
}

첫 줄은 배달해야 하는 장소의 수 N(1≤N≤12)이 주어진다. 이때, 출발지(회사)는 1번이다. 

둘째 줄은 N X N 크기의 장소와 장소를 이동하는 비용(0 ≤ 비용＜ 100)이 한 칸씩의 공백으로 구분하여 주어진다. 비용은 양방향이 아니라 단방향으로 가기 위한 비용이다. 예들 들어 첫 번째 행 두 번째 열에 적힌 비용은 1번 장소에서 2번 장소로 이동하기 위한 비용을 의미하며, 2번 장소에서 1번 장소로 이동하기 위한 비용은 두 번째 행 첫 번째 열에 주어진다.
장소 사이에 이동할 수 있는 방법이 없다면 비용을 0으로 표시한다.

회사에서 출발하여 오늘 배달해야 하는 모든 장소를 한 번씩 들러 물건을 배달하고 회사에 돌아오기 위한 최소의 비용을 출력한다.

[Copy] 5 0 14 4 10 20 14 0 7 8 7 4 5 0 7 16 11 7 9 0 2 18 7 17 4 0

[Copy] 30

테스트 코드를 이 배열로하면 문제가 별 안보이지만, 아래아래 6짜리로 하면 예외 케이스를 확인할 수 있다. 이것만 유의하면 문제 없음

예산관리와 유의하여 볼 것.

5 

0 14 4 10 20 

14 0 7 8 7 

4 5 0 7 16 

11 7 9 0 2 

18 7 17 4 0

이 배열로하면, 

6

0 93 23 32 39 46 

0 0 7 58 59 13 

40 98 0 14 33 98 

3 39 0 0 13 16 

51 25 19 88 0 47 

65 81 63 0 6 0 

#include<stdio.h>

int N;

int map[110][110];

int sol = 0x7fffffff;

int max = 0x7fffffff;

int chk[13];

void dfs(int V, int r, int cost) // V는 접점의 개수를 counting, r은 각 들어갈 열, cost는 총 비용

{

if (cost >= sol) return; //만약 현재값이 sol보다 커버리면 아무의미 없으니까 skip

if (V >= N)

{

if (map[r][1] == 0) { 

return; /* 1로 돌아갈때, 돌아올 수 못한 다는 것을 의미 */

}

cost += map[r][1];//비용 증가

if (cost < sol) sol = cost;

return;

}

for (int i = 2; i <= N; i++)

{

if (r == i) continue;//똑같은 곳에서 똑같은 곳으로 갈일은 없으니 skip

if (!chk[i] && map[r][i])//들러보지 않은 곳

{

chk[i] = 1;

dfs(V + 1, i, cost + map[r][i]);

chk[i] = 0;

}

}

}

void main()

{

freopen("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]);

dfs(1, 1, 0);

printf("%d", sol != max ? sol : 0);

}

http://www.jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=729&sca=30&sfl=wr_subject

#include<stdio.h>

/*

눈금의 간격이 1인 M×N(M,N≤100)크기의 모눈종이가 있다.

이 모눈종이 위에 눈금에 맞추어 K개의 직사각형을 그릴 때, 이들 K개의 직사각형의 내부를 제외한 나머지 부분이

몇 개의 분리된 영역으로 나누어진다.

예를 들어 M=5, N=7 인 모눈종이 위에 <그림 1>과 같이 직사각형 3개를 그렸다면,

그 나머지 영역은 <그림 2>와 같이 3개의 분리된 영역으로 나누어지게 된다.

efc6e5f9d670c6da62174cf11a66a8c2_1449731

<그림 2>와 같이 분리된 세 영역의 넓이는 각각 1, 7, 13이 된다.

M, N과 K 그리고 K개의 직사각형의 좌표가 주어질 때, K개의 직사각형 내부를 제외한 나머지 부분이

몇 개의 분리된 영역으로 나누어지는지, 그리고 분리된 각 영역의 넓이가 얼마인지를 구하여 이를 출력하는 프로그램을 작성하시오.

[Copy] 5 7 3 0 2 4 4 1 1 2 5 4 0 6 2

[Copy] 3 1 7 13

*/

typedef struct {

int sX;

int sY;

int eX;

int eY;

} _pos;

_pos POS[1000];

int map[100][100] = { 0, };

int nCount = 0;

int nArea = 0;

int Area[100] = { 0, };

int sero;

int garo;

int idx = -1;

void find(int se, int ga)

{

nCount++;

if (se - 1 >= 0 && map[se - 1][ga] == 0) 

{

map[se - 1][ga] = idx;

find(se - 1, ga); 

}

if (se + 1 < sero && map[se + 1][ga] == 0)

{ 

map[se + 1][ga] = idx; 

find(se + 1, ga); 

}

if (ga - 1 >= 0 && map[se][ga - 1] == 0) 

{ 

map[se][ga - 1] = idx; 

find(se, ga - 1); 

}

if (ga + 1 < garo && map[se][ga + 1] == 0)

{ 

map[se][ga + 1] = idx;

find(se, ga + 1); 

}

//int Dy[] = { 1, 0,0, -1 };

//int Dx[] = { 0,-1, 1, 0 };

//nArea++;

//int head = 0;

//int tail = 1;

//while (1)

//{

// for (int x = 0; x < 4; x++)

// {

// int tmpX = garo + Dx[x];

// int tmpY = sero + Dy[x];

// if (map[tmpY][tmpX] == 0)

// {

// map[tmpY][tmpX] == -1;

// nCount++;

// }

// }

//}

}

void main()

{

int count;

// freopen("input.txt", "r", stdin);

scanf("%d %d %d", &sero, &garo, &count);

for (int i = 0; i < count; i++)

{

scanf("%d %d %d %d", &POS[i].sX, &POS[i].sY, &POS[i].eX, &POS[i].eY);

int tmpX = POS[i].eX - POS[i].sX;

int tmpY = POS[i].eY - POS[i].sY;

for (int y = POS[i].sY; y < tmpY + POS[i].sY; y++)

{

for (int x = POS[i].sX; x < tmpX + POS[i].sX; x++)

{

map[y][x]++;

}

}

}

for (int i = 0; i< sero; i++)

{

for (int j = 0; j < garo; j++)

{

if (map[i][j] == 0)

{

map[i][j] = --idx;

find(i, j);

Area[nArea++] = nCount;

nCount = 0;

}

}

}

for (int i = 0; i < nArea-1; i++)

{

for (int j = 0; j < nArea - 1 -i; j++)

{

if (Area[j] > Area[j + 1])

{

int tmp = Area[j];

Area[j] = Area[j + 1];

Area[j + 1] = tmp;

}

}

}

printf("%d\n", nArea);

for (int i = 0; i < nArea; i++)

{

printf("%d ", Area[i]);

}

}