재현시의 시장 구재현은 지난 몇 년간 게리맨더링을 통해서 자신의 당에게 유리하게 선거구를 획정했다. 견제할 권력이 없어진 구재현은 권력을 매우 부당하게 행사했고, 심지어는 시의 이름도 재현시로 변경했다. 이번 선거에서는 최대한 공평하게 선거구를 획정하려고 한다.
재현시는 크기가 N×N인 격자로 나타낼 수 있다. 격자의 각 칸은 구역을 의미하고, r행 c열에 있는 구역은 (r, c)로 나타낼 수 있다. 구역을 다섯 개의 선거구로 나눠야 하고, 각 구역은 다섯 선거구 중 하나에 포함되어야 한다. 선거구는 구역을 적어도 하나 포함해야 하고, 한 선거구에 포함되어 있는 구역은 모두 연결되어 있어야 한다. 구역 A에서 인접한 구역을 통해서 구역 B로 갈 수 있을 때, 두 구역은 연결되어 있다고 한다. 중간에 통하는 인접한 구역은 0개 이상이어야 하고, 모두 같은 선거구에 포함된 구역이어야 한다.
선거구를 나누는 방법은 다음과 같다.
기준점 (x, y)와 경계의 길이 d1, d2를 정한다. (d1, d2≥ 1, 1 ≤ x < x+d1+d2≤ N, 1 ≤ y-d1< y < y+d2≤ N)
1) (x, y)에서 시작해서 왼쪽 아래 대각선으로 d1만큼 한 번 씩 내려간다. (< v)
2) 한 줄 씩 내려가면서 가로로 y까지 5 선거구역임을 표시한다.
3 )(x, y)에서 시작해서 오른쪽 아래 대각선으로 d2만큼 한 번 씩 내려간다.(> v)
4) 한 줄 씩 내려가면서 y부터 가로로 y까지 5 선거구역임을 표시한다.
5) 위의 1),2)번을 수행한 뒤의 위치부터 다시 오른쪽 대각선 아래로 d2만큼 한 번 씩 이동한다. (> v)
6) 한 줄 씩 내려가면서 가로로 y까지 5 선거구역임을 표시한다.
7) 위의 3),4)번을 수행한 뒤의 위치부터 다시 왼쪽 대각선 아래로 d1만큼 한 번 씩 이동한다. (< v)
8) ) 한 줄 씩 내려가면서 y부터 가로로 y까지 5 선거구역임을 표시한다.
이렇게 하면 5선거구역 표시가 끝난다.
2단계 : 1~4 선거구역 표시 => getpartOne(); getpartTwo(); getpartThree(); getpartFour();
그 다음은 문제에서 주어진 아래의 1~4 선거구역의 범위에 따라
1번 선거구: 1 ≤ r < x+d1, 1 ≤ c ≤ y
2번 선거구: 1 ≤ r ≤ x+d2, y < c ≤ N
3번 선거구: x+d1≤ r ≤ N, 1 ≤ c < y-d1+d2
4번 선거구: x+d2< r ≤ N, y-d1+d2 ≤ c ≤ N
이미 5선거구역으로 표시되어 있는 곳을 제외하고 해당 선거구역 숫자료 표시해 주면 된다.
#include <iostream>
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
int A[21][21];
//위 오 아 왼
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,1,0,-1 };
int divideMap[21][21];
int N;
//1~N 사이에 들어오는지 범위 체크
bool chk(int r, int c) {
if (r<1 || r>N || c<1 || c>N) return false;
return true;
}
//1~4 선거구역 표시. 5가 이미 표시되어 있는 경우 패스
int getpartOne(int x, int y, int d1, int d2) {
int sum = 0;
for (int i = 1; i < x + d1; i++) {
for (int j = 1; j <= y; j++) {
if (divideMap[i][j] != 5) { //5구역 만나면 다음 줄
divideMap[i][j] = 1;
sum += A[i][j];
}
}
}
return sum;
}
int getpartTwo(int x, int y, int d1, int d2) {
int sum = 0;
for (int i = 1; i <= x + d2; i++) { //1~4
for (int j = y + 1; j <= N; j++) { //6~7
if (divideMap[i][j] != 5) {
divideMap[i][j] = 2;
sum += A[i][j];
}
}
}
return sum;
}
int getpartThree(int x, int y, int d1, int d2) {
int sum = 0;
for (int i = x + d1; i <= N; i++) { //i = 5,6,7
for (int j = 1; j < y - d1 + d2; j++) {
if (divideMap[i][j] != 5) {
divideMap[i][j] = 3;
sum += A[i][j];
}
}
}return sum;
}
int getpartFour(int x, int y, int d1, int d2) {
int sum = 0;
for (int i = x + d2 + 1; i <= N; i++) {
for (int j = y - d1 + d2; j <= N; j++) {
if (divideMap[i][j] != 5) {
divideMap[i][j] = 4;
sum += A[i][j];
}
}
}return sum;
}
//5선거구역 표시. 범위 넘어가서 다른 선거구역의 크기가 최소 1이상 되지 않는 경우 false 리턴
bool divide(int x, int y, int d1, int d2) {
memset(divideMap, 0, sizeof(divideMap));
divideMap[x][y] = 5;
int initR = x;
int initC = y;
//1
for (int k = 0; k < d1; k++) {
int nr = initR + 1;
int nc = initC - 1;
if (!chk(nr, nc)) {
return false;
}
initR = nr;
initC = nc;
for (int col = nc; col <= y; col++) {
divideMap[nr][col] = 5;
}
}
//2
int initR2 = x;
int initC2 = y;
for (int k = 0; k < d2; k++) {
int nr = initR2 + 1;
int nc = initC2 + 1;
if (!chk(nr, nc)) {
return false;
}
initR2 = nr;
initC2 = nc;
for (int col = y; col <= nc; col++) {
divideMap[nr][col] = 5;
}
}
//3
int startR = x + d1;
int startC = y - d1;
for (int k = 0; k < d2; k++) {
int nr = startR + 1;
int nc = startC + 1;
if (!chk(nr, nc)) {
return false;
}
startR = nr;
startC = nc;
for (int col = nc; col <= y - d1 + d2; col++) {
divideMap[nr][col] = 5;
}
}
int startR2 = x + d2;
int startC2 = y + d2;
for (int k = 0; k < d1; k++) {
int nr = startR2 + 1;
int nc = startC2 - 1;
if (!chk(nr, nc)) {
return false;
}
startR2 = nr;
startC2 = nc;
for (int col = y - d1 + d2; col <= nc; col++) {
divideMap[nr][col] = 5;
}
}
return true;
}
int main() {
cin >> N;
int sumA = 0;
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
cin >> A[i][j];
sumA += A[i][j];
}
}
//각 칸을 돌면서 기준점 정함
int mini = 987654321;
for (int x = 1; x <= N; x++) { //행
for (int y = 1; y <= N; y++) { //열
for (int d1 = 1; d1 <= 18; d1++) {
for (int d2 = 1; d2 <= 18; d2++) {
if (x + d1 + d2 > N) break;
if (!divide(x, y, d1, d2)) continue;
int sum1 = getpartOne(x, y, d1, d2);
int sum2 = getpartTwo(x, y, d1, d2);
int sum3 = getpartThree(x, y, d1, d2);
int sum4 = getpartFour(x, y, d1, d2);
int sum5 = sumA - (sum1 + sum2 + sum3 + sum4);
//각 선거구역 크기는 최소 1칸 이상
if (sum1 >= 1 && sum2 >= 1 && sum3 >= 1 && sum4 >= 1 && sum5 >= 1) {// 선거구는 구역을 적어도 하나 포함해야 하고
vector<int> vec = { sum1, sum2, sum3, sum4, sum5 };
sort(vec.begin(), vec.end());
int maxNum = vec[4];
int minNum = vec[0];
if (mini > maxNum - minNum) mini = maxNum - minNum;
}
}
}
}
}
cout << mini;
return 0;
}
모노미노도미노는 아래와 같이 생긴 보드에서 진행되는 게임이다. 보드는 빨간색 보드, 파란색 보드, 초록색 보드가 그림과 같이 붙어있는 형태이다. 게임에서 사용하는 좌표 (x, y)에서 x는 행, y는 열을 의미한다. 빨간색, 파란색, 초록색 보드가 사용하는 좌표는 그 색으로 그림에 적혀있다.
<그림 1> 모노미노도미노 게임 보드
이 게임에서 사용하는 블록은 타일 하나 또는 두 개가 가로 또는 세로로 붙어있는 형태이다. 아래와 같이 세 종류가 있으며, 왼쪽부터 순서대로 크기가 1×1, 1×2, 2×1 이다.
<그림 2> 모노미노도미노 게임에서 사용하는 블록
블록을 놓을 위치를 빨간색 보드에서 선택하면, 그 위치부터 초록색 보드로 블록이 이동하고, 파란색 보드로 블록이 이동한다. 블록의 이동은 다른 블록을 만나거나 보드의 경계를 만나기 전까지 계속해서 이동한다. 예를 들어, 크기가 1×1인 블록을 (1, 1)에 놓으면, 보드의 상태는 <그림 3>과 같이 변한다.
<그림 3>
여기서 크기가 1×2인 블록을 (3, 0)과 (3, 1)에 놓으면 <그림 4>와 같이 보드의 상태가 변한다.
<그림 4>
다시 이 상태에서 크기가 2×1인 블록을 (2, 2), (3, 2)와 (2, 3), (3, 3)에 놓으면 <그림 5>와 같이 변한다.
<그림 5>
초록색 보드의 4번 행은 모든 칸이 타일로 가득 차있다. 이렇게 초록색 보드에서 어떤 행이 타일로 가득 차 있다면, 그 행의 타일은 모두 사라진다. 사라진 이후에는 초록색 보드에서 사라진 행의 위에 있는 블록이 사라진 행의 수만큼 아래로 이동한다. 파란색의 경우는 열이 타일로 가득 차 있으면, 그 열의 타일이 모두 사라지며, 사라진 이후에는 파란색 보드에서 사라진 열의 왼쪽에 있는 블록이 사라진 열의 수만큼 오른쪽으로 이동한다. 이렇게 한 행이나 열이 타일로 가득 차서 사라지면 1점을 획득한다. 점수는 사라진 행 또는 열의 수와 같다. 만약, 두 개의 행이 사라지면 2점을 획득하게 되고, 한 행과 한 열이 사라져도 2점을 획득하게 된다. 위의 보드는 아래와 같이 변하고, 1점을 얻는다.
<그림 6>
여기서 크기가 2×1인 블록을 (1, 3), (2, 3)에 놓으면 보드는 <그림 7>과 같이 변한다.
<그림 7>
초록색 보드의 0, 1번 행과 파란색 보드의 0, 1번 열은 그림에는 연한색으로 표현되어 있는 특별한 칸이다. 초록색 보드의 0, 1번 행에 블록이 있으면, 블록이 있는 행의 수만큼 아래 행에 있는 타일이 사라지고, 초록색 보드의 모든 블록이 사라진 행의 수만큼 아래로 이동하고, 파란색 보드의 0, 1번 열에 블록이 있으면, 블록이 있는 열의 수만큼 오른쪽 열에 있는 타일이 사라지고, 파란색 보드의 모든 블록이 사라진 열의 수만큼 이동하게 된다. 위의 그림은 파란색 보드의 1번 열에 블록이 있기 때문에, 5번 열에 있는 블록이 모두 사라지고, 파란색 보드의 모든 블록이 오른쪽으로 한 칸 이동하게 된다. 따라서, 보드는 <그림 8>과 같이 변하게 된다.
<그림 8>
위의 보드에서 1×2인 블록을 (0, 0), (0, 1)에 놓으면 <그림 9>와 같다.
<그림 9>
여기서 크기가 2×1인 블록을 (2, 0), (3, 0)에 놓으면 <그림 10>과 같이 변한다. 파란색 보드는 1번 열에 블록이 생겨서 오른쪽으로 한 칸씩 이동한 상태이다.
<그림 10>
크기가 2×1인 블록을 (1, 2), (2, 2)에 놓으면, <그림 11>과 같이 변한다.
<그림 11>
파란색 보드는 1번 열에 블록이 있기 때문에, 5번 열의 타일이 사라지고 모든 블록이 오른쪽으로 한 칸씩 이동하게 된다. 초록색 보드는 4번 행의 모든 칸에 타일이 있기 때문에, 1점을 얻으면서, 4번 행의 모든 타일이 사라진다.
<그림 12>
<그림 12>는 <그림 11>의 상태에서 파란색 보드는 모든 블록이 오른쪽으로 한 칸 이동했고, 초록색 보드의 4번 행이 모두 사라진 상태이다. 이제, 초록색 보드에서 사라진 행의 위에 있는 블록이 아래로 한 칸씩 내려와야 한다. 이동한 후의 상태는 <그림 13>과 같다.
<그림 13>
행이나 열이 타일로 가득찬 경우와 연한 칸에 블록이 있는 경우가 동시에 발생할 수 있다. 이 경우에는 행이나 열이 타일로 가득 찬 경우가 없을 때까지 점수를 획득하는 과정이 모두 진행된 후, 연한 칸에 블록이 있는 경우를 처리해야 한다.
블록은 보드에 놓인 이후에 다른 블록과 합쳐지지 않는다. 블록을 놓은 위치가 순서대로 주어졌을 때, 얻은 점수와 초록색 보드와 파란색 보드에 타일이 있는 칸의 개수를 모두 구해보자.
입력
첫째 줄에 블록을 놓은 횟수 N(1 ≤ N ≤ 10,000)이 주어진다.
둘째 줄부터 N개의 줄에 블록을 놓은 정보가 한 줄에 하나씩 순서대로 주어지며,t x y와 같은 형태이다.
t = 1: 크기가 1×1인 블록을 (x, y)에 놓은 경우
t = 2: 크기가 1×2인 블록을 (x, y), (x, y+1)에 놓은 경우
t = 3: 크기가 2×1인 블록을 (x, y), (x+1, y)에 놓은 경우
블록이 차지하는 칸이 빨간색 칸의 경계를 넘어가는 경우는 입력으로 주어지지 않는다.
출력
첫째 줄에 블록을 모두 놓았을 때 얻은 점수를 출력한다.
둘째 줄에는 파란색 보드와 초록색 보드에서 타일이 들어있는 칸의 개수를 출력한다.
접근 방법
줄이 꽉 차서 삭제하고 한줄씩 밀 때, 인덱스를 증가시켜서
밀려서 검사하지 못한 그 줄을 검사해줘야한다.
처음에는 while(1)문 안에서
꽉 찬 줄을 찾고 한 줄씩 삭제했다. 5~0 돌고 삭제하고 다시 5~0을 돌았다. 그랬더니 계속 '틀렸습니다' 가 떴다. 그래서 5~0 번은 한 번만 돌고 꽉 찬 줄을 발견했을 때 인덱스를 조정해서 멈췄던 곳 부터 다시 진행을 했다.
shift 할 때 마지막 줄은 따로 삭제를 해줘야하는 것도 주의하자.
#include <iostream>
#include <string.h>
#include <vector>
using namespace std;
int red[4][4];
int blue[4][6];
int green[6][4];
int ans = 0;
//열 지우는 함수
void delColBlue(int col) {
for (int r = 0; r < 4; r++) {
blue[r][col] = 0;
}
}
void delRowGreen(int row) {
for (int c = 0; c < 4; c++) {
green[row][c] = 0;
}
}
int maxBlue(int row) {//걸리지 않을때까지 오른쪽 또는 아래로 밀었을 때
for (int col = 0; col <= 5; col++) {
if (blue[row][col] == 1) {
return col - 1;
}
}return 5;
}
int maxGreen(int col) {
for (int row = 0; row <= 5; row++) {
if (green[row][col] == 1) {
return row - 1;
}
}return 5;
}
//STEP 1 : 블록 놓기
void shiftFunc(int t, int x, int y) {
if (t == 1) {
blue[x][maxBlue(x)] = 1;
green[maxGreen(y)][y] = 1;
}
else if (t == 2) { //1*2
int c = maxBlue(x);
blue[x][c] = 1;
blue[x][c - 1] = 1;
int r = maxGreen(y);
int r2 = maxGreen(y + 1);
if (r < r2) {
green[r][y] = 1;
green[r][y + 1] = 1;
}
else {
green[r2][y] = 1;
green[r2][y + 1] = 1;
}
}
else { //2*1
int c = maxBlue(x);
int c2 = maxBlue(x + 1);
if (c < c2) {
blue[x][c] = 1;
blue[x + 1][c] = 1;
}
else {
blue[x][c2] = 1;
blue[x + 1][c2] = 1;
}
int r = maxGreen(y);
green[r][y] = 1;
green[r - 1][y] = 1;
}
}
void eraseAndpushBlue(int col) {
for (int c = col; c >= 1; c--) {
for (int r = 0; r < 4; r++) {
blue[r][c] = blue[r][c - 1];
}
}
}
void eraseAndpushGreen(int row) {
for (int r = row; r >= 1; r--) {
for (int c = 0; c < 4; c++) {
green[r][c] = green[r - 1][c];
}
}
}
//STEP 2 : 가장 오른쪽 또는 아래부터 4칸 다 찬 줄을 찾아서 삭제하고 shift
void getFullLine() {
//blue
for (int c = 5; c >= 2; c--) {
int cnt = 0;
for (int r = 0; r < 4; r++) {
if (blue[r][c] == 0) break;
else cnt++;
}
if (cnt == 4) {
ans++;
eraseAndpushBlue(c);
c++;
}
}
//green
for (int r = 5; r >= 2; r--) {
int cnt = 0;
for (int c = 0; c < 4; c++) {
if (green[r][c] == 0) break;
else cnt++;
}
if (cnt == 4) {
ans++;
eraseAndpushGreen(r);
r++;
}
}
}
//STEP 3 : 0, 1 번째 줄에 블록 있을 때 있는 줄의 수 만큼 shift
void specialBlue() {
int cnt = 0;
for (int c = 0; c <= 1; c++) {
for (int r = 0; r < 4; r++) {
if (blue[r][c] == 1) {
cnt++;
break;
}
}
}
for (int c = 5; c >= 2; c--) {
for (int r = 0; r < 4; r++) {
blue[r][c] = blue[r][c - cnt];
}
}
delColBlue(1);
delColBlue(0);
}
void specialGreen() {
int cnt = 0;
for (int r = 0; r <= 1; r++) {
for (int c = 0; c < 4; c++) {
if (green[r][c] == 1) {
cnt++;
break;
}
}
}
for (int r = 5; r >= 2; r--) {
for (int c = 0; c < 4; c++) {
green[r][c] = green[r - cnt][c];
}
}
delRowGreen(0);
delRowGreen(1);
}
//블록 수 카운트
int tileBlue() {
int res = 0;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 6; j++) {
if (blue[i][j] == 1) res++;
}
}
return res;
}
int tileGreen() {
int res = 0;
for (int i = 0; i < 6; i++) {
for (int j = 0; j < 4; j++) {
if (green[i][j] == 1) res++;
}
}
return res;
}
int main() {
int N; cin >> N;
memset(red, 0, sizeof(red));
memset(blue, 0, sizeof(blue));
memset(green, 0, sizeof(green));
for (int T = 0; T < N; T++) {
int t, x, y;
cin >> t >> x >> y;
shiftFunc(t, x, y); //빨간색에서 파란색, 초록색 보드로 타일 밀기
getFullLine();
specialBlue();
specialGreen();
}
cout << ans << "\n" << tileBlue() + tileGreen();
return 0;
}
아래 배열은 map 배열로, (H x W) 만큼 배열 B에서 복사해온것이다. (H x W)만큼을 제외한 곳은 0으로 채웠다.
1
2
3
4
0
5
7
9
11
0
9
15
17
19
0
0
0
0
0
0
X=1, Y=1이므로 색으로 표시한 곳이 겹치는 부분이다.
우리는 배열 A를 쉽게 알 수 있는데, 이 배열 A를 이용해서 거꾸로 생각해보면 코드를 쉽게 구현할 수 있다. 배열 A는 아래와 같다.
1
2
3
4
5
6
7
8
9
10
11
12
이걸 X=1, Y=1만큼 옮겨서 겹친 것을 구현해보면, 다음과 같다.
1
2
3
4
0
5
6+1
7+2
8+3
4
9
10+15
11+6
12+7
8
0
9
10
11
12
매 행을 진행해 나가면서 겹친 부분끼리 뺀 값을 갱신해줘야, 다음 행을 계산할 때 그 값이 반영돼서 올바른 값이 나온다.
다시 말하면, map[1][1]에서 map[1-X][1-Y]를 빼서 map[1][1]을 6으로 갱신해줘야, 그 다음 행의 map[2][2]-map[2-X][2-Y]를 계산할 때 올바르게 11에서 6을 뺄 수 있다. (매 행마다 값을 갱신해주지 않으면 11에서 (6+1) 을 뺀 것으로 계산된다.)
길이가 N인 컨베이어 벨트가 있고, 길이가 2N인 벨트가 이 컨베이어 벨트를 위아래로 감싸며 돌고 있다. 벨트는 길이 1 간격으로 2N개의 칸으로 나뉘어져 있으며, 각 칸에는 아래 그림과 같이 1부터 2N까지의 번호가 매겨져 있다.
벨트가 한 칸 회전하면 1번부터 2N-1번까지의 칸은 다음 번호의 칸이 있는 위치로 이동하고, 2N번 칸은 1번 칸의 위치로 이동한다. i번 칸의 내구도는 Ai이다. 위의 그림에서 1번 칸이 있는 위치를 "올라가는 위치", N번 칸이 있는 위치를 "내려가는 위치"라고 한다.
컨베이어 벨트에 박스 모양 로봇을 하나씩 올리려고 한다. 로봇은 올라가는 위치에만 땅에서 올라가고, 내려가는 위치에서만 땅으로 내려갈 수 있다. 내려가는 위치에 로봇이 있는 경우 로봇은 반드시 땅으로 내려가야 한다. 로봇이 어떤 칸에 올라가거나 이동하면 그 칸의 내구도는 즉시 1만큼 감소한다. 내구도가 0인 칸에는 로봇이 올라갈 수 없다.
로봇은 컨베이어 벨트 위에서 스스로 이동할 수 있다.
컨베이어 벨트를 이용해 로봇들을 건너편으로 옮기려고 한다. 로봇을 옮기는 과정에서는 아래와 같은 일이 순서대로 일어난다.
벨트가 한 칸 회전한다.
가장 먼저 벨트에 올라간 로봇부터, 벨트가 회전하는 방향으로 한 칸 이동할 수 있다면 이동한다. 만약 이동할 수 없다면 가만히 있는다.
로봇이 이동하기 위해서는 이동하려는 칸에 로봇이 없으며, 그 칸의 내구도가 1 이상 남아 있어야 한다.
올라가는 위치에 로봇이 없다면 로봇을 하나 올린다.
내구도가 0인 칸의 개수가 K개 이상이라면 과정을 종료한다. 그렇지 않다면 1번으로 돌아간다.
종료되었을 때 몇 번째 단계가 진행 중이었는지 구해보자. 가장 처음 수행되는 단계는 1번째 단계이다.
입력
첫째 줄에 N, K가 주어진다. 둘째 줄에는 A1, A2, ..., A2N이 주어진다.
출력
몇 번째 단계가 진행 중일때 종료되었는지 출력한다.
제한
2 ≤ N ≤ 100
1 ≤ K ≤ 2N
1 ≤ Ai≤ 1,000
접근 방법
문제에서 주어진 조건대로만 잘 구현하면 되는 문제이다.
beltArr[1]에 로봇이 들어오고 beltArr[N]에서 로봇이 나가는 것에 유의하자.
내구도는 beltArr[1] ~ beltArr[2N] 에서 숫자가 돌고,
로봇은 isRobot[1] ~ isRobot[N] 에서만 도는 것도 주의해야한다.
(처음에 로봇도 1부터 2N까지 돌려서 계속 헤맸었다.)
나머지는 주석을 참고하면 된다.
#include <iostream>
#include <utility>
using namespace std;
int beltArr[201] = {0};
pair<int,bool> isRobot[101]; //몇번째인지, 로봇 있는지여부
int N,K;
bool cntZero(){ //내구도 0인 곳이 K개 이상이면 true 리턴
int cnt = 0;
bool res = false;
for(int i = 1; i<=2*N; i++){
if(beltArr[i]==0){
cnt++;
}
if(cnt>=K) {
res = true;
break;
}
}
return res;
}
int findFirstRobot(){ //1~N 칸에서 가장 먼저 들어간 로봇 찾기
for(int i = N; i>=1; i--){
if(isRobot[i].second==true){
return i;
}
}
return 0;
}
//2번 : 로봇 한칸 전진 : 먼저 올라간 로봇부터 / 이동 가능하면(로봇 없고, 내구도 1이상) / 로봇&내구도 바꿈
void shiftRobot(){
int minIdx = findFirstRobot();
if(minIdx!=0){
for(int i = minIdx; i>=1; i--){
if(isRobot[i].second==true){ //현재 자리에 로봇이 있고
if(i==N){ //마지막 로봇은 그냥 내림
isRobot[i].first = 0;
isRobot[i].second = false;
}
else{
if(isRobot[i+1].second==false && beltArr[i+1]>=1){ //다음 자리에 로봇 없고, 내구도 1 이상이면
isRobot[i+1] = isRobot[i]; //다음 칸으로 옮기고
beltArr[i+1] -= 1;
isRobot[i].first = 0; //옮겼으니까 초기화
isRobot[i].second = false;
}
}
}
}
}
}
//1번 : 회전 : 내구도 & 로봇 위치 shift
void shiftNumber(){
//내구도 이동
int tmp = beltArr[2*N];
for(int i = 2*N -1; i>=1; i--){
beltArr[i+1] = beltArr[i];
}
beltArr[1] = tmp;
//로봇 이동
//내리는 위치의 로봇 처리
isRobot[N].first = 0;
isRobot[N].second = false;
for(int i = N-1; i>=1; i--){
isRobot[i+1] = isRobot[i];
}
isRobot[1].first=0;
isRobot[1].second = false;
}
//3번 : beltArr[1]에 로봇없으면 로봇 하나 올림
bool putRobot(int order){
if(beltArr[1]>=1 && isRobot[1].second==false) { //처음칸의 내구도 1 이상이고 로봇 없으면
beltArr[1]-=1; //내구도 1 감소
isRobot[1].first = order;
isRobot[1].second = true;
return true;
}
return false;
}
int solution(){
int ord = 1;
int step = 1;
while(1){
//한칸회전
shiftNumber();
if(cntZero()){break;}
//먼저 올라간 로봇부터 전진
shiftRobot();
if(cntZero()){break;}
//1번 비었으면 로봇 올림
if(putRobot(ord)){ //로봇 올릴 수 있었으면 ord++
ord++;
}
if(cntZero()){break;}
step+=1;
}
return step;
}
int main(){
cin>>N>>K;
for(int i = 1; i<=N; i++){
scanf("%d", &beltArr[i]);
isRobot[i].first = 0;
isRobot[i].second = false;
}
for(int i = N+1; i<=2*N; i++){
scanf("%d", &beltArr[i]);
}
cout << solution();
return 0;
}
오늘은 이 지도에서 지나갈 수 있는 길이 몇 개 있는지 알아보려고 한다. 길이란 한 행 또는 한 열 전부를 나타내며, 한쪽 끝에서 다른쪽 끝까지 지나가는 것이다.
다음과 같은 N=6인 경우 지도를 살펴보자.
이때, 길은 총 2N개가 있으며, 아래와 같다.
길을 지나갈 수 있으려면 길에 속한 모든 칸의 높이가 모두 같아야 한다. 또는, 경사로를 놓아서 지나갈 수 있는 길을 만들 수 있다. 경사로는 높이가 항상 1이며, 길이는 L이다. 또, 개수는 매우 많아 부족할 일이 없다. 경사로는 낮은 칸과 높은 칸을 연결하며, 아래와 같은 조건을 만족해야한다.
경사로는 낮은 칸에 놓으며, L개의 연속된 칸에 경사로의 바닥이 모두 접해야 한다.
낮은 칸과 높은 칸의 높이 차이는 1이어야 한다.
경사로를 놓을 낮은 칸의 높이는 모두 같아야 하고, L개의 칸이 연속되어 있어야 한다.
아래와 같은 경우에는 경사로를 놓을 수 없다.
경사로를 놓은 곳에 또 경사로를 놓는 경우
낮은 칸과 높은 칸의 높이 차이가 1이 아닌 경우
낮은 지점의 칸의 높이가 모두 같지 않거나, L개가 연속되지 않은 경우
경사로를 놓다가 범위를 벗어나는 경우
L = 2인 경우에 경사로를 놓을 수 있는 경우를 그림으로 나타내면 아래와 같다.
경사로를 놓을 수 없는 경우는 아래와 같다.
위의 그림의 가장 왼쪽부터 1번, 2번, 3번, 4번 예제라고 했을 때, 1번은 높이 차이가 1이 아니라서, 2번은 경사로를 바닥과 접하게 놓지 않아서, 3번은 겹쳐서 놓아서, 4번은 기울이게 놓아서 불가능한 경우이다.
가장 위에 주어진 그림 예의 경우에 지나갈 수 있는 길은 초록색으로, 지나갈 수 없는 길은 빨간색으로 표시되어 있으며, 아래와 같다. 경사로의 길이 L = 2이다.
지도가 주어졌을 때, 지나갈 수 있는 길의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에 N (2 ≤ N ≤ 100)과 L (1 ≤ L ≤ N)이 주어진다. 둘째 줄부터 N개의 줄에 지도가 주어진다. 각 칸의 높이는 10보다 작거나 같은 자연수이다.
출력
첫째 줄에 지나갈 수 있는 길의 개수를 출력한다.
접근 방법
각각 행에 대해, 열에 대해 연산이 중복되는데 인덱스가 헷갈려서 크기가 2N인 벡터배열에 넣고 동일한 인덱스를 사용했다.
한칸씩 전진하면서 옆의 요소와 비교하며 길을 탐색하는데, 이때 총 네가지 경우가 있다.
1) 옆의 요소와 같을 때 -> sameHeight++ (검사했던 길에 높이가 같은 평평한 길이 얼마나 있는지)
2) 옆의 요소의 높이가 1 더 높을 때 -> 이제까지 왔던 길에서 높이가 같아 평평한 길이 L만큼 있는지 체크
3) 옆의 요소의 높이가 1 더 낮을 때 -> 앞으로 검사할 길에 높이가 같아 평평한 길이 L만큼 있는지 체크
4) 옆의 요소랑 높이 차이가 2 이상일 때 -> stop 하고 다음 검사할 길로 바로 넘어감
