[BAEKJOON] 1236, 1259, 1268, 1080, 1124, 2493

※ 소스코드는 각 문제 설명 하단에 <더보기>를 통해 확인하실 수 있습니다.

 

[bronze1, 1236 성 지키기] - 구현

가로 세로 경비원이 겹치지 않은 좌표의 개수를 세면 된다 생각했지만, 예제 1번과 3번에서 가로/세로 특정 줄에 X가 하나도 없는 경우에 의해, 조금 더 생각이 필요했다 
그래서 가로와 세로에 경비원이 존재하는지 판단하는 배열을 두고 교차지점에 경비원이 존재하는지 판단하여 없는 경우 추가하며 a-z를 확인했고, 이후 가로와 세로줄에 경비원이 존재하는지 판단하여 두 경우의 합을 구해주면 됐다

#include <iostream>
#include <algorithm>
#pragma warning(disable:4996)

using namespace std;

int N, M;
char map[51][51];
bool r[51];
bool c[51];
int main() {
	scanf("%d %d", &N, &M);

	int x_cnt = 0;
	for (int i = 0; i < N; i++) {
		scanf("%s", &map[i]);
		for (int j = 0; j < M; j++) {
			if (map[i][j] == 'X') {
				x_cnt++;
				r[i] = true;
				c[j] = true;
			}
		}
	}
	if (!x_cnt) {
		printf("%d", max(N, M));
		return 0;
	}

	int answer = 0;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {
			if (!r[i] && !c[j]) {
				answer++;
				r[i] = true;
				c[j] = true;
			}
		}
	}

	for (int i = 0; i < N; i++) if (!r[i]) answer++;
	for (int j = 0; j < M; j++) if (!c[j]) answer++;

	printf("%d", answer);
}

 

[bronze1, 1259 팰린드롬수] - 문자열

왜 temp[0] == '0' 구문에서 Time check failure stack around the variabale was corrupted 에러가 표출되는지 해결하진 못했다

#include <iostream>
#pragma warning(disable:4996)

using namespace std;

int mstrlen(char str[]) {
	int cnt = 0;
	while (*str++ != '\0') {
		cnt++;
	}
	return cnt;
}

int main() {
	char temp[5];
	while (true) {
		scanf("%s", &temp);
		if (temp[0] == '0') break;

		bool flag = false;
		int len = mstrlen(temp);
		for (int i = 0; i < len / 2; i++) {
			if (temp[i] != temp[len - i - 1]) {
				flag = true;
				break;
			}
		}
		flag ? printf("no\n") : printf("yes\n");
	}
}

[bronze1, 1268 임시 반장 정하기] - 구현

N학년에 대해, 각 학생이 다른 학생과 같은 반이 된 적이 있는지 체크하고, 다시 모든학생을 검사해 가장 많은 친구를 가진 학생을 선별하면 되는 간단한 문제였으나, 문제를 꼬아서 생각하여 우선순위 큐를 사용해야 된다 생각했고 시간초과를 겪었다
모두가 같은반이 된 경우의 수가 1개도 없을 땐, 가장 작은 학생의 번호인 1이 출력됨에 유의하고 풀어나가야 한다

#include <iostream>
#pragma warning(disable:4996)

using namespace std;

int N;
int student[1001][5];
bool visit[1001][1001];
int main() {
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < 5; j++) {
			scanf("%d", &student[i][j]);
		}
	}

	for (int k = 0; k < 5; k++) {
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				if (i != j && student[i][k] == student[j][k]) {
					visit[i][j] = visit[j][i] = true;
				}
			}
		}
	}

	int idx = -1;
	int answer = -1;
	for (int i = 0; i < N; i++) {
		int cnt = 0;
		for (int j = 0; j < N; j++) {
			if (visit[i][j]) cnt++;
		}
		if (answer <= cnt) {
			if (answer != cnt) idx = i + 1;
			answer = cnt;
		}
	}

	printf("%d", idx);
}

[sliver1, 1080 행렬] - 그리디 + 최적해

a-z까지 모든 구간에 대해, A와B가 동일하지 않은 좌표에서 3x3배열을 반전시키며 진행한다

