Shining...

/*문제 설명

n×n의 행렬로 지형도가 표시된 산이 있다.행렬의 원소의 값은 양의 정수 값으로 그 위치에서의 높이를 말해준다.등산가들은 산의 바깥지역(높이 0)으로부터 정상에 도달하기 위하여 가장 경제적인 루트를 탐색하려고 한다.경제적인 경로란 힘을 가장 적게 들이고 정상까지 올라갈 수 있는 길을 말한다.

예를 보면서 설명해보자.다음은 행렬 Mount[5, 5]로 표시된 산악지형이다.산의 정상은 Mount[3, 3]의 위치에 있으며, 그 높이는 6이다.그리고 이 산의 바깥지역은 모두 해발이 0이다.등산가가 산에 오르는 시작점의 위치는 산의 바깥지역의 어디에서 시작해도 좋다.

등산가는 어떤 한 지역에서 그 위치에 인접한 네 방향(위, 아래, 왼쪽, 오른쪽)으로만 움직일 수 있다.인접한 지역으로 움직일 수 있는 경우는(1) 평지로 이동할 경우, (2) 내려갈 경우, (3) 올라갈 경우의 세 가지이다.이 세 가지 경우에 필요한 "힘"의 양은 다음과 같이 표현될 수 있다.

(1)인접한 같은 높이의 지역을 수평 이동할 경우에는 그냥 평지를 걸어가면 되므로 힘이 전혀 들지 않는다고 가정한다.예를 들면 Mount[5, 2]에서 Mount[5, 3]으로 이동하는 경우와 Mount[4, 5]에서 Mount[5, 5]로 이동하는 경우에는 전혀 힘이 들지 않는다.

(2)내리막길을 따라갈 경우(예를 들면, Mount[2, 3]에서 Mount[2, 2]로 갈 때)에는 그 높이 차이만큼의 힘이 든다.즉 이 경우에는 5 - 3 = 2만큼의 힘이 든다.

(3)오르막길을 오를 경우에는 이동할 두 지역의 높이 차의 제곱만큼의 힘이 든다.즉 Mount[1, 2]에서 Mount[1, 3]으로 갈 경우는(4 - 2)2 = 4 만큼의 힘이 든다.

입력

첫째 줄에는 산의 크기인 Mount[n, n]의 n값이 주어지고, 두 번째 줄에는 정상의 위치 Mount[y, x]의 y, x값이 주어진다.

단, Mount[n, n]에서 n은 100이하이고, 각 지형의 최대 높이는 50이하라고 가정한다.

그 다음 n개의 줄은 산의 크기에 따른 각 지점의 높이가 양의 정수 값으로 주어진다.

출력

첫째 줄에 정상까지 도달하는 가장 경제적인 경로를 따라 올라가는데 사용된 힘을 출력한다.

입력 예시

5

3 3

1 2 4 3 2

1 3 5 4 4

2 3 6 5 1

3 1 4 1 3

2 3 3 5 3

출력 예시

8

도움말

경로는 다음과 같다.

2[1, 5]->3[1, 4]->4[2, 4]->5[3, 4]->6[3, 3]

= 2 * 2 + 1 * 1 + 1 * 1 + 1 * 1 + 1 * 1

= 8

*/

#include<stdio.h>

/*

5

3 3

1 2 4 3 2

1 3 5 4 4

2 3 6 5 1

3 1 4 1 3

2 3 3 5 3

*/

int N;

int GARO, SERO;

int map[102][102];

int chk[102][102];

typedef struct {

int posY;

int posX;

} _pos;

_pos POSITION[1000000];

void main()

{

int i, j;

scanf("%d", &N);

scanf("%d %d", &SERO, &GARO);

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

{

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

{

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

}

}

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

{

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

{

chk[i][j] = 0x7fffffff;

}

}

int head = 0, tail = 0;

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

{

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

{

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

{

POSITION[tail].posY = i;

POSITION[tail].posX = j;

tail++;

}

}

}

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

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

int temp;

while (1)

{

if (head == tail) break;

for (int dir = 0; dir < 4; dir++)

{

int tmpY = POSITION[head].posY + Dy[dir];

int tmpX = POSITION[head].posX + Dx[dir];

if (tmpY >= 1 && tmpX >= 1 && tmpY <= N && tmpX <= N)

{

temp = map[POSITION[head].posY][POSITION[head].posX] - map[tmpY][tmpX];

if (temp < 0) temp = temp * temp;

temp += chk[POSITION[head].posY][POSITION[head].posX];

if (chk[tmpY][tmpX] > temp)

{

chk[tmpY][tmpX] = temp;

POSITION[tail].posY = tmpY;

POSITION[tail].posX = tmpX;

tail++;

}

}

}

head++;

}

printf("%d", chk[SERO][GARO]);

}

