이것 저것 &

문제링크:https://www.acmicpc.net/problem/5549

전형적인 구현문제입니다.

• 1. 사각형을 기준으로 포함되는 정글, 바다, 얼음 값들을 저장합니다.
• 2. 사각형기준으로 jungle = pos[c][d][0] - pos[a - 1][d][0] - pos[c][b - 1][0] + pos[a - 1][b - 1][0] 을 통해 해당 위치의 개수를 구합니다.

정답 코드입니다. 시간초과를 주의하기 위해 '\n' 를 사용해야합니다.

#include <iostream>
#include <string>
using namespace std;
int m = 0, n = 0, k = 0;
int a, b, c, d;
char arr[1001][1001];
int pos[1001][1001][3] = { 0 }; // J O I순
string temp;
int main() {
	cin >> m >> n >> k;
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	for (int i = 1; i <= m; i++) {
		cin >> temp;
		for (int j = 1; j <= n; j++)
			arr[i][j] = temp[j - 1];
	}

	//테두리를 미리 표시 
	for (int i = 1; i <= n; i++) {
		if (arr[1][i] == 'J') pos[1][i][0] = 1;
		else if (arr[1][i] == 'O') pos[1][i][1] = 1;
		else if (arr[1][i] == 'I') pos[1][i][2] = 1;

		pos[1][i][0] += pos[1][i - 1][0];
		pos[1][i][1] += pos[1][i - 1][1];
		pos[1][i][2] += pos[1][i - 1][2];
	}

	for (int i = 1; i <= m; i++) {
		if (arr[i][1] == 'J') pos[i][1][0] = 1;
		else if (arr[i][1] == 'O') pos[i][1][1] = 1;
		else if (arr[i][1] == 'I') pos[i][1][2] = 1;

		pos[i][1][0] += pos[i - 1][1][0];
		pos[i][1][1] += pos[i - 1][1][1];
		pos[i][1][2] += pos[i - 1][1][2];
	}
	
	for (int i = 2; i <= m ; i++) {
		for (int j = 2; j <= n ; j++) {
			pos[i][j][0] = pos[i - 1][j][0] + pos[i][j - 1][0] - pos[i - 1][j - 1][0];
			pos[i][j][1] = pos[i - 1][j][1] + pos[i][j - 1][1] - pos[i - 1][j - 1][1];
			pos[i][j][2] = pos[i - 1][j][2] + pos[i][j - 1][2] - pos[i - 1][j - 1][2];

			if (arr[i][j] == 'J') pos[i][j][0] += 1;
			else if (arr[i][j] == 'O') pos[i][j][1] += 1;
			else if (arr[i][j] == 'I') pos[i][j][2] += 1;
		}
	}


	// 
	for (int i = 0; i < k; i++) { 
		cin >> a >> b >> c >> d;
		int jungle = pos[c][d][0] - pos[a - 1][d][0] - pos[c][b - 1][0] + pos[a - 1][b - 1][0];
		int ocean  = pos[c][d][1] - pos[a - 1][d][1] - pos[c][b - 1][1] + pos[a - 1][b - 1][1];
		int ice    = pos[c][d][2] - pos[a - 1][d][2] - pos[c][b - 1][2] + pos[a - 1][b - 1][2];
		cout << jungle << ' ' << ocean << ' ' << ice << '\n';
	}

}

문제링크:https://www.acmicpc.net/problem/1043

구현문제입니다. 문제를 꼼꼼하게 읽는 습관을 길러야 할 것같습니다.

문제 조건중  어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 라는 조건에 주목해야합니다.

6 5

1 6

2 4 5

2 1 2

2 2 3

2 3 4

2 5 6

와 같은 테스트 케이스에서 답은 0 입니다. 

과장된 이야기를 먼저 들은 사람이 나중에 진짜 이야기를 들어도 거짓말쟁이인게 들통납니다. 

즉 순서가 상관이 없는 문제입니다. 

알고리즘 입니다. 

1. 만약 진실을 알고 있는 사람이 있다면 해당 파티에서 거짓말을 못합니다.

2. 진실을 알고있는 사람과 함께 파티에 참여한 사람들이 있다면, 해당 사람들이 진실을 알고있다고 표시합니다.

