[BAEKJOON] 1816, 1834, 1855, 1303, 1747, 21608

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

 

[bronze1, 1816 암호키] 구현 + 소수

visual studio에서 S를 1번입력 받고 출력한 뒤 종료되는 비정상적인 작동을 하였으나, 제출 시에는 문제가없었다.
소수 배열 선언 시, 크기를 MAX로 지정하고, MAX를 포함한 범위까지 루프를 돌렸기에 문제가 발생했다.
 
visual studio에서 비정상적인 작동을 하는 이유가,
prime_number[MAX]배열이 메모리에 잡힌 후, N이 메모리에 추가되었기 때문에
N의 메모리 주소가 prime_number[MAX+1]메모리 주소로 착각되어, N=ture가 대입되고 루프가 1번으로 마무리된 것이라 한다
 
그렇다고 N을 먼저 선언하고 prime_number[MAX]로 할때나, N을 입력받지 않고 makePrimeNumber()를 하는 과정에서
visual studio에서는 어떠한 오류 알림도 내보내진 않아서 찜찜하다.

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

using namespace std;

#define MAX 1000000
#define ll long long

int N;
bool prime_number[MAX + 1];
vector <int> prime_n;

void makePrimeNumber() {
	prime_number[1] = true;
	prime_number[0] = true;
	for (int i = 2; i <= MAX; i++) {
		if (prime_number[i]) continue;
		prime_n.push_back(i);
		for (int j = i + i; j <= MAX; j += i)
			prime_number[j] = true;
	}
}

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

	ll S;
	for(int n=0;n<N;n++) {
		scanf("%lld", &S);
		bool flag = false;
		for (ll i = 0; i < prime_n.size(); i++) {
			if (S % prime_n[i] == 0) {
				flag = true;
				break;
			}
		}
		flag ? printf("NO\n") : printf("YES\n");
	}
}

 

[bronze1, 1834 나머지와 몫이 같은 수] - 구현

나머지와 몫이 같은 경우는 주어진 N보다 작은 수만 가능하다는 것을 생각하자

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

using namespace std;

int N;
int main() {
	scanf("%d", &N);
	long long answer = 0;
	for (long long i = 1; i < N; i++) {
		answer += i * N + i;
	}
	printf("%lld", answer);
}

 

[bronze1, 1855 암호] - 구현

문자열의 길이와 열을 기준으로 나누어 떨어질 땐 정방향, 나누어 떨어지지 않을 땐 역방향으로 열의 인덱스를 조정하면 된다

새롭게 만든 문자열 테이블에서 초기화되지 않은 값에 유의하라

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

using namespace std;

int K;
string str;
char decrpyt[201][21];
int main() {
	scanf("%d", &K);
	cin >> str;
	for (int i = 0; i < str.length(); i++) {
		int div = i / K;
		int mod = i % K;
		if (div % 2 == 0) {
			decrpyt[div][mod] = str[i];
		}
		else {
			decrpyt[div][K - mod - 1] = str[i];
		}
	}
	int len = str.length() / K;
	if (str.length() % K != 0) len++;
	for (int j = 0; j < K; j++) {
		for (int i = 0; i < str.length() / K; i++) {
			if ('a' > decrpyt[i][j] || 'z' < decrpyt[i][j]) continue;
			printf("%c", decrpyt[i][j]);
		}
	}
}

 

 

[sliver1, 1303 전쟁 - 전투] - 너비우선탐색(BFS)

간단한 BFS문제이다. 가로가 N이고 세로가 M임에 주의하라

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

using namespace std;

int N, M;
char war[101][101];
bool visit[101][101];

struct Data {
	int y, x;
};
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };

bool range(int y, int x) {
	return y<0 || x<0 || y>N - 1 || x>M - 1;
}
int main() {
	scanf("%d %d", &M, &N);
	for (int n = 0; n < N; n++) {
		scanf("%s", &war[n]);
	}

	queue <Data> q;
	int white = 0, blue = 0;
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < M; x++) {
			if (!visit[y][x]) {
				int cnt = 1;
				visit[y][x] = true;
				q.push({ y, x });
				while (!q.empty()) {
					Data next = q.front(); q.pop();
					for (int d = 0; d < 4; d++) {
						int ny = next.y + dy[d];
						int nx = next.x + dx[d];
						if (!range(ny, nx) && !visit[ny][nx] && war[ny][nx] == war[y][x]) {
							visit[ny][nx] = true;
							q.push({ ny, nx });
							cnt++;
						}
					}
				}
				if (war[y][x] == 'W') white += cnt * cnt;
				else blue += cnt * cnt;
			}
		}
	}
	printf("%d %d", white, blue);
}

 

[sliver1, 1747 소수&팰린드롬] - 구현 + 소수

최대 입력인 1,000,000이 입력됐을 때, 이보다 큰 소수이면서 팰린드롬인 수를 찾아야하므로
최대 배열의 크기를 1,000,000보다 큰 크기로 지정해주어야 함에 유의한다

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

