예산 관리

 

정보 선생님은 예산이 많은 부서에서 일하고 있다. 학기말이 가까워지면서 부서의 예산을 가급적 모두 집행해야 될 상황이 되었다.   정보 선생님은 예산 범위를 넘지 않는 선에서 다양한 활동을 하고 싶어 한다. 지금 남은 예산(B)이 40이고(단위:만원), 예산을 사용할 수 있는 활동(n)이 6개가 있다.   6개의 활동에 각각 드는 비용은 7, 13, 17, 19, 29, 31이다. 여기서 40을 채울 수 있는 활동의 개수는 상관이 없다. 40을 넘지 않는 범위에서 활동 비용을 조합해보면,                               7 + 13 + 17 = 37                                                            7 + 31 = 38                                                            7 + 13 + 19 = 39                                                           ... 따라서 40을 초과하지 않으면서 예산을 최대로 사용할 수 있는 비용은 39이다. 정보 선생님을 도와 줄 수 있는 프로그램을 작성하시오. 입력  첫째 줄에 남은 예산(B)이 입력된다. ( 10 <= B <= 35,000 )  둘째 줄에 예산을 사용할 수 있는 활동의 수(n)가 입력된다. (1 <= n <= 21 )  셋째 줄에 공백을 기준으로 n개의 활동비가 양의 정수로 입력된다. 출력  남은 예산을 초과하지 않으면서 최대로 사용할 수 있는 비용액을 출력한다. 입력 예 40 6 7 13 17 19 29 31 출력 예  39

 

 

 

f(i, sum) = i번째 활동을 고려할 때, i-1까지 활동비용의 합계가 sum인 경우
#include <stdio.h>
int B/*예산*/, n/*개수*/, act[23], res;

void f(int i, int sum)  // i번활동, i-1까지의 합계

{   

if(i==n+1)   

{     

if(sum<=B && sum>res) //예산 보다는 작고 현재 값보다는 크면.

res=sum ;

return;

}

f(i+1, sum+act[i]); // i번째 활동을 포함하거나

f(i+1, sum);         // 포함하지 않 거나

}
int main() {

int i;

scanf("%d %d", &B, &n);

for(i=1; i<=n; i++)

scanf("%d", &act[i]);

f(1, 0);

printf("%d", res);

return 0;

}

 

배낭 문제(S)

f(i, r) = i~n번째 물건까지 고려했을 때, 남은 무게가 r인 가치의 최대 합
#include <stdio.h>
int W, n, i, j, w[102], v[102]; 
int max(int a, int b) {return a>b ? a:b;}
int f(int i/*물건번호*/, int r/*남은무게*/)
{ 
    if (i == n + 1)      
        return 0;  
    else if (r<w[i])     //만약 남은무게가 현재 물건크기보다 작다면.. 다음물건으로 진행
        return f(i + 1, r);  
    else     
        return max(f(i + 1, r), f(i + 1, r-w[i]) + v[i]);
}  

int main()
{
 scanf("%d %d", &n, &W);  
 for (i = 1; i <= n; i++)   
  scanf("%d%d", &w[i], &v[i]);  
 printf("%d", f(1, W));  
 return 0;
}

 

더하기

int T, N/*개수*/, K/*합계*/;

int d[20];

int sol;

int DFS(int x, int sum)

{

if (sum == K) return 1;

if (x >= N) return 0;

if (sum + d[x] <= K)

{

if (DFS(x + 1, sum + d[x]) == 1) return 1;

}

if (DFS(x + 1, sum) == 1) 

{ return 1; }

return 0;

}

int main(void)

{

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

int i;

scanf("%d", &T);

while (T--)

{

scanf("%d %d", &N, &K);

for (i = 0; i<N; i++)

{

scanf("%d", &d[i]);

}

if (DFS(0, 0)) printf("YES\n");

else printf("NO\n");

}

return 0;

}

 

//등산로

#include <stdio.h>

int N;//산의크기(지도의크기)

int DY;//정상의세로위치

int DX;//정상의가로위치

int map[110][110];//산의정보

int D[110][110];//힘을계산해서갱신할배열

struct st {

int r, c;//r:세로위치, c:가로위치

};

#define MAXQ (110*110*10)

#define INF (0x7FFFFFFF)

struct st queue[MAXQ];

int wp, rp;

int In_Queue(int r, int c) {

if (wp >= MAXQ) return 0;//저장실패

queue[wp].r = r;

queue[wp++].c = c;

return 1;//성공

}

int Out_Queue(struct st *p) {

if (wp == rp) return 0;//읽기실패

*p = queue[rp++];

return 1;//성공

}

int BFS(void) {

int rr[] = { -1, 1, 0, 0 };

int cc[] = { 0, 0, -1, 1 };

int i, j, temp, r, c;

struct st p;

//D배열INF값으로초기화, 시작위치를큐에저장

for (i = 0; i<N + 2; i++) {//세로

for (j = 0; j<N + 2; j++) {//가로

if ((i == 0) || (j == 0) || (i == N + 1) || (j == N + 1)) {

In_Queue(i, j);

D[i][j] = 0;

}

else D[i][j] = INF;

}

}

while (Out_Queue(&p)) {

for (i = 0; i<4; i++) {

r = p.r + rr[i];//p.r은현재위치, r은이동할위치

c = p.c + cc[i];//p.c는현재위치, c는이동할위치

if ((r>0) && (c>0) && (r<N + 1) && (c<N + 1)) {//이동가능

temp = map[p.r][p.c] - map[r][c];//현재위치높이- 이동할위치의높이

if (temp < 0) temp *= temp; //오르막길(차의제곱만큼힘이듦)

temp += D[p.r][p.c];

if (D[r][c] > temp) {//기존보다힘이적게들때만갱신

D[r][c] = temp;

In_Queue(r, c);

}

}

}

}

return D[DY][DX];

}

int main(void) {

int i, j, sol;

scanf("%d", &N);

scanf("%d %d", &DY, &DX);

for (i = 1; i <= N; i++) {

for (j = 1; j <= N; j++) {

scanf("%d", &map[i][j]);

}

}

sol = BFS();

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

return 0;

}

//영역구하기

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]);

}

}