|
정보 선생님은 예산이 많은 부서에서 일하고 있다. 학기말이 가까워지면서 부서의 예산을 가급적 모두 집행해야 될 상황이 되었다.
정보 선생님은 예산 범위를 넘지 않는 선에서 다양한 활동을 하고 싶어 한다. 지금 남은 예산(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]);
}
}
