2024-02-27

-자리배정(10157, 백준)

N범위가 1000임으로 그냥 구현하면 된다. 정말 힘든 구현문제라고 생각한다. x, y변수를 잡아주어, x, y를 증가, 감소시켜가며 사각형을 채운뒤 k번째 좌표값을 출력하였다. 자꾸 이상한데 수가 덮어져서 한참 디버깅했다. 미리 조건들을 써놓고 코딩하면 좋을듯 하다.

<소스코드>

#include <stdio.h>

int map[1010][1010];

int main()
{
	int i, j;
	int C, R, K;
	scanf("%d %d %d", &C, &R, &K);
	int cnt = 1;
	int x = 1, y = 1;
	int now_cnt = 0, now_dis = 1, dis = 1;
	if (C * R < K) {
		printf("0");
		return 0;
	}
	while (1) {
		if (K <= cnt) break;
		if (dis == 1) {
			map[x][y++] = cnt++;
			now_cnt++;
			if (now_cnt >= R - now_dis) {
				dis = 2;
				now_cnt = 0;
			}
		}
		else if (dis == 2) {
			map[x++][y] = cnt++;
			now_cnt++;
			if (now_cnt >= C - now_dis) {
				dis = 3;
				now_cnt = 0;
			}
		}
		else if (dis == 3) {
			map[x][y--] = cnt++;
			now_cnt++;
			if (now_cnt >= R - now_dis) {
				dis = 4;
				now_cnt = 0;
			}
		}
		else if (dis == 4) {
			map[x--][y] = cnt++;
			now_cnt++;
			if (now_cnt >= C - now_dis) {
				x++;
				y++;
				dis = 1;
				now_dis += 2;
				now_cnt = 0;
			}
		}
	}
	printf("%d %d", x, y);
	return 0;
}

-개미(10158, 백준)

 아이디어가 필요한 수학 문제였다. t의 범위가 무지막지하게 크기때문에, 완전탐색으로 구현 할 수 없다. x좌표와 y좌표를 나누어 각각 바라보면, 규칙이 나오게 된다. 공간이 한정되어있고, 벽면에 닿는다면 반사 되어 반대방향으로 나아감으로 결국 한정된 좌표안에서 놀게 되는데 생각해보면, 몇번 반사됬는지에 따라 경우가 두가지로 갈린다. 반사되어 x, y좌표가 각각 w, h에서 0, 0으로 가는 경우와 0, 0에서 w, h로 가는 경우이다. 이를 이용하면, 수학적 접근을 통해 O(1)만에 해결이 가능하다.

<소스코드>

#include <stdio.h>

long long w, h, x, y, t;

int main()
{
	scanf("%lld %lld %lld %lld %lld", &w, &h, &x, &y, &t);
	x += t;
	y += t;
	long long ans_x, ans_y;
	if (x <= w) ans_x = x;
	else {
		long long divi = x / w;
		if (divi % 2) ans_x = w - (x % w); //홀수
		else ans_x = x % w; //짝수
	}
	if (y <= w) ans_y = y;
	else {
		long long divi = y / h;
		if (divi % 2) ans_y = h - (y % h); //홀수
		else ans_y = y % h; //짝수
	}
	printf("%lld %lld", ans_x, ans_y);
	return 0;
}

-저울(10159, 백준)

 보자마자 그래프탐색이 떠올랐다. 자신과 비교가 불가능한 물건의 번호를 출력하는 문제이다. 즉, 노드가 연결되지않은 번호를 출력하면된다. 입력받으며, 정방향간선과 역방향간선을 각각 저장해주고, BFS를 이용해 두 간선을 한 노드를 기준으로 탐색 후, 해당노드와 연결되어있지않다고 판단되는 경우 cnt를 증가시키는 식으로 구현하였다.

<소스코드>

#include <stdio.h>
#include <queue>
#include <vector>

using namespace std;

int n, m;
vector<int> vec1[110], vec[110];
int ch[110], ch1[110];
int ans[110];

void BFS1(int x)
{
	queue <int> q;
	ch1[x] = 1;
	q.push(x);
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		for (int i = 0; i < vec1[now].size(); i++) {
			int nw = vec1[now][i];
			if (ch1[nw] == 0) {
				ch1[nw] = 1;
				q.push(nw);
			}
		}
	}
	return;
}

void BFS(int x)
{
	queue <int> q;
	ch[x] = 1;
	q.push(x);
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		for (int i = 0; i < vec[now].size(); i++) {
			int nw = vec[now][i];
			if (ch[nw] == 0) {
				ch[nw] = 1;
				q.push(nw);
			}
		}
	}
	return;
}