3x3배열을 뒤집을 수 없는 구간이 포함되는 경우 그 구간에 대해 검증을 하며 풀어갔지만, 모든 구간에 대해 진행해도 뒤집을 수 없는 구간은 변하지 않기 때문에 마지막에 A와 B가 동일한지 한번만 검증해 주어도 된다

※ 그리디+최적해에 대한 참고: https://www.acmicpc.net/board/view/76546

#include <iostream>
#pragma warning(disable:4996)

using namespace std;

int N, M;
char A[51][51], B[51][51];
bool diff[51][51];

void reverse_diff(int r, int c);
bool check_diff();

int main() {
	scanf("%d %d\n", &N, &M);

	for (int i = 0; i < N; i++)
		scanf("%s", &A[i]);

	for (int i = 0; i < N; i++)
		scanf("%s", &B[i]);
	
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			diff[i][j] = A[i][j] == B[i][j] ? true : false;


	if (N < 3 || M < 3) {
		bool same = false;
		for (int i = 0; i < N; i++)
			for (int j = 0; j < M; j++)
				if (!diff[i][j]) {
					printf("-1");
					return 0;
				}
		printf("0");
		return 0;
	}

	
	int answer = 0;
	for (int i = 0; i < N - 2; i++)
		for (int j = 0; j < M - 2; j++)
			if (!diff[i][j]) {
				reverse_diff(i, j);
				answer++;
			}

	check_diff() ? printf("%d", answer) : printf("-1");
}


void reverse_diff(int r, int c) {
	for (int i = r; i < r + 3; i++)
		for (int j = c; j < c + 3; j++)
			diff[i][j] = !diff[i][j];
}

bool check_diff() {
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			if (!diff[i][j]) return false;
	return true;
}

[sliver1, 1124 언더프라임] - 소수

모든 구간에서 값이 소수인 경우를 배제하지 않는 경우에 시간초과가 발생하는 것에 주의해야 한다

#include <iostream>
#include <vector>
#pragma warning(disable:4996)

using namespace std;

bool prime_number[100001];
vector<int>prime_list;
void set_prime_number() {
	prime_number[0] = true;
	prime_number[1] = true;
	for (int i = 2; i < 100001; i++) {
		prime_list.push_back(i);
		for (int j = i + i; j < 100001; j += i) {
			if (!prime_number[j]) prime_number[j] = true;
		}
	}
}

int A, B;
int main() {
	scanf("%d %d", &A, &B);

	set_prime_number();

	int answer = 0;
	for (int i = A; i <= B; i++) {
		if (!prime_number[i]) continue;
		int n = i;
		int cnt = 0;
		for (int p = 0; p < prime_list.size(); p++) {
			if (n == 1) break;
			while (n % prime_list[p] == 0) {
				n = n / prime_list[p];
				cnt++;
			}
		}
		if (!prime_number[cnt]) answer++;
	}
	printf("%d", answer);
}

[gold5, 2493 탑] - 스택

문제는 자신의 왼쪽방향에 있는 탑에 신호를 보내며, 탑의 높이가 자신보다 높은 경우에
자신이 보낸 신호를 수신할 수 있다는 것을 파악하는게 중요하다
그렇기에 앞선 높은 탑의 정보와 자신의 정보를 차곡차곡 저장하고, 비교해 나갈 수 있는 스택을 사용하였다

#include <iostream>
#include <stack>
#pragma warning(disable:4996)

using namespace std;

int N, t;
int main() {
	scanf("%d", &N);

	stack <pair<int, int>> tower;

	for (int i = 1; i <= N; i++) {
		scanf("%d", &t);
		if (tower.empty()) {
			tower.push({i, t});
			printf("0 ");
		}
		else {
			if (tower.top().second < t) {
				while (!tower.empty() && tower.top().second < t) {
					tower.pop();
				}
				tower.empty() ? printf("0 ") : printf("%d ", tower.top().first);
				tower.push({ i, t });
			}
			else {
				printf("%d ", tower.top().first);
				tower.push({ i, t });
			}
		}
	}
}