📜 문제
문제링크
시뮬레이션 문제로 문제에서 주어진 조건을 구현하기만 하면 된다.
📖 풀이
문제의 조건을 읽어보면 현재 관찰하는 영역을 기준으로 (비어 있는 칸)
1) 인접한 영역에 좋아하는 학생의 수
2) 인접한 영역에 비어있는 영역의 수
3) 관찰하는 영역의 (r , c)
총 3가지를 저장하는 공간이 필요한 것을 알 수 있다. 이를 비어 있는 모든 칸에 대해서 수행하고 나면 현재 자리를 배치할 학생의 가능한 모든 자리에 대해서 위의 3가지가 저장되게 된다. 그리고 이를 문제의 조건에 맞게 정렬하면 현재 관찰하는 학생의 자리를 확정할 수 있다.
- 공간복잡도
1) 각 학생별로 선호하는 학생을 저장 할 배열
int[400][4]
2) 각 학생의 위치를 저장할 board 배열int[20][20]
3) 위의 세가지를 저장할 vectorint[20][20] x4
3)의 경우에 pair 를 이용해 pair<int,pair<int,pair<int,int>>>> 형태로 저장
메모리 제한이 1024Mb로 약 2.4억개의 int 를 사용할 수 있기 때문에 메모리 초과는 발생하지 않는다.
- 시간복잡도
1) 해당 학생의 가능한 모든 자리를 조사
O(N^2)
2) 해당 학생의 가능한 모든 자리를 정렬O(N^2)
3) 자리를 모두 결정하고 점수를 매기는 과정O(N^2)
최악의 경우를 기준으로 생각해보자
학생들의 자리가 배정됨에 따라 1), 2) 과정의 시간복잡도는 줄어들겠지만 계산상의 편의를 위해 모든 학생들의 자리 배정이 위의 시간복잡도를 따른다고 해보자.
N^2 * O(N^2) = O(N^4) 이지만 N의 최대값이 20이기 때문에 1초내에 통과 할 수 있다.
🖥 코드
#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;
int n,answer;
int dy[4]={-1,1,0,0};
int dx[4]={0,0,-1,1};
int prefer[404][4];
int board[22][22];
//인접한 칸에 좋아하는 학생수, 인접한 칸에 비어있는 칸, {행,열} 를 문제의 조건에 맞게 정렬하기 위한 compare 함수
bool compare(pair<int,pair<int,pair<int,int>>>v1, pair<int,pair<int,pair<int,int>>>v2){
if(v1.first == v2.first){
if(v1.second.first == v2.second.first){
if(v1.second.second.first == v2.second.second.first){
return v1.second.second.second < v2.second.second.second;
}
return v1.second.second.first < v2.second.second.first;
}
else return v1.second.first > v2.second.first;
}
else return v1.first > v2.first;
}
void student_position(int num){
//인접한 칸에 좋아하는 학생수, 인접한 칸에 비어있는 칸, {행,열} 순서로 저장
vector<pair<int,pair<int,pair<int,int>>>>v;
for(int y=0; y<n; y++){
for(int x=0; x<n; x++){
if(board[y][x]!=0)continue;
int first=0,second=0;
//인접한 영역을 돌면서 좋아하는 학생수, 비어있는 칸의 개수를 센다.
for(int dir=0; dir<4; dir++){
int ny=y+dy[dir];
int nx=x+dx[dir];
if(ny<0 || ny>=n || nx<0 || nx>=n)continue;
if(board[ny][nx]==0)second++;
else{
for(int i=0; i<4; i++){
int prefer_student=prefer[num][i];
if(board[ny][nx]==prefer_student)first++;
}
}
}
v.push_back({first,{second,{y,x}}});
}
}
sort(v.begin(),v.end(),compare);
int y=v[0].second.second.first;
int x=v[0].second.second.second;
board[y][x]=num;//조건에 맞는 위치에 학생을 배치한다.
}
//학생들이 모두 앉았을때 점수를 구하기 위한 함수
void make_answer(){
for(int y=0; y<n; y++){
for(int x=0; x<n; x++){
int num=board[y][x];
int cnt=0;
for(int dir=0; dir<4; dir++){
int ny=y+dy[dir];
int nx=x+dx[dir];
if(ny<0 || ny>=n || nx<0 || nx>=n)continue;
for(int i=0; i<4; i++){
if(board[ny][nx]==prefer[num][i])cnt++;
}
}
if(cnt==0)continue;
else if(cnt==1)answer+=1;
else if(cnt==2)answer+=10;
else if(cnt==3)answer+=100;
else answer+=1000;
}
}
}
int main(void){
ios::sync_with_stdio(0);
cin.tie(0);
cin>>n;
for(int i=1; i<=n*n; i++){
int num;
cin>>num;
for(int j=0; j<4; j++){
cin>>prefer[num][j];
}
student_position(num);
}
make_answer();
cout<<answer;
return 0;
}🔨 피드백
처음 문제를 읽었을 때, 정렬을 이용하면 문제를 쉽게 해결할 수 있겠다라는 생각은 들었지만 막상 sort 함수의 cmp 함수를 만드는 과정에서 조금 시간이 걸렸다.
bool cmp1(int a, int b){
return a>b;
}
bool cmp2(int a, int b){
if(a>b) return true;
else return false;
}위의 두 cmp 함수는 a가 b보다 클 때 우선적으로 정렬을 하겠다는 것을 의미한다. 그리고 이번 문제를 풀기 위해서 선언했던 cmp 함수를 살펴보자!
bool compare(pair<int,pair<int,pair<int,int>>>v1, pair<int,pair<int,pair<int,int>>>v2){
if(v1.first == v2.first){
if(v1.second.first == v2.second.first){
if(v1.second.second.first == v2.second.second.first){
return v1.second.second.second < v2.second.second.second;
}
return v1.second.second.first < v2.second.second.first;
}
else return v1.second.first > v2.second.first;
}
else return v1.first > v2.first;
}위의 경우를 살펴보면 현재 살펴보는 칸과 인접한 영역에 좋아하는 학생의 수가 큰 경우 우선적으로 정렬하고, 만약 같다면 인접한 영역에 비어있는 칸 수 가 큰 경우 우선적으로 정렬하고 , 마찬가지로 비어 있는 칸수가 같으면 행, 열 순서대로 살피도록 설정했다.
문제 자체의 풀이는 조건 그대로를 구현하면 되기 때문에 다른 문제들에 비해서 쉽게 느껴졌지만 항상 정렬에서 cmp를 만드는 부분이 헷갈리는 것 같다! 관련 문제들 풀어보면서 확실하게 개념공부 해야겠다!🔥
