[BAEKJOON] 1068, 2023, 20055

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

 

[gold5, 1068 트리] - 깊이우선탐색(DFS)

간단한 DFS문제이나, 백트래킹 방식으로 접근하면 예외를 쉽게 생각할 수 있다
1) 현재 노드가 삭제된 노드인 경우, 리프 노드 개수를 구할 수 없으므로 0 반환
2) 현재 노드에게 자식이 없는 경우, 자신이 리프 노드이므로 1 반환
3) 자식이 있음에도 리프 노드값이 반한되지 않은 경우, 삭제된 노드를 자식으로 가지고 있었으므로 자신이 리프 노드가 되어 1 반환

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

using namespace std;

int tree[51];
int child[51];
vector<int> parent[51];
int del_node;

int leefNode(int node) {
	int cnt = 0;
	if (node == del_node) 
		return 0;
	if (!parent[node].size()) 
		return 1;
	for (int i = 0; i < parent[node].size(); i++) {
		cnt += leefNode(parent[node][i]);
	}
	if (cnt == 0) cnt = 1;
	return cnt;
}

int main() {
	int N, node, root_node;
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &node);
		if (node == -1) root_node = i;
		else parent[node].push_back(i);
	}
	scanf("%d", &del_node);
	int answer = leefNode(root_node);
	printf("%d", answer);
}

 

[gold5, 2023 신기한 소수] - 백트래킹 + 소수

단순하게 1억개의 배열을 두고 소수를 판단하면 메모리초과를 만날 수 있으며,
메모리초과가 아니더라도, N자리의 수를 1~N자리의 모든 소수를 판단하는 과정에서 시간초과를 겪을 수 있다
  
왼쪽부터 첫 자리도 소수를 판단하므로, 첫 자리에 올 수 있는 수는 한자리 소수인 (2, 3, 5, 7)이 된다
여기에 수(0~9)를 붙여가며 소수인지 판단하고, 최대자리 수 까지 소수라면 그 수를 출력한다
  
수를 붙여간다는 의미는 N = 2,3,5,7일 때, N*10 + i(0~9)가 된다
여기서 짝수를 붙여나가는 경우, 무조건 2의 배수가 되어 소수일 수 없으므로 배제해야 한다

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

using namespace std;

int prime_number[4] = { 2,3,5,7 };

bool checkPrimeNumber(int n) {
	if (n < 10) return true;
	for (int i = 2; i < n; i++) {
		if (n % i == 0) return false;
	}
	return true;
}

void makePrimeNumber(int n, int len) {
	if (!checkPrimeNumber(n)) return;
	if (len == 0) {
		printf("%d\n", n);
		return;
	}
	for (int i = 1; i < 10; i += 2) {
		makePrimeNumber(n * 10 + i, len - 1);
	}
}

int main() {
	int N;
	scanf("%d", &N);
	for (int i = 0; i < 4; i++) {
		makePrimeNumber(prime_number[i], N - 1);
	}
}

 

[gold5, 20055 컨베이어 벨트 위의 로봇] - 구현 + 시뮬레이션

벨트 확인, 벨트 회전, 로봇 이동, 로봇 추가 네 단계로 구분하여 구현한다.

원형으로 돌아 다시 처음으로 돌아오므로, deque를 활용해 구현하는 것이 편하다.

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

using namespace std;

int N, K;
deque <int> belt;
deque <bool> robot;

int stage;
void spinStage() {
	belt.push_front(belt.back()); belt.pop_back();
	robot.push_front(robot.back()); robot.pop_back();

	if (robot[N - 1]) robot[N - 1] = false;
}
void moveRobot() {
	int robotSize = robot.size();
	for (int i = N - 2; i >= 0; i--) {
		if (robot[i] && !robot[i + 1] && belt[i + 1] > 0) {
			belt[i + 1] -= 1;
			robot[i] = false;
			if (i + 1 == N - 1) continue;
			robot[i + 1] = true;
		}
	}
}
void raiseRobot() {
	if (belt[0] > 0 && !robot[0]) {
		belt[0] -= 1;
		robot[0] = true;
	}
}
int checkBelt() {
	int cnt = 0;
	for (int i = 0; i < 2 * N; i++)
		if (belt[i] == 0) cnt++;
	return cnt;
}
int main() {
	scanf("%d %d", &N, &K);
	int durability;
	for (int i = 0; i < 2 * N; i++) {
		scanf("%d", &durability);
		belt.push_back(durability);
		robot.push_back(false);
	}
	while (true) {
		if (checkBelt() >= K) break;
		stage++;
		spinStage();
		moveRobot();
		raiseRobot();
	}
	printf("%d", stage);
}