알고리즘
백준 21608번 상어 초등학교 C++
영춘권의달인
2021. 11. 23. 12:40



입력받은 순서대로 조건에 맞게 학생들의 자리를 정해줬을 때 학생의 만족도의 총합을 출력하는 문제이다.
코드는 그냥 문제에 나온 조건을 그대로 구현하였다.
실버 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;
};