이 문제는 처음에 이해하는데만 20분 이상 걸린 것 같다. 문제 설명이 부실한 느낌?을 많이 받았다.
이 문제에서는 조건들이 굉장히 많이 나오는데 결국 중요한 것은 N X N인 격자 내에서 5개의 선거구를 만들 수 있는 조건을 충족하면서 각 선거구 인구의 최댓값에서 최솟값을 뺀 값이 최솟값이 되어야 한다.
여기서 중요한 것은 5개의 선거구를 만들 수 있는 조건이다.
문제 조건 중 일부를 보면 경계선을 만들 수 있는 조건이 나와 있다. 이 경계선과 경계선 안에 포함되어 있는 곳이 5번 선거구가 된다. 그렇다면 이 5번 선거구를 어떻게 구현할 것인지 생각해봐야 한다.
본인은 입력으로 주어지는 선거구의 인구를 MAP이라는 2차원 배열에 저장하였다. 그리고 선거구를 나눠주기 위해 TEMP라는 2차원 배열을 사용하였다.
기본적인 흐름은 완전 탐색이다. 완전 탐색이기 때문에 i와 j가 0부터 n-1까지 탐색한다. 그리고 5개의 선거구를 만들 수 있는 d1과 d2인 경우에 각 선거구를 나눈 뒤 합을 계산한다.
여기서 어려웠던 것은 d1과 d2의 범위 설정이다. d1과 d2의 길이를 잘 설정해야 범위 안에 들어오는 경계선을 만들 수 있는데 생각보다 쉽지 않았다.
기본적으로 d1의 길이에 따라 왼쪽 대각선의 길이가 정해지고 d2의 길이에 따라 오른쪽 대각선의 길이가 정해진다.
첫 번째 예시에서 d1이 3이고 d2가 2인 경우를 생각해보자. 5개의 선거구로 나눌 수 있을까? 나눌 수 있다.
하지만 d1이 4가 되는 순간 d2의 길이와 관계없이 범위를 벗어나게 된다. 그렇다면 첫 번째 예시에서 d1의 최대 길이는 3일 것이다. 여기서 또 3은 어떻게 구할 수 있을까?
본인은 인덱스를 0부터 시작했기 때문에 첫 번째 예시에서 기준점은 (1,3)이다. 기준점을 보면 알 수 있듯이 d1은 현재 기준점의 y좌표만큼 갈 수 있다. 현재 기준점의 y좌표 길이보다 커지면 범위를 벗어나는 것이다.
그렇다면 d2는 어떨까?
이번에는 두 번째 예시를 보자. d2가 2인 경우가 최대 길이라는 것을 쉽게 알 수 있다. d2가 3이 되는 순간 범위를 벗어나기 때문이다. 그러면 d2의 최대 길이가 2인 것은 어떻게 구할 수 있을까?
현재 n은 7이고 기준점은 (1,4)이다. 여기서 n-y를 하게 되면 3이 된다. 이 뜻은 n-y 전까지가 d2의 최대 길이 범위가 된다는 것이다.
d1과 d2의 최대 길이 범위를 구했기 때문에 남은 것은 선거구를 나눠주는 방법과 각 선거구의 인구를 합하는 방법이다.
선거구를 나눠주기 전에 할 일은 경계선이 범위 안에 들어오는지 체크하는 것이다.
본인은 꼭짓점 4개를 기준으로 선거구를 나눌 것이기 때문에 이 꼭짓점들 중에 하나라도 범위를 벗어나면 경계선을 만들지 못한다고 판단하였다.
첫 번째 예시를 다시 봤을 때 꼭짓점을 사진과 같이 번호를 붙였다.(인덱스는 0부터 시작하므로 0,1,2,3)
각 꼭짓점의 좌표는 문제에 제시되어있다.
1번은 (x, y) , 2번은 (x + d1, y - d1), 3번은 (x + d2, y + d2), 4번은 (x + d2 + d1, y + d2 - d1)이다.
1번은 기준점이기 때문에 항상 범위 안에 있으므로 범위를 체크할 필요가 없다.
그러므로 2번, 3번, 4번 꼭짓점이 범위 안에 들어오면 벡터에 각 꼭짓점 좌표를 넣어준다.
위 그림 같은 경우 v[0] = {1,3} , v[1] = {3,1} , v[2] = {3,5}, v[3] = {5,3} 이런 식으로 저장한다.
이제 선거구를 나눠줘야 한다.
우선 TEMP 배열을 모두 5로 초기화를 시켜준다. 그 이후에 4번 반복문을 돌면서 1, 2, 3, 4번 선거구를 정할 것이다.
1번 선거구의 경우에 행은 2번 꼭짓점 전까지, 열은 1번 꼭짓점까지 포함한다.
2번 선거구의 경우에 행은 2번 꼭짓점까지, 열은 n-1까지 포함한다.
3, 4번 선거구는 아래서부터 탐색한다.
3번 선거구의 경우에 행은 2번 꼭짓점까지, 열은 4번 꼭짓점 전까지 포함한다.
4번 선거구의 경우에 행은 3번 꼭짓점 전까지, 열은 n-1까지 포함한다.
각 선거구마다 규칙이 다르기 때문에 범위를 잘 설정해가며 선거구를 나눠야 한다.
1번 선거구는 1번 선거구의 행이 1번 꼭짓점의 행과 같거나 커지면 열의 범위를 하나씩 줄이면 된다.
2번 선거구는 2번 선거구의 행이 1번 꼭짓점의 행보다 커지면 열의 시작 지점을 한 칸씩 앞으로 간다.
3번 선거구는 3번 선거구의 행이 4번 꼭짓점의 행보다 작을 때 열의 범위를 하나씩 줄이면 된다.
4번 선거구는 4번 선거구의 행이 4번 꼭짓점의 행과 같거나 작을 때 열의 시작 지점을 한 칸씩 앞으로 간다.
이 부분은 코드를 보면 이해가 쉬울 것이다.
이런 식으로 선거구를 다 나눴으면 각 선거구의 인구의 합을 구해야 한다.
선거구의 인구의 최댓값에서 최솟값을 빼야 하기 때문에 본인은 각 선거구의 합을 배열에 저장한 뒤 정렬을 통해 그 차이를 구하였다. 이 차이가 한 번 기준점을 정하고 경계선을 정상적으로 그렸을 때 각 선거구 인구의 최댓값과 최솟값의 차이기 때문에 min 함수를 이용하여 그 차이를 업데이트해준다. 그리고 마지막에 최솟값을 출력해주면 된다.
[소스 코드]
#include <bits/stdc++.h>
using namespace std;
int n;
int MAP[21][21];
int TEMP[21][21];
vector<pair<int, int>> v;
int SUM[6];
int MIN = 2147483647;
bool check(int x, int y, int d1, int d2) {
if (x + d1 >= n || y - d1 < 0) return false;
else if (x + d2 >= n || y + d2 >= n) return false;
else if (x + d2 + d1 >= n || y + d2 - d1 < 0) return false;
return true;
}
void calculate() {
int sum = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
SUM[TEMP[i][j]] += MAP[i][j];
}
}
sort(SUM, SUM + 6);
sum = SUM[5] - SUM[1];
MIN = min(MIN, sum);
fill(SUM, SUM + 6, 0);
}
void setting() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
TEMP[i][j] = 5;
}
}
}
void go() {
setting();
int cnt = 0;
for (int i = 0; i < v[1].first; i++) {
if (i >= v[0].first) cnt++;
for (int j = 0; j <= v[0].second - cnt; j++) {
TEMP[i][j] = 1;
}
}
cnt = 0;
for (int i = 0; i <= v[2].first; i++) {
if (i > v[0].first) cnt++;
for (int j = v[0].second + 1 + cnt; j < n; j++) {
TEMP[i][j] = 2;
}
}
cnt = 0;
for (int i = n - 1; i >= v[1].first; i--) {
if (i < v[3].first) cnt++;
for (int j = 0; j < v[3].second - cnt; j++) {
TEMP[i][j] = 3;
}
}
cnt = 0;
for (int i = n - 1; i > v[2].first; i--) {
if (i <= v[3].first) cnt++;
for (int j = v[3].second + cnt; j < n; j++) {
TEMP[i][j] = 4;
}
}
v.clear();
}
void INPUT() {
cin >> n;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
cin >> MAP[i][j];
}
}
}
void solve() {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
for (int d1 = 1; d1 <= j; d1++) {
for (int d2 = 1; d2 < n - j; d2++) {
if (check(i, j, d1, d2)) {
v.push_back({ i,j });
v.push_back({ i + d1, j - d1 });
v.push_back({ i + d2, j + d2 });
v.push_back({ i + d1 + d2, j - d1 + d2 });
go();
calculate();
}
}
}
}
}
cout << MIN;
}
int main() {
cin.tie(0);
ios::sync_with_stdio(0);
INPUT();
solve();
return 0;
}
톱니바퀴가 4개있고 각 톱니바퀴는 8개의 톱니로 이루어져 있다. 그리고 톱니는 N극(0) 또는 S극(1)으로 이루어져 있다.
각 톱니바퀴는 맞닿은 극이 서로 다르면 회전을 한다. 즉, n번째 톱니바퀴의 2번째 톱니와 n+1번째 톱니바퀴의 6번째 톱니의 극이 서로 다르면 회전을 한다. (톱니는 0부터 시작한다고 가정)
톱니바퀴를 K번 회전시킨 후 조건에 따라 점수를 더한다.
회전 후 각 톱니바퀴의 12시 방향이 S극이면 점수를 더하는데 1번 톱니바퀴는 1점, 2번 톱니바퀴는 2점, 3번 톱니바퀴는 4점, 4번 톱니바퀴는 8점이다. 합산한 점수를 출력하면 된다.
왼쪽 톱니바퀴부터 1번, 2번, 3번, 4번 톱니바퀴이다.
그림과 같은 톱니바퀴가 주어진다면 아래와 같은 숫자로 나타낼 수 있다.
10101111
01111101
11001110
00000010
그 다음엔 K가 주어지고 회전시킬 톱니바퀴 번호와 방향을 입력받는다.
예를 들어 2 1이면 2번 톱니바퀴를 시계방향으로 돌리는 것이다. 1 -1이면 1번 톱니바퀴를 반시계 방향으로 돌리는 것이다.
본인은 문제를 쉽게 풀기 위해 톱니바퀴를 덱으로 선언하여 풀었다.
문제에는 톱니바퀴가 1번부터 시작했지만 본인은 0번부터 시작하였다. 그래서 처음 톱니바퀴 번호를 입력받을 때 -1을 해준다.
회전할 톱니바퀴를 찾기 위해 벡터와 큐를 사용하였다. 또한, 톱니바퀴의 방문 체크를 해주었다.
여기서 중요한 것은 K번 입력받는 톱니바퀴들은 그 방향으로 무조건 회전을 한다. 인접한 톱니바퀴와 극이 같다고 해서 회전을 안 하는 것이 아니다.
그리고 이 문제는 회전하기 전의 상태에서 맞닿은 극이 서로 다르면 서로 다른 방향으로 회전한다. 즉, 입력받은 톱니바퀴를 해당 방향으로 회전시킨 뒤 인접한 톱니바퀴와 맞닿은 극이 서로 다른지를 보는 것이 아니다. 본인은 이 부분에서 문제를 잘못 이해하여 계속 틀렸다.
다시 문제로 돌아와서 처음 입력받는 톱니바퀴 번호와 방향을 큐와 벡터에 넣어준다. 큐는 회전할 톱니바퀴를 찾기 위해서 사용하고, 벡터는 톱니바퀴 정보를 저장하고 실제로 회전시키기 위해 사용한다.
큐가 빌 때까지 반복하면서 회전할 큐를 찾는다. 여기서 톱니바퀴가 0번째가 아닌 경우, 3번째가 아닌 경우로 나뉜다.
0번째가 아닌 경우는 현재 톱니바퀴와 그 왼쪽 톱니바퀴의 맞닿은 극이 서로 다른지, 방문한 톱니바퀴인지 체크한다.
3번째가 아닌 경우는 현재 톱니바퀴와 그 오른쪽 톱니바퀴의 맞닿은 극이 서로 다른지, 방문한 톱니바퀴인지 체크한다.
방문하지 않았고, 맞닿은 극이 서로 다르면 큐와 벡터에 톱니바퀴 번호와 반대 방향(방향 * -1)을 넣어준 뒤 해당 톱니바퀴를 방문 체크해준다.
큐를 통해 회전할 톱니바퀴를 다 찾았으면 반복문을 빠져나오고 벡터에 저장된 회전할 톱니바퀴들을 실제로 회전시킨다.
톱니바퀴는 덱으로 선언했기 때문에 숫자를 앞뒤로 넣고 빼는 것이 쉽다.
시계 방향인 경우 뒤에 숫자를 저장한 뒤 삭제하고 저장한 숫자를 앞에 넣어주면 된다.
반시계 방향인 경우 앞에 숫자를 저장한 뒤 삭제하고 저장한 숫자를 뒤에 넣어주면 된다.
이 작업을 K번 반복한 뒤 마지막에 점수를 더해주면 된다.
K번 반복할 때 방문 체크 배열을 초기화해주고 벡터를 초기화해줘야 한다.
[소스 코드]
#include <bits/stdc++.h>
using namespace std;
int k; //회전 횟수
bool check[4];
deque<int> dq[4]; // 톱니바퀴 상태 저장 및 회전하기 위한 덱
queue<pair<int, int>> q; // 회전할 톱니바퀴를 저장하기 위한 큐
vector<pair<int, int>> v; // 회전할 톱니바퀴들을 실제로 방향에 따라 회전시키기 위한 벡터
void rotate() {
for (int i = 0; i < v.size(); i++) { // 톱니바퀴 회전
int cur_num = v[i].first;
int cur_d = v[i].second;
if (cur_d == 1) { // 시계 방향이면
int tmp = dq[cur_num].back(); // 현재 톱니바퀴의 마지막 숫자를 tmp에 저장
dq[cur_num].pop_back(); // 현재 톱니바퀴의 마지막 숫자 삭제
dq[cur_num].push_front(tmp); // 현재 톱니바퀴의 앞에다가 tmp 삽입
}
else { // 시계 반대방향이면
int tmp = dq[cur_num].front(); // 현재 톱니바퀴의 첫번째 숫자를 tmp에 저장
dq[cur_num].pop_front(); // 현재 톱니바퀴의 첫번째 숫자 삭제
dq[cur_num].push_back(tmp); // 현재 톱니바퀴의 뒤에다가 tmp 삽입
}
}
}
void check_rotate() {
cin >> k;
for (int i = 0; i < k; i++) {
memset(check, false, sizeof(check));
v.clear();
int num, d;
cin >> num >> d;
num -= 1; // 인덱스를 0부터 시작하기 위해 입력되는 num값에서 -1
v.push_back({ num,d }); // 처음 입력받는 톱니바퀴와 방향을 푸쉬
q.push({ num, d }); // 처음 입력받는 톱니바퀴와 방향을 푸쉬
check[num] = true; // 해당 톱니바퀴 방문체크
while (!q.empty()) {
int cur_num = q.front().first; // 현재 톱니바퀴 숫자
int cur_d = q.front().second; // 회전할 방향
q.pop();
if (cur_num != 0) { // 톱니바퀴가 첫번째가 아니라면
if (dq[cur_num - 1][2] != dq[cur_num][6] && !check[cur_num - 1]) {
// 왼쪽 톱니바퀴와 극이 다르고 왼쪽 톱니바퀴를 방문하지 않았다면
q.push({ cur_num - 1, cur_d * -1 }); // 왼쪽 톱니바퀴 번호와 반대 방향을 큐에 푸쉬
v.push_back({ cur_num - 1, cur_d * -1 }); // 왼쪽 톱니바퀴 번호와 반대 방향을 벡터에 푸쉬
check[cur_num - 1] = true; // 왼쪽 톱니바퀴 방문 체크
}
}
if (cur_num != 3) { // 톱니바퀴가 마지막이 아니라면
if (dq[cur_num][2] != dq[cur_num + 1][6] && !check[cur_num + 1]) {
// 오른쪽 톱니바퀴와 극이 다르고 오른쪽 톱니바퀴를 방문하지 않았다면
q.push({ cur_num + 1, cur_d * -1 }); // 오른쪽 톱니바퀴 번호와 반대 방향을 큐에 푸쉬
v.push_back({ cur_num + 1, cur_d * -1 }); // 오른쪽 톱니바퀴 번호와 반대 방향을 벡터에 푸쉬
check[cur_num + 1] = true; // 오른쪽 톱니바퀴 방문 체크
}
}
}
rotate();
}
}
void count() {
int cnt = 0;
if (dq[0][0] == 1) cnt += 1;
if (dq[1][0] == 1) cnt += 2;
if (dq[2][0] == 1) cnt += 4;
if (dq[3][0] == 1) cnt += 8;
cout << cnt;
}
void INPUT() {
for (int i = 0; i < 4; i++) {
string str;
cin >> str;
for (int j = 0; j < 8; j++) {
dq[i].push_back(str[j] - '0'); // 톱니바퀴 처음 상태 저장
}
}
}
void solve() {
INPUT();
check_rotate();
count();
}
int main() {
cin.tie(0); ios::sync_with_stdio(0);
solve();
return 0;
}