#include<stdio.h>

/*

덧셈을 못하는 철수를 공부시키기 위해 자연수들을 주고, 그 중에 몇 개의 수를 골라서 그 합이 K가 될 수 있는지 알아보라고 시켰다.

철수 어머니가 자연수들을 무작위로 선택해서 본인도 가능한지 아닌지 모르고 있다. 어머니가 채점을 할 수 있게 주어진 문제의 답을 찾아주자.

번째 줄에 테스트 케이스 개수 T(1≤T≤10)가 주어진다.

두 번째 줄부터 아래 내용이 T개 만큼 주어진다.

첫 줄에 자연수 개수 N(5 <= N <= 20)과 K(1 <= K <= 2,000,000)가 공백으로 구분되어 입력된다.

다음 줄에 N개의 자연수 di(1 <= di <= 100,000)가 공백으로 구분되어 입력된다.

T줄에 걸쳐 각 테스트 케이스 별로 주어진 자연수 중 몇 개의 합이 K가 되면 “YES”를 아니면 “NO”를 출력한다.

입력 예시

2

5 19

1 2 4 7 10

5 25

1 2 4 7 10

출력 예시

YES

*/

#include<stdio.h>

int T;

int N;

int CNT;

int GOAL;

int num[100001];

int dfs(int pos, int cost)

{

if (cost > GOAL) return 0;

if (cost == GOAL) return 1;

for (int i = pos; i < N; i++) // 다중트리

{

if (dfs(i + 1, cost + num[i]) == 1) return 1;

}

return 0;

}

int dfs(int pos, int cost)

{

if (pos > cntN)  return 0;

if (cost > GOAL) return 0;

if (cost == GOAL) return 1;

if (dfs(pos + 1, cost + arr[pos]) == 1) return 1; // 이진트리

if ( dfs(pos + 1, cost )==1) return 1;

}

void main()

{

scanf("%d", &T);

while (T--)

{

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

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

{

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

}

printf("%s\n", dfs(0, 0) == 1 ? "YES" : "NO");

}

}

#include<stdio.h>

typedef struct {

int sero;

int garo;

int idx;

int stat;

} _zergling;

하나로 모두 묶을 수 없기 때문에, 두가지를 동시에 사용해야 한다.

Zergling(가로,세로,idx)과 map(stat) 두개를 사용해서 처리

_zergling map[100][100];

_zergling Zergling[1000000];

int maps[100][100];

int cnt_time;

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

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

void main()

{

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

int garo; int sero;

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

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

{

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

{

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

maps[i][j] = map[i][j].stat;

if (map[i][j].stat == 1)

{

map[i][j].garo = j;

map[i][j].sero = i;

}

}

}

int zerg_garo = 0; 

int zerg_sero = 0;

scanf("%d %d", &zerg_garo, &zerg_sero);

int head = 0; int tail = 0;

map[zerg_sero - 1][zerg_garo - 1].stat = 0;

Zergling[tail].idx = 3;

Zergling[tail].garo = zerg_garo - 1;

Zergling[tail].sero = zerg_sero - 1;

cnt_time = map[zerg_sero - 1][zerg_garo - 1].idx;

tail++;

int a = 0;

while (1)

{

if (head == tail) break;

for (int dir = 0; dir < 4; dir++)

{

int garo_t = Zergling[head].garo + Dx[dir];

int sero_t = Zergling[head].sero + Dy[dir];

if (map[sero_t][garo_t].stat == 1)

{

a++;

map[sero_t][garo_t].stat = 0;

Zergling[tail].idx = Zergling[head].idx + 1;

Zergling[tail].garo = garo_t; // myqueue.push 의 다른 표현?

Zergling[tail].sero = sero_t;

cnt_time = (cnt_time > Zergling[tail].idx) ? cnt_time : Zergling[tail].idx;

tail++;

}

}

head++;

}

int cnt_num = 0;

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

{

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

{

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

if (map[i][j].stat == 1)

{

cnt_num++;

}

}

}

printf("%d\n%d", Zergling[head - 1].idx, cnt_num);

}