반응형
728x170
이것도 정말 구현문제로써
시키는대로 하면 된다.
다만 범위에 신경쓰도록
사용자 입력만이 범위가 아니란 것을 명심하자
https://www.acmicpc.net/problem/21608
#맞는 풀이
#include <iostream>
#include <vector>
#include <algorithm>
#define X first
#define Y second
using namespace std;
int seat[21][21];//자리 배치 1~N만 쓸 것임
int dx[4] = { 1,-1,0,0 }; //방향
int dy[4] = { 0,0,1,-1 }; //방향
int good[5] = { 0,1,10,100,1000 }; //점수
int N;
vector <int> info[401]; //학생 번호와 선호하는 학생을 저장
int main() {
cin >> N;
int num = N * N;
while (num--) {
int st, a, b, c, d;
cin >> st >> a >> b >> c >> d;
info[st].push_back(a);
info[st].push_back(b);
info[st].push_back(c);
info[st].push_back(d);
int x, y; //자리
bool isDone = false; // 해당 작업에서 자리를 찾았는지
//1번 작업
vector<pair<int, int>> vec1[5]; //벡터 배열 선언
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (seat[i][j] == 0) {
int cnt = 0;
for (int dir = 0; dir < 4; dir++) {
int nx = i + dx[dir];
int ny = j + dy[dir];
if (nx<1 || nx>N || ny<1 || ny>N)continue;
if (seat[nx][ny] == a || seat[nx][ny] == b || seat[nx][ny] == c || seat[nx][ny] == d) {
cnt++;
}
}
//해당 인접한 개수만큼에 대해 벡터 추가
vec1[cnt].push_back({ i,j });
}
}
}
//vec1에 대해서 인접한 칸이 많은 벡터부터 찾음
int after1;
for (int i = 4; i >= 0; i--) {
if (vec1[i].empty()) continue;
//비어있지 않다면 개수를 셈
int size = vec1[i].size();
//개수가 1로 유일하면 그 원소가 자리 결정
if (size == 1) {
x = vec1[i][0].X;
y = vec1[i][0].Y;
isDone = true;
break;
}
else {
after1 = i; // 해당 벡터 저장
break;
}
}
//2번 작업 시작 전 자리를 찾았으면 다음 것 찾으러감
if (isDone) {
seat[x][y] = st;
continue;
}
//2번 작업 vec1에서 여러 개의 후보를 가져옴. -> after i에 저장해놓음
//해당 벡터에 들어있는 좌표들의 인접 빈칸 조사
vector<pair<int, int>> vec2[5]; //벡터 배열 선언
for (auto x : vec1[after1]) {
int cnt = 0;
for (int dir = 0; dir < 4; dir++) {
int nx = x.X + dx[dir];
int ny = x.Y + dy[dir];
if (nx<1 || nx>N || ny<1 || ny>N)continue;
if (seat[nx][ny] == 0) { cnt++; } // 해당 자리가 비어있으면
}
vec2[cnt].push_back(x);
}
//vec2에 대해서 인접한 빈칸이 많은 벡터부터 찾음
int after2;
for (int i = 4; i >= 0; i--) {
if (vec2[i].empty()) continue;
//비어있지 않다면 개수를 셈
int size = vec2[i].size();
//개수가 1로 유일하면 자리 결정
if (size == 1) {
x = vec2[i][0].X;
y = vec2[i][0].Y;
isDone = true;
break;
}
else {
after2 = i; // 해당 벡터 번호 저장
break;
}
}
//3번 작업 시작 전 자리를 찾았으면 다음 것 찾으러감
if (isDone) {
seat[x][y] = st;
continue;
}
//3번 작업 시작
//vec2[after2]에 대한 좌표들을 먼저 x(행)으로 오름차순 정렬후 y(열) 오름차순 정렬하여 가장 작은 것
sort(vec2[after2].begin(), vec2[after2].end());
x = vec2[after2][0].X;
y = vec2[after2][0].Y;
isDone = true;
//마지막 자리를 찾아서 넣음
if (isDone) {
seat[x][y] = st;
continue;
}
}
//자리를 모두 배치했으면 만족도 조사
long long ans = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
int number = seat[i][j];
int cnt = 0;
for (int dir = 0; dir < 4; dir++) {
int nx = i + dx[dir];
int ny = j + dy[dir];
if (nx<1 || nx>N || ny<1 || ny>N)continue;
if (seat[nx][ny] == info[number][0] || seat[nx][ny] == info[number][1] || seat[nx][ny] == info[number][2] || seat[nx][ny] == info[number][3]) {
cnt++;
}
}
ans += good[cnt];
}
}
cout << ans;
return 0;
}
info에 대한 것을 처음에 21로 했다.
학생수는 최소 400명인데..ㅠ
제대로 범위 판단하자
728x90
반응형
그리드형
'문제풀이(Problem Solving)' 카테고리의 다른 글
백준, BOJ, 9465번, 스티커: C++ [CPP] (0) | 2021.12.17 |
---|---|
백준, BOJ, 14500번, 테트로미노: C++ [CPP] (0) | 2021.12.10 |
백준, BOJ, 20055번, 컨베이어 벨트 위의 로봇 : C++ [CPP] (0) | 2021.12.08 |
백준, BOJ, 3190번, 뱀 : C++ [CPP] (0) | 2021.12.08 |
백준, BOJ, 1707번, 이분 그래프 : C++ [CPP] ★ (0) | 2021.12.07 |