3.  2번 조건이 부합하면 다시 처음 파티부터 확인합니다. 

	#include <iostream>
	using namespace std;
	int n = 0, m = 0, result = 0;
	int num = 0, temp = 0;
	bool knowlege[51] = { 0 };
	bool val[50] = { 0 };
	int arr[50][51] = { 0 };
	int arr_index[50] = { 0 };
	int main() {
		cin >> n >> m; //사람의 수와 파티의 수
	
		cin >> num;
		for (int i = 0; i < num; i++) {
			cin >> temp;
			knowlege[temp] = 1;
		}

		for (int i = 0; i < m; i++) {
			cin >> num;
			arr_index[i] = num;
			for (int j = 0; j < num; j++)
				cin >> arr[i][j];
		}
	
		for (int i = 0; i < m; i++) {

			for (int j = 0; j < arr_index[i]; j++) {
				int v = arr[i][j];

				if (knowlege[v] == 1) {
					val[i] = 1; // 이파티에서 거짓말을 못해 
					bool jud2 = true;
					for (int k = 0; k < arr_index[i]; k++)
						if (knowlege[arr[i][k]] == 0 && j != k)
							jud2 = false, knowlege[arr[i][k]] = 1;

					if (jud2 == false) {
						i = -1;
						break;
					}

				}
			}

		}
	
		for (int i = 0; i < m; i++)
			if (val[i] == 0) result++; 


	
		cout << result << endl;
	}

구현 난이도 자체는 매우 낮은 문제지만 구현을 어떻게 할지 조금 생각해보아야 하는 문제였습니다. 

문제링크:https://www.acmicpc.net/problem/2140

전형적인 구현문제입니다. 

모서리의 숫자들이 주어질 때 해당 지뢰의 최대갯수를 찾는 문제였습니다.

생각해보면 최대개수이기때문에 지뢰가 있을 수 없는 장소들만 찾아주면 됩니다.

저는 #위치를 탐색하면서  주변(8방향)에 0이 포함되어있으면 해당 #은 지뢰가 없다고 표시해주는 방법으로 해결하였습니다. 

그리고 0이 없다면 해당 위치는 지뢰가 있는것이고 주변(8방향)값들은 값을 1씩 낮춰줌으로써 구현하였습니다.

#include <iostream>
#include <string>
using namespace std;
int n = 0, result = 0;
string arr[101];
int y_ar[8] = {-1,-1,0,1,1,1,0,-1};
int x_ar[8] = {0,1,1,1,0,-1,-1,-1};


// 규칙을 보다보면 8방향에 0이 있는 경우에만 폭탄이 없고 나머지는 폭탄이 있다고 가정
int main() {
	cin >> n;

	for (int i = 0; i < n; i++)
		cin >> arr[i];

	for (int i = 1; i < n - 1; i++)
		for (int j = 1; j < n - 1; j++) {
			bool jud = true;
			for (int u = 0; u < 8; u++) {
				int y = i + y_ar[u];
				int x = j + x_ar[u];
				
				if (arr[y][x] == '0') {
					arr[i][j] = ' ';
					jud = false;
				}
			}
			if (jud == true) {
				for (int u = 0; u < 8; u++) {
					int y = i + y_ar[u];
					int x = j + x_ar[u];

					if ('0' < arr[y][x] &&  arr[y][x] <= '3') {
						arr[y][x] -= 1;
					}
				}
			}

		}
			
	for (int i = 1; i < n - 1; i++)
		for (int j = 1; j < n - 1; j++)
			if (arr[i][j] == '#') result++;
	
	cout << result << endl;

	return 0;
}

문제링크:https://www.acmicpc.net/problem/6416

1. 들어오는 간선이 하나도 없는 단 하나의 노드가 존재한다. 이를 루트(root) 노드라고 부른다.
2. 루트 노드를 제외한 모든 노드는 반드시 단 하나의 들어오는 간선이 존재한다.
3. 루트에서 다른 노드로 가는 경로는 반드시 가능하며, 유일하다. 이는 루트를 제외한 모든 노드에 성립해야 한다.

3가지조건을 만족해야합니다.

그리고 수의 범위가 주어지지 않았기 때문에 배열의 크기를 정해놓는 것은 안됩니다.

위의 조건들에 대해서 곰곰히 생각하다 보면 집합에 대해서 생각하실 수 있습니다. 

위 조건들을 만족시키위해서 노드 집합의 개수 s + 1 과  입력받은 횟수가 같아야 한다는 것을 알 수있습니다. 

정답코드입니다.

#include <iostream>
#include <cstring>
#include <vector>
#include <set>
using namespace std;

int a, b;
int u = 0;
set <int> arr;

