백준 21608번 상어 초등학교 C++

출처 : https://www.acmicpc.net/problem/21608

 

입력받은 순서대로 조건에 맞게 학생들의 자리를 정해줬을 때 학생의 만족도의 총합을 출력하는 문제이다.

코드는 그냥 문제에 나온 조건을 그대로 구현하였다.

실버 1 난이도의 문제인데 푸는데 한시간이 넘게 걸렸다. 

구현 문제 푸는 연습을 많이 해야할 것 같다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
typedef long long ll;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int PosR[4] = { -1,0,1,0 };
	int PosC[4] = { 0,1,0,-1 };

	int n, s_num, input;
	cin >> n;
	vector<vector<int>> student(n * n + 1, vector<int>());
	vector<vector<int>> v(n + 1, vector<int>(n + 1, 0));
	vector<int> seq(n * n + 1);
	for (int i = 1; i <= n * n; i++) {
		cin >> s_num;
		seq[i] = s_num;
		for (int i = 0; i < 4; i++) {
			cin >> input;
			student[s_num].push_back(input);
		}
	}
	
	for (int i = 1; i <= n * n; i++) {
		int max_like_student = 0;
		int max_empty_place = 0;
		pair<int, int> promising_Pos = { 0,0 };
		for (int j = 1; j <= n; j++) {
			for (int k = 1; k <= n; k++) {
				int like_student = 0;
				int empty_place = 0;
				int first_cnt = 0;
				if (v[j][k] != 0) continue;
				for (int y = 0; y < 4; y++) {
					int nextRow = j + PosR[y];
					int nextCol = k + PosC[y];
					if (nextRow<1 || nextRow>n) continue;
					if (nextCol<1 || nextCol>n) continue;
					if (v[nextRow][nextCol] == 0) {
						empty_place++;
					}
					else {
						auto it = find(student[seq[i]].begin(), student[seq[i]].end(), v[nextRow][nextCol]);
						if (it == student[seq[i]].end()) {
							continue;
						}
						like_student++;
					}
				}
				if (promising_Pos.first == 0 && promising_Pos.second == 0) {
					promising_Pos = { j,k };
				}
				if (like_student < max_like_student) continue;
				if (like_student > max_like_student) {
					max_like_student = like_student;
					max_empty_place = empty_place;
					promising_Pos = { j,k };
					continue;
				}
				if (like_student == max_like_student) {
					if (empty_place < max_empty_place) continue;
					if (empty_place > max_empty_place) {
						max_empty_place = empty_place;
						promising_Pos = { j,k };
					}
				}
			}
		}
		v[promising_Pos.first][promising_Pos.second] = seq[i];
	}
	int sum = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			int cnt = 0;
			int curr_student = v[i][j];
			for (int k = 0; k < 4; k++) {
				int nextRow = i + PosR[k];
				int nextCol = j + PosC[k];
				if (nextRow<1 || nextRow>n) continue;
				if (nextCol<1 || nextCol>n) continue;
				int near = v[nextRow][nextCol];
				auto it = find(student[curr_student].begin(), student[curr_student].end(), near);
				if (it != student[curr_student].end()) {
					cnt++;
				}
			}
			if (cnt == 1) sum += 1;
			if (cnt == 2) sum += 10;
			if (cnt == 3) sum += 100;
			if (cnt == 4) sum += 1000;
		}
	}
	cout << sum;
};