KOI 1996 초등부 문제 풀이

한국정보올림피아드(정올) 1996년도 초등부 문제 풀이 포스팅이다.

문제들은 백준저지에서 참고하고 풀이했다.

https://www.acmicpc.net/category/detail/403

1번 단지번호 붙이기 문제이다.

https://www.acmicpc.net/problem/2667 (백준 2667번)

dfs로 풀면 간단하게 풀 수 있는 문제이다.

 

#include <stdio.h>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

vector<vector<char> > matrix;
int N; //length of matrix edge
int num_of_danji;
int num_of_1;
int x,y;
vector<int> num_of_houses;
void dump_matrix();
bool find_danji();
bool spread(int xpos, int ypos);
bool comp(int a, int b) {
    return (a > b);
};
int main() {
	char temp;
	scanf("%d\n", &N);
	
	matrix.assign(N, vector<char>(N, '0'));
	for (int i=0; i<N; i++) {
		for (int j=0; j<N; j++) {
			scanf("%c", &temp);
			if (temp == '1') {
				num_of_1++;
			}
			matrix[i][j] = temp;
		}
		scanf("\n");
	}

	while (num_of_1 > 0) {
		// dump_matrix();
		find_danji();
		int temp = num_of_1;
		// cout << "x:" << x << endl << "y:" << y << endl;
		spread(x, y);
		num_of_danji++;
		num_of_houses.push_back(temp - num_of_1);
		// dump_matrix();
	}
	
	cout << num_of_danji << endl;
	sort(num_of_houses.begin(), num_of_houses.end());
	for (int i=0; i< num_of_houses.size(); i++) {
		cout << num_of_houses[i] << endl;;
	}
	
}

bool find_danji() {
	for (int i=0; i<N; i++) {
		for (int j=0;j<N; j++) {
			if (matrix[i][j] == '1') {
				x = i;
				y = j;
				return true;
			}
		}
	}
	x = -1;
	y = -1;
	return false;
}
bool spread(int xpos, int ypos) {
	// cout << "spread(" << xpos << "," << ypos << ")" << endl;
	if (xpos >= 0 && xpos < N && ypos >= 0 && ypos < N) {
		// cout << "flag 1"<< endl;
		if (matrix[xpos][ypos] == '1') {
			// cout << "flag 2"<< endl;
			matrix[xpos][ypos] = '0';
			num_of_1--;
			
			return spread(xpos-1, ypos) || spread(xpos, ypos-1) || spread(xpos+1, ypos) || spread(xpos, ypos+1);
		} else {
			return false;
		}
	} else {
		return false;
	}
}
void dump_matrix() {
	for(int i=0; i<N; i++) {
		for(int j=0; j<N; j++) {
			printf("%c", matrix[i][j]);
		}
		putchar('\n');
	}
}

2번 숫자고르기 문제이다.

https://www.acmicpc.net/problem/2668

다음 특징들에 착안해서 알고리즘을 고안했다.

위쪽의 그룹의 숫자는 중복이 없고 인덱스값과 같다.

아래쪽 그룹의 숫자는 중복이 있다. 따라서 없는 숫자도 있다.

위쪽 그룹 숫자를 U집합 이라고 하고 아래쪽 집합 숫자를 D집합이라고 하자.

아래쪽 그룹에 없는 숫자가 위쪽 그룹에서 지정될 수 없다는 점을 이용해서 다음 알고리즘을 고안했다.

1. 두번째 줄의 숫자 집합을 구한다. 이를 A라고 한다.

2. A의 원소를 인덱스(첫번째 줄의 숫자기준)로 하는 숫자 집합 B를 구한다.

3. A집합과 B집합이 일치하면 이(A집합 혹은 B집합)를 리턴한다. 그렇지 않으면 다음 단계로 간다.

4. B집합을 A집합으로 두고, B집합은 초기화한다. A집합을 기준으로 스텝 2를 다시 시도한 뒤 3번으로 간다.

백준에 나타난 예시에서 해당 알고리즘을 진행하면 다음과 같이 나타난다.

첫번째 스탭에서 집합 A는 다음과 같이 나타난다.

A = { 1, 3, 4, 5, 6 }

아래쪽 집합의 숫자들을 중복을 제거한 집합의 결과이다.

이때 이 A집합은 U집합에서 고른녀석들이라고 볼 수 있다.

알고리즘 두번째 스탭에서 집합 B를 구한다.