int main() {
	
	while (1) {
		u++;
		arr.clear();
		int sum = 0;
		bool jud2 = true;
		for (int k = 0;; k++) {
			
			cin >> a >> b;
			if (k == 0) {
				if (a == -1 && b == -1)
					return 0;
				else if (a == 0 && b == 0) {
					cout << "Case " << u << " is a tree." << '\n';
					jud2 = false;
					break;
				}
			}
			if (a == 0 && b == 0)
				break;
			arr.insert(a);
			arr.insert(b);
			sum++;

		}
		if (jud2 == true) {
			if (sum + 1 == arr.size())
				cout << "Case " << u << " is a tree." << '\n';
			else
				cout << "Case " << u << " is not a tree." << '\n';
		}
	}

	return 0;
}

문제링크:https://www.acmicpc.net/source/10245386

스택을 이용한 구현문제였습니다. 

예외처리때문에 애먹은 문제입니다.

우선 올바른 괄호열인지 구분하기 위해서 스택을 사용합니다.

스택을 사용하여 올바른 괄호열인지 구분하는 것은 쉽게 하실거라고 생각합니다. 

문제는 괄호의 점수계산입니다.

이러한 조건을 가지고 있습니다.

각각의 괄호안에 들어갈 때 값이 커집니다. 

2(2+(3x3)) +2(3) 입니다. 즉 2X2 + 2X3X3 + 2X3 =28 입니다.

• 문자열을 검사하며 '(' 라면 스택에 넣습니다. TEMP 값에 2를 곱합니다. 
• 문자열을 검사하며 '[' 라면 스택에 넣습니다. TEMP 값에 3을 곱합니다. 
• 문자열을 검사하며 ')' 라면 스택을 확인해 값을 연산이 되는 확인합니다.
• 연산이 된다면 값을 RESULT에 추가하고 스택을 POP하며 TEMP값도 나누기 2 합니다. 
• ']' 도 마찬가지의 방식입니다.

만약 스택에 값이 남아있다면 올바르게 괄호 검사 상태가 아니기 때문에 0을 출력합니다. 

정답코드입니다. 다양한 예외사항이 있었습니다. 

#include <iostream>
#include <deque>
#include <string>
using namespace std;

string input;
deque <char> arr;
int temp = 1;
int result = 0;
int main() {

	cin >> input;

	for (int i = 0; i < input.size(); i++) {
		if (input[i] == '(') {
			arr.push_back('(');
			temp *= 2;
		}
		else if (input[i] == '[') {
			arr.push_back('[');
			temp *= 3;
		}
		else if (input[i] == ')' && i>0) {
			if (input[i - 1] == '(') {
				arr.pop_back();
				result += temp;
				temp /= 2;			
			}
			
			else if (arr.empty() != 1){
				if (arr.back() == '(') {
					arr.pop_back();
					temp /= 2;
				}
			}
			else{
				cout << 0 << '\n';
				return 0;
			}

		}
		else if (input[i] == ']' && i > 0 ) {
			if (input[i - 1] == '[') {
				arr.pop_back();
				result += temp;
				temp /= 3;
			}
			else if (arr.empty() != 1) {
				if (arr.back() == '[') {
				arr.pop_back();
				temp /= 3;
				}
			}
			else {
				cout << 0 << '\n';
				return 0;
			}
		}

		
		
	}

	if(arr.empty()!= 1)
		cout << 0 << '\n';
	else
		cout << result << endl;
	return 0;
}

문제링크:https://www.acmicpc.net/problem/2194

bfs를 사용하는 문제였습니다.

하지만 기존 탐색과는 다르게 탐색하는 유닛의 크기가 1X1이 아닌 값이기 때문에 

이동하면서 숫자 넘어가는 숫자들의 범위나 이동할 수 있는지 여부를 반복문을 통해서 판별해야하기 때문에 구현문제로 분류하였습니다.

• 값 입력
• 상하좌우로 움직기
• 이동할때 모든 값이 배열을 벗어나는지 장애물이 있는지 확인하기
• 이동가능할 경우 visited에 표시하기
• 값 출력

정답코드입니다.

#include <iostream>
#include <queue>
using namespace std;
int arr[501][501] = { 0 };
int visited[501][501] = { 0 };
int n = 0, m = 0, a = 0, b = 0, k = 0;
int start_y, start_x, destination_y, destination_x;

int x_ar[4] = { 0,0,1,-1 };
int y_ar[4] = { 1,-1,0,0 };

