💡 구현
Memory 2036KB Time 4ms Code Length 4698B
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
//비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
//1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
//2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.
// 탐색하면서 주변에 좋아하는 학생 카운트 -> 최댓값 구하고 vector(최댓값을 가진 인덱스,비어있는칸 갯수,y,x) 만들고 정렬해서 맨앞에 나온 값을 맵에 추가(숫자)
// 최종적으로 탐색하면서 좋아하는 학생 카운트하기.
#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
using namespace std;
int N;
int survey[400][5]; // 0번 인덱스는 현재 학생의 번호임
int dy[] = { -1,1,0,0 };
int dx[] = { 0,0, -1,1 };
struct info_map {
int num, likeNum;
};
struct info_vector {
int max, emptyblock, y, x;
};
bool cmp(const info_vector & first,const info_vector & second) {
if (first.emptyblock > second.emptyblock) {
return true;
}
else if (first.emptyblock == second.emptyblock) {
if (first.y < second.y) {
return true;
}
else if (first.y == second.y) {
if (first.x < second.x) {
return true;
}
}
}
return false;
}
info_map MAP[20][20] = {0};
void init() {
memset(MAP, 0, sizeof(MAP));
memset(survey, 0, sizeof(survey));
cin >> N;
for (int i = 0; i < N*N; i++) {
for (int j = 0; j < 5; j++) {
cin >> survey[i][j];
}
}
}
void putStudent(int index) {
//비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
//1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
//2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.
// 탐색하면서 주변에 좋아하는 학생 카운트 -> 최댓값 구하고 vector(최댓값,비어있는칸 갯수,y,x) 만들고 정렬해서 맨앞에 나온 값을 맵에 추가(숫자와 최댓값)
int StudentNum = survey[index][0];
vector<info_vector> vc;
int cntMax = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (MAP[i][j].num == 0) { // 해당 칸이 빈칸이라면
int likecnt = 0;
int emptycnt = 0;
for (int k = 0; k < 4; k++) {
int ny = i + dy[k];
int nx = j + dx[k];
if (ny >= N || nx >= N || ny < 0 || nx < 0)continue;
if (MAP[ny][nx].num == 0) emptycnt++;
else {
for (int t = 1; t <= 4; t++) {
if (MAP[ny][nx].num == survey[index][t]) likecnt++;
}
}
}
if (cntMax < likecnt) { // 해당 칸에서부터 다시 쌓음
vc.clear();
cntMax = likecnt;
vc.push_back({ cntMax, emptycnt, i,j });
}
else if (cntMax == likecnt) { // 벡터에 추가.
vc.push_back({ cntMax, emptycnt, i,j });
}
}
}
}
if (vc.size() == 0) return;
sort(vc.begin(), vc.end(), cmp);
info_vector FindLoc = vc[0]; // 찾은 위치
MAP[FindLoc.y][FindLoc.x].num = StudentNum;
}
int findresult() {
for (int i = 0; i < N; i++) { // 현재 주위에 좋아하는 사람 수 파악하기
for (int j = 0; j < N; j++) {
int likecnt = 0;
int StudentNum = MAP[i][j].num;
int index = 0;
for (int k = 0; k < N*N; k++) { // survey에서 인덱스 찾아야함
if (survey[k][0] == StudentNum) {
index = k;
break;
}
}
for (int k = 0; k < 4; k++) {
int ny = i + dy[k];
int nx = j + dx[k];
if (ny >= N || nx >= N || ny < 0 || nx < 0)continue;
for (int t = 1; t <= 4; t++) {
if (MAP[ny][nx].num == survey[index][t]) likecnt++;
}
}
MAP[i][j].likeNum = likecnt;
}
}
int sum = 0;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (MAP[i][j].likeNum == 1) {
sum += 1;
}
else if (MAP[i][j].likeNum == 2) {
sum += 10;
}
else if (MAP[i][j].likeNum == 3) {
sum += 100;
}
else if (MAP[i][j].likeNum == 4) {
sum += 1000;
}
}
}
return sum;
}
void printMap() {
cout << endl;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout << MAP[i][j].num << " ";
}
cout << endl;
}
cout << endl;
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cout << MAP[i][j].likeNum << " ";
}
cout << endl;
}
}
int main() {
init();
for (int i = 0; i < N*N; i++) {
putStudent(i);
}
//printMap();
int result = findresult();
cout << result << endl;
}
이 코드는 N x N 크기의 공간에 학생들을 배치하는 프로그램이다.
init 함수에서는 입력으로 받은 N값과 학생들의 선호도를 survey 배열에 저장한다.
putStudent 함수에서는 각 학생을 순서대로 배치한다. 빈 칸 중에서 인접한 칸에 가장 많은 좋아하는 학생을 찾아서 배치한다. 만약 여러 칸이 동률이면, 빈 칸이 가장 많은 칸으로, 그런 칸도 여러 개이면 행의 번호가 작은 칸으로, 그런 칸도 여러 개이면 열의 번호가 작은 칸으로 배치한다.
findresult 함수에서는 각 학생 주변에 몇 명의 좋아하는 학생이 있는지 계산하고, 이를 바탕으로 만족도를 계산한다.
main 함수에서는 init 함수를 통해 초기화를 한 뒤, putStudent 함수를 통해 학생을 배치하고, findresult 함수를 통해 만족도를 계산하여 출력한다.