집합 B는 다음 항목들의 집합이다.

D[1], D[3], D[4], D[5], D[6]

B = { 3, 1, 5, 5, 6 } = { 1, 3, 5, 6 }

이때 이 B집합은 D집합에서 A집합에 대응되는 녀석이라고 볼 수 있다.

세번재 스탭에서 A와 B집합을 비교했을 때,  B집합이 크기가 더 작으므로 B집합을 A집합에 대입하고 다시 이어나간다.

A집합은 다시 다음값이 된다.(U집합에서 고른녀석들)

A = { 1, 3, 5, 6 }

B = { 3, 1, 5, 4 } = { 1, 3, 4, 5 }

다시 비교했을 때 맞지 않으므로 A집합에 다시 B 집합을 대응한다.

A = { 1, 3, 4, 5 }

B = { 3, 1, 5, 5 } = { 1, 3, 5 }

일치하지 않으므로 다시 대응한다.

A = { 1, 3, 5 }

B = { 1, 3, 5 }

일치하므로 정답을 리턴한다.

 

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

using namespace std;

vector<int> arr; //기본애들
vector<int> elite; //뽑힌애들
set<int> set1, set2;
int N;

void arr_dump();
void set_dump(set<int> a);
bool is_equal(set<int>, set<int>);
int main() {
	
	int temp;
	scanf("%d\n", &N);
	arr.reserve(N+1);
	arr.push_back(0000);
	for (int i=0; i<N; i++) {
		scanf("%d\n", &temp);
		arr.push_back(temp);
	}
	
	// arr_dump();
	for(int i=1; i< arr.size(); i++) {
		set1.insert(arr[i]);
	}
	// cout << "set1 : ";
	// set_dump(set1);
	for (set<int>::iterator pos = set1.begin(); pos != set1.end(); pos++) {
		set2.insert(arr[*pos]);
	}
	// cout << "set2 : ";
	// set_dump(set2);
	// cout << "is_equal " << is_equal(set1, set2) << endl;
	

	do {
		set1 = set2;
		set2.clear();
		for (set<int>::iterator pos = set1.begin(); pos != set1.end(); pos++) {
			set2.insert(arr[*pos]);
		}
		
	} while(!is_equal(set1, set2));
	// cout << "fin";
	// set_dump(set1);
	printf("%lu", set1.size());
	set_dump(set1);
}

void arr_dump() {
	for (int i=1; i<arr.size(); i++) {
		printf("%d ", arr[i]);
	}
}
void set_dump(set<int> a) {
	cout << endl;
	for (set<int>::iterator IterPos = a.begin(); IterPos != a.end(); IterPos++) {
		cout << *IterPos << endl;
	}
}
bool is_equal(set<int> a, set<int> b) {
	if (a.size() != b.size()) {
		return false;
	}
	set<int>::iterator ai, bi;
	ai = a.begin();
	bi = b.begin();
	while (ai != a.end()) {
		if (*ai != *bi) {
			return false;
		}
		ai++;
		bi++;
	}
	return true;
}

3번 직사각형 네개의 합집합의 면적 구하기 문제이다.

https://www.acmicpc.net/problem/2669 (백준 2669번)

N값이 크지 않으므로 좌표평면을 만들어서 죄다 더해버리면 된다.

 

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

using namespace std;

int map[100][100] = {0,};
int rect[4][4];

void dump();
int answer();
int main() {
	for (int i=0; i<4;i++) {
		scanf("%d %d %d %d\n", &rect[i][0], &rect[i][1], &rect[i][2], &rect[i][3]);
	}
	for (int i=0; i<4;i++) {
		for (int x=rect[i][0]; x < rect[i][2]; x++) {
			for(int y=rect[i][1]; y < rect[i][3]; y++) {
				map[x][y]++;
			}
		}
	}
	// dump();
	cout << answer() << endl;
}
int answer() {
	int count = 0;
	for(int i=0;i<100;i++) {
		for (int j=0;j<100;j++) {
			if (map[i][j]) {
				count++;
			}
		}
	}
	return count;
}
void dump() {
	//rect
	// for(int i=0;i<4;i++) {
	// 	for(int j=0;j<4;j++) {
	// 		printf("%d\t", rect[i][j]);
	// 	}
	// }
	
	for(int i=99;i>=0;i--) {
		for(int j=99;j>=0;j--) {
			printf("%d ", map[j][i]);
		}
		putchar('\n');
	}
}