void bfs() {
	queue<int> que[2];
	que[0].push(start_y);
	que[1].push(start_x);
	visited[start_y][start_x] = 1;
	while (!que[0].empty()) {
		int yy = que[0].front();
		int xx = que[1].front();
		que[0].pop(), que[1].pop();

		
		for (int k = 0; k < 4; k++) {
			bool jud = true;
			for (int i = 0; i < a; i++) {
				for (int j = 0; j < b; j++) {
					int y = i + yy + y_ar[k];
					int x = j + xx + x_ar[k];
					if (y >= 1 && y <= n&&x >= 1 && x <= m) {
						if (arr[y][x] == 1) {
							jud = false;
							break;
						}
					}
					else { //해당공간에서 벗어나니까 
						jud = false;
						break;
					}
				}
				if (jud == false)
					break;
			}
			if (jud == true && visited [yy+y_ar[k]][xx+x_ar[k]] == 0) {
				visited[yy + y_ar[k]][xx + x_ar[k]] = visited[yy][xx] + 1;
				que[0].push(yy + y_ar[k]);
				que[1].push(xx + x_ar[k]);
			}
		}
		
	}
}

int main() {
	cin >> n >> m >> a >> b >> k;
	int num_a = 0, num_b = 0;
	for (int i = 0; i < k; i++) {
		cin >> num_a >> num_b;
		arr[num_a][num_b] = 1;
	}
	cin >> start_y >> start_x >> destination_y >> destination_x;

	bfs();

	cout << visited[destination_y][destination_x] - 1 << '\n';
}

문제링크:https://www.acmicpc.net/problem/1756

구현문제로 분류되지만 그리디 알고리즘이라고도 생각할 수 있는 문제였습니다.

흔하게 생각하는 방법으로 구현하게 되면 

O(n*d) 의 시간복잡도가 걸리는 이준 포문을 구현할 수 있습니다.

하지만 해당 방법은 시간초과입니다. 

n,d 둘다 300000까지이기 때문입니다. 

그렇기 때문에 nlgn, n, d 만큼 걸리는 방법을 고안해야합니다.

n입장에서볼때 d배열에서 자신보다 작은위치 아래로는 들어갈 수 없습니다. 

즉, n => 3 2 5일 때 3은 d의 제일 아래인 3으로 갈 수 없습니다. 

그렇다면  5 6 4 3 6 2 3를 5 5 4 3 3 2 2 로 나타낼 수 있습니다. 어차피 작은 위치아래로는 내려갈 수 없기 때문이죠.

이렇게 배열을 바꾼 후에는 d 배열의 끝부터 n을 삽입할 수 있는지 순서대로 확인해주시면 됩니다. 

구현자체는 쉽고, 구현방법을 생각하는게 어려운 문제였습니다. 

정답코드입니다. 꼭 직접 작성해보세요! 화이팅 : ) 

#include <iostream>
using namespace std;
int d = 0, n = 0, result = 0;
int arr_d[300000] = { 0 };
int arr_n[300000] = { 0 };
int visited[300000] = { 0 };
int main() {
	cin >> d >> n;

	for (int i = 0; i < d; i++) {
		cin >> arr_d[i];
		if (i > 0 && arr_d[i - 1] < arr_d[i]) arr_d[i] = arr_d[i - 1];
	}
	for (int i = 0; i < n; i++)
		cin >> arr_n[i];



	int cnt = 0;
	for (int i = d - 1; i >= 0; i--) {
		if (arr_n[cnt] <= arr_d[i]) {
			visited[cnt] = 1 + i;
			cnt++;
		}
		if (cnt == n)
			break;
	}

	if (cnt == n)
		cout << visited[cnt - 1] << endl;
	else
		cout << 0 << endl;

	return 0;
}

문제링크: https://www.acmicpc.net/problem/1188

소시지를 하나로 이어붙인 상태 즉, n = 1일때 m - 1번 잘라야 모두에게 같은 크기의 소시지를 줄 수 있다.

즉, 최악의 경우 m - 1 최소의 경우 0번이다. 

그렇다면 소시지가 여러개가 있을 때 어떻게 해야할까?

최대공약수를 생각해보면 답이 나온다. 

소시지를 일자로 두고 일정한 크기 만큼 자를 때 두 수의 (최대 공약수 - 1)  만큼 이미 잘려있을 것이다. 

즉 식은 b - gcd(a,b) 이다. 

#include <iostream>
using namespace std;

int n = 0, m = 0;
int GCD(int a, int b) {
	if (a%b == 0)
		return b;

	return GCD(b, a%b);
}

int main() {
	cin >> n >> m;

	cout << m - GCD(n, m) << endl;
}

최대 공약수를 구하는 재귀는 위와 같이 구현할 수 있다.