아이디어
조건
선생님은 학생의 순서를 정했고, 각 학생이 좋아하는 학생 4명도 모두 조사했다
struct student { student() : me(0), like1(0), like2(0), like3(0), like4(0) {} int me; int like1; int like2; int like3; int like4; };
1.비어있는 칸 중에서 좋아하는 학생이 인접한 칸에 가장 많은 칸으로 자리를 정한다.
// 좋아하는 학생 확인하는 함수 bool check_nearby(const student me, const int near) { if (me.like1 == near || me.like2 == near || me.like3 == near || me.like4 == near) { return true; } return false; }
- 1을 만족하는 칸이 여러 개이면, 인접한 칸 중에서 비어있는 칸이 가장 많은 칸으로 자리를 정한다.
constexpr int dr[] = { 0,1,0,-1 }; constexpr int dc[] = { 1,0,-1,0 }; // void select_seat(vector<vector<student>>& grid, const student current_student, const int grid_size) { int select_seat_row = -1; // 선택할 자리의 행 int select_seat_col = -1; // 선택할 자리의 열 int select_seat_count = 0; // 근처에 좋아하는 학생 수 int select_seat_space = 0; // 근처에 빈 자리 수 for (int r = 0; r < grid_size; r++) { for (int c = 0; c < grid_size; c++) { if (grid[r][c].me)continue; // 이미 선택 된 자리면 continue int count = 0; int space = 0; for (int i = 0; i < 4; i++) // 상 하 좌 우 체크 { const int nr = r + dr[i]; const int nc = c + dc[i]; if (nr < 0 || nr >= grid_size || nc < 0 || nc >= grid_size)continue; if (check_nearby(current_student, grid[nr][nc].me)) count++; // 근처자리에 좋아하는 학생이 있으면 if (grid[nr][nc].me == 0) space++; // 근처 자리가 비어있으면 } if (select_seat_count < count) // 조건 1만족하면~ { select_seat_count = count; select_seat_space = space; select_seat_row = r; select_seat_col = c; } else if (select_seat_count == count && select_seat_space < space) // 조건 2 만족하면 { select_seat_space = space; select_seat_row = r; select_seat_col = c; } } } grid[select_seat_row][select_seat_col] = current_student; // 자리 선정 }
- 2를 만족하는 칸도 여러 개인 경우에는 행의 번호가 가장 작은 칸으로, 그러한 칸도 여러 개이면 열의 번호가 가장 작은 칸으로 자리를 정한다.
// 3번 조건 // 2번 조건에서 선택하지 않고 끝까지 갔을 경우 빈 칸 탐색 if (select_seat_row == -1) select_one(grid, select_seat_row, select_seat_col, grid_size); // select_one함수 void select_one(const vector<vector<student>>& grid, int& select_seat_row, int& select_seat_col, const int grid_size) { for (int r = 0; r < grid_size; r++) { for (int c = 0; c < grid_size; c++) { if (grid[r][c].me == 0) { select_seat_row = r; select_seat_col = c; return; } } } }
만족도 구하기
학생의 만족도를 구하려면 그 학생과 인접한 칸에 앉은 좋아하는 학생의 수를 구해야 한다. 그 값이 0이면 학생의 만족도는 0, 1이면 1, 2이면 10, 3이면 100, 4이면 1000이다.
int print_student_satisfaction(const vector<vector<student>>& grid) { const int row = static_cast<int>(grid.size()); const int col = static_cast<int>(grid[0].size()); int total_score = 0; for (int r = 0; r < row; r++) { for (int c = 0; c < col; c++) { int satisfaction = 0; for (int i = 0; i < 4; i++) { const int nr = r + dr[i]; const int nc = c + dc[i]; if (nr < 0 || nr >= row || nc < 0 || nc >= col)continue; if (check_nearby(grid[r][c], grid[nr][nc].me)) satisfaction++; } total_score += static_cast<int>(pow(10, satisfaction)) / 10; } } return total_score; }
정답 코드
#include<bits/stdc++.h>
using namespace std;
#define FAST_IO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr)
struct student
{
student() : me(0), like1(0), like2(0), like3(0), like4(0) {}
int me;
int like1;
int like2;
int like3;
int like4;
};
constexpr int dr[] = { 0,1,0,-1 };
constexpr int dc[] = { 1,0,-1,0 };
bool check_nearby(const student me, const int near)
{
if (me.like1 == near ||
me.like2 == near ||
me.like3 == near ||
me.like4 == near)
{
return true;
}
return false;
}
void select_one(const vector<vector<student>>& grid, int& select_seat_row, int& select_seat_col, const int grid_size)
{
for (int r = 0; r < grid_size; r++)
{
for (int c = 0; c < grid_size; c++)
{
if (grid[r][c].me == 0)
{
select_seat_row = r;
select_seat_col = c;
return;
}
}
}
}
void select_seat(vector<vector<student>>& grid, const student current_student, const int grid_size)
{
int select_seat_row = -1;
int select_seat_col = -1;
int select_seat_count = 0;
int select_seat_space = 0;
for (int r = 0; r < grid_size; r++)
{
for (int c = 0; c < grid_size; c++)
{
if (grid[r][c].me)continue;
int count = 0;
int space = 0;
for (int i = 0; i < 4; i++)
{
const int nr = r + dr[i];
const int nc = c + dc[i];
if (nr < 0 || nr >= grid_size || nc < 0 || nc >= grid_size)continue;
if (check_nearby(current_student, grid[nr][nc].me)) count++;
if (grid[nr][nc].me == 0) space++;
}
if (select_seat_count < count)
{
select_seat_count = count;
select_seat_space = space;
select_seat_row = r;
select_seat_col = c;
}
else if (select_seat_count == count && select_seat_space < space)
{
select_seat_space = space;
select_seat_row = r;
select_seat_col = c;
}
}
}
if (select_seat_row == -1) select_one(grid, select_seat_row, select_seat_col, grid_size);
grid[select_seat_row][select_seat_col] = current_student;
}
int print_student_satisfaction(const vector<vector<student>>& grid)
{
const int row = static_cast<int>(grid.size());
const int col = static_cast<int>(grid[0].size());
int total_score = 0;
for (int r = 0; r < row; r++)
{
for (int c = 0; c < col; c++)
{
int satisfaction = 0;
for (int i = 0; i < 4; i++)
{
const int nr = r + dr[i];
const int nc = c + dc[i];
if (nr < 0 || nr >= row || nc < 0 || nc >= col)continue;
if (check_nearby(grid[r][c], grid[nr][nc].me)) satisfaction++;
}
total_score += static_cast<int>(pow(10, satisfaction)) / 10;
}
}
return total_score;
}
int main()
{
FAST_IO;
int grid_size; cin >> grid_size;
const int student_num = grid_size * grid_size;
vector<vector<student>> grid(grid_size, vector<student>(grid_size));
vector<student>students(student_num);
for (student& student : students)
{
cin >> student.me >> student.like1 >> student.like2 >> student.like3 >> student.like4;
}
for (const student student : students)
{
select_seat(grid, student, grid_size);
}
cout << print_student_satisfaction(grid) << '\n';
return 0;
}