using namespace std;

int N;

#define MAX 2000001
bool prime_number[MAX];
vector <int> palindrome_number;

bool check_palindrome(string str) {
	int len = str.length();
	if (len == 2 && str[0] != str[1]) return false;
	for (int i = 0; i < len / 2; i++) {
		if (str[i] != str[len - i - 1]) return false;
	}
	return true;
}
void makePrimeNumber() {
	prime_number[0] = true;
	prime_number[1] = true;
	for (int i = 2; i <= MAX; i++) {
		if (prime_number[i]) continue;
		if (check_palindrome(to_string(i))) palindrome_number.push_back(i);
		for (int j = i + i; j <= MAX; j += i) {
			prime_number[j] = true;
		}
	}
}

int main() {
	scanf("%d", &N);
	makePrimeNumber();
	for (int i = 0; i < palindrome_number.size(); i++) {
		if (N <= palindrome_number[i]) {
			printf("%d", palindrome_number[i]);
			break;
		}
	}
}

 

[gold5, 21608 상어 초등학교] - 구현

1. 빈칸 중, 좋아하는 학생이 가장 많이 인접한 칸을 선택한다
2. 1을 만족하는 칸이 여러개일 때, 인접한 칸중 빈칸이 많이 인접한 칸을 선택한다
3. 2를 만족하는 칸이 여러개일 때, 행의 번호가 가장 작은 칸으로, 다음으로 열의 번호가 가장 작은 칸으로 선택한다

주어진 조건만 잘 따라간다면 쉽게 해결할 수 있다.

이해하기 쉽게 1, 2, 3에 해당하는 정렬을 각각 구현해 매번 정렬하는 하드코딩을 했지만

1), 2), 3)을 기준으로 한번에 정렬해서 문제를 풀어나가는 것을 권장한다

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

using namespace std;

int N;
int board[401][401];
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0,-1,1 };

bool range(int y, int x) {
	return y<0 || x<0 || y>N - 1 || x>N - 1;
}

struct Data {
	// l= like, b= blank, r= row, c= cloumn
	int l, b, r, c;
};
bool likeCompare(Data a, Data b) {
	return a.l > b.l;
}
bool blankCompare(Data a, Data b) {
	return a.b > b.b;
}
bool coordCompare(Data a, Data b) {
	if (a.r == b.r)
		return a.c < b.c;
	return a.r < b.r;
}
int main() {
	scanf("%d", &N);
	int student[401][4] = { 0, };
	for (int t = 0; t < N * N; t++) {
		int n;
		scanf("%d", &n);
		for (int i = 0; i < 4; i++) {
			scanf("%d", &student[n][i]);
		}

		vector <Data> seat;
		for (int y = 0; y < N; y++) {
			for (int x = 0; x < N; x++) {
				if (board[y][x]) continue;
				int like = 0, blank = 0;
				for (int d = 0; d < 4; d++) {
					int ny = y + dy[d];
					int nx = x + dx[d];
					if (!range(ny, nx)) {
						if (!board[ny][nx]) blank++;
						else {
							for (int s = 0; s < 4; s++) {
								if (student[n][s] == board[ny][nx]) like++;
							}
						}
					}
				}
				seat.push_back({ like, blank, y, x });
			}
		}
		if (seat.size() == 1) {
			board[seat[0].r][seat[0].c] = n;
		}
		else {
			sort(seat.begin(), seat.end(), likeCompare);
			if (seat[0].l != seat[1].l) {
				board[seat[0].r][seat[0].c] = n;
			}
			else {
				int l = seat[0].l;
				vector <Data> like;
				for (int i = 0; i < seat.size(); i++) {
					if (seat[i].l == l) like.push_back(seat[i]);
				}
				sort(like.begin(), like.end(), blankCompare);
				if (like[0].b != like[1].b) {
					board[like[0].r][like[0].c] = n;
				}
				else {
					int b = like[0].b;
					vector <Data> blank;
					for (int i = 0; i < like.size(); i++) {
						if (like[i].b == b) blank.push_back(like[i]);
					}
					sort(blank.begin(), blank.end(), coordCompare);
					board[blank[0].r][blank[0].c] = n;
				}
			}
		}
	}

	int answer = 0;
	int like[3][3] = { 0, };
	for (int y = 0; y < N; y++) {
		for (int x = 0; x < N; x++) {
			int cnt = 0;
			for (int d = 0; d < 4; d++) {
				int ny = y + dy[d];
				int nx = x + dx[d];
				if (!range(ny, nx)) {
					for (int s = 0; s < 4; s++) {
						if (student[board[y][x]][s] == board[ny][nx]) cnt++;
					}
				}
			}
			like[y][x] = cnt;
			answer += cnt == 0 ? 0 : pow(10, cnt - 1);
		}
	}
	printf("%d", answer);
}