int main()
{
	int i, j;
	scanf("%d %d", &n, &m);
	for (i = 0; i < m; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		vec[x].push_back(y);
		vec1[y].push_back(x);
	}
	for (i = 1; i <= n; i++) {
		BFS(i);
		BFS1(i);
		int cnt = 0;
		for (j = 1; j <= n; j++) {
			if (ch[j] == 0 && ch1[j] == 0) cnt++;
		}
		ans[i] = cnt;
		for (j = 1; j <= n; j++) ch[j] = 0, ch1[j] = 0;
	}
	for (i = 1; i <= n; i++) printf("%d\n", ans[i]);
	return 0;
}

-암호(10160, 백준)

 처음에는 안전하지 않은 암호를 구하여 전체암호에서 빼주는 식으로 코딩을 했다. 하지만 경우가 너무 많고 어려워, 안전한 암호를 구하는 방향으로 생각했다. n범위도 크고, 값도 큼으로 대충 DP나 그리디문제라고 생각하고 접근을 하였고, 안전하지 않은 패턴인 ABCBC와 ABABC가 모두 5글자임으로, 5글자 전 값을 현재값에서 2번 뺀 값에서 ABABCBC가 두 배열을 공통으로 가지고 있기 때문에 포함과 배제를 이용하여, 7글자 전값을 더해주어 답을 구하였다. 1,000,000,009으로 나눈 나머지를 구하는 과정에서 음수가 나올 수 있기에 큰 수를 더한뒤 빼주는 식으로 처리하였다. 

<점화식>

Dp[i] = (Dp[i-1] * k) - (Dp[i-5] * 2) + Dp[i-7]

<소스코드>

#include <stdio.h>

int n, m;
long long dp[1000010];

int main()
{
	int i, j;
	scanf("%d %d", &n, &m);
	dp[0] = 1;
	for (i = 1; i <= n; i++) {
		dp[i] = (dp[i - 1] * m) % 1000000009;
		if (i >= 5) dp[i] = (2000000018 + dp[i] - (dp[i - 5] * 2)) % 1000000009;
		if (i >= 7) dp[i] = (dp[i] + dp[i - 7]) % 1000000009;
	}
	printf("%lld", dp[n] % 1000000009);
	return 0;
}

다시보니 너무 더러운것같다. 다음엔 define을 이용해야겠다...

 

-숨바꼭질 4(13913, 백준)

 숨바꼭질(백준, 1697)에서 경로 역추적을 하는 문제이다. DP를 이용하여 풀었다. Dp[i] = i까지 수빈이가 이동할때, 최소이동 횟수. 수빈이가 순간이동하는 경우와, 걷는경우 두가지경우중 더 작은 이동횟수를 지닌값을 구하였다. 경로배열에 어떤 idx값에서 왔는지 구해놓은 뒤, 백트래킹으로 경로를 찾아 출력해주었다.

<점화식>

짝수라면 -> dp[i] = min(dp[i / 2] + 1, min(dp[i], dp[i - 1] + 1));
홀수라면 -> dp[i] = min(dp[i], min(dp[i - 1] + 1, dp[(i + 1) / 2] + 2));

<소스코드>

#include <stdio.h>
#include <vector>

using namespace std;

int n, k;
int dp[100010];
int way[100010];
vector<int> ans;

void dfs(int x)
{
	ans.push_back(x);
	if (way[x] == x) return;
	else dfs(way[x]);
}

int main()
{
	int i, j;
	scanf("%d %d", &n, &k);
	dp[n] = 0;
	way[n] = n;
	for (i = n - 1; i >= 0; i--) {
		dp[i] = dp[i + 1] + 1;
		way[i] = i + 1;
	}
	for (i = n + 1; i <= k; i++) {
		dp[i] = dp[i - 1] + 1;
		way[i] = i - 1;
		if (i % 2 == 0) {
			if (dp[i] > dp[i / 2] + 1) {
				dp[i] = dp[i / 2] + 1;
				way[i] = i / 2;
			}
		}
		else {
			if (dp[i] > dp[(i + 1) / 2] + 2) {
				dp[i] = dp[(i + 1) / 2] + 2;
				way[i] = i + 1;
				way[i + 1] = (i + 1) / 2;
			}
		}
	}
	printf("%d\n", dp[k]);
	dfs(k);
	for (i = ans.size() - 1; i >= 0; i--) printf("%d ", ans[i]);
	return 0;
}