반응형
[모의 SW 역량테스트] 활주로 건설
1. 이해하기
- 활주로는 높이가 동일한 구간에서 건설이 가능하다.
- 높이가 다른 구간의 경우 활주로가 끊어지기 때문에 길이가 X이고, 높이가 1인 경사로를 설치해야만 한다.
- 경사로는 경사로의 길이만큼 활주로의 높이가 같아야 설치가 가능하다.
- 동일한 위치에 두 개 이상의 경사로를 겹쳐서 사용할 수 없다.
- 경사로는 세워서 사용할 수 없다.
2. 구현하기
-
각 활주로마다 경사로를 설치할 수 있는지 확인한다.
- 활주로에 경사로가 설치가 이미 되어있는지 확인.
- 경사로의 길이만큼 활주로의 높이가 같은지 확인.
bool is_installed(bool install[20], int st, int en) { for(int i = st; i <= en; i++) { if(install[i]) return true; } return false; } bool is_same_height_row(int row, int st, int en) { int height = map[row][st]; for(int i = st; i <= en; i++) { if(height != map[row][i]) return false; } return true; } bool can_install_row(bool install[20], int row, int st, int en) { if(is_installed(install,st,en)) return false; if(!is_same_height_row(row,st,en)) return false; return true; } void install_way(bool install[20], int st, int en) { for(int i = st; i <= en; i++) { install[i] = true; } } bool is_same_height_col(int col, int st, int en) { int height = map[st][col]; for(int i = st; i <= en; i++) { if(height != map[i][col]) return false; } return true; } bool can_install_col(bool install[20], int col, int st, int en) { if(is_installed(install,st,en)) return false; if(!is_same_height_col(col,st,en)) return false; return true; }
-
각 행과 열에 대해서 활주로가 될 수 있는지 검사한다.
int solve() { int ret = 0; for(int i = 0; i < N; i++) { bool flag = true; bool install[20] = {false,}; for(int j = 0; j < N-1; j++) { if(map[i][j]+1 < map[i][j+1] or map[i][j] > map[i][j+1]+1) { flag = false; break; } else if(map[i][j]+1 == map[i][j+1]) { int st = j-X+1, en = j; if(st < 0) { flag = false; break; } if(!can_install_row(install,i,st,en)) { flag = false; break; } else { install_way(install,st,en); } } else if(map[i][j] == map[i][j+1]+1) { int st = j+1, en = j+X; if(en >= N) { flag = false; break; } if(!can_install_row(install,i,st,en)) { flag = false; break; } else { install_way(install,st,en); } } } if(flag) ret++; memset(install,false,sizeof(install)); flag = true; for(int j = 0; j < N-1; j++) { if(map[j][i]+1 < map[j+1][i] or map[j][i] > map[j+1][i]+1) { flag = false; break; } else if(map[j][i]+1 == map[j+1][i]) { int st = j-X+1, en = j; if(st < 0) { flag = false; break; } if(!can_install_col(install, i, st, en)) { flag = false; break; } else { install_way(install,st,en); } } else if(map[j][i] == map[j+1][i]+1) { int st = j+1, en = j+X; if(en >= N) { flag = false; break; } if(!can_install_col(install,i,st,en)) { flag = false; break; } else { install_way(install,st,en); } } } if(flag) ret++; } return ret; }
3. 전체 코드
#include <iostream>
#include <cstring>
using namespace std;
int map[20][20];
int N,X;
bool is_installed(bool install[20], int st, int en) {
for(int i = st; i <= en; i++) {
if(install[i]) return true;
}
return false;
}
bool is_same_height_row(int row, int st, int en) {
int height = map[row][st];
for(int i = st; i <= en; i++) {
if(height != map[row][i]) return false;
}
return true;
}
bool can_install_row(bool install[20], int row, int st, int en) {
if(is_installed(install,st,en)) return false;
if(!is_same_height_row(row,st,en)) return false;
return true;
}
void install_way(bool install[20], int st, int en) {
for(int i = st; i <= en; i++) {
install[i] = true;
}
}
bool is_same_height_col(int col, int st, int en) {
int height = map[st][col];
for(int i = st; i <= en; i++) {
if(height != map[i][col]) return false;
}
return true;
}
bool can_install_col(bool install[20], int col, int st, int en) {
if(is_installed(install,st,en)) return false;
if(!is_same_height_col(col,st,en)) return false;
return true;
}
int solve() {
int ret = 0;
for(int i = 0; i < N; i++) {
bool flag = true;
bool install[20] = {false,};
for(int j = 0; j < N-1; j++) {
if(map[i][j]+1 < map[i][j+1] or map[i][j] > map[i][j+1]+1) {
flag = false; break;
} else if(map[i][j]+1 == map[i][j+1]) {
int st = j-X+1, en = j;
if(st < 0) {
flag = false; break;
}
if(!can_install_row(install,i,st,en)) {
flag = false; break;
} else {
install_way(install,st,en);
}
} else if(map[i][j] == map[i][j+1]+1) {
int st = j+1, en = j+X;
if(en >= N) {
flag = false; break;
}
if(!can_install_row(install,i,st,en)) {
flag = false; break;
} else {
install_way(install,st,en);
}
}
}
if(flag) ret++;
memset(install,false,sizeof(install));
flag = true;
for(int j = 0; j < N-1; j++) {
if(map[j][i]+1 < map[j+1][i] or map[j][i] > map[j+1][i]+1) {
flag = false; break;
} else if(map[j][i]+1 == map[j+1][i]) {
int st = j-X+1, en = j;
if(st < 0) {
flag = false; break;
}
if(!can_install_col(install, i, st, en)) {
flag = false; break;
} else {
install_way(install,st,en);
}
} else if(map[j][i] == map[j+1][i]+1) {
int st = j+1, en = j+X;
if(en >= N) {
flag = false; break;
}
if(!can_install_col(install,i,st,en)) {
flag = false; break;
} else {
install_way(install,st,en);
}
}
}
if(flag) ret++;
}
return ret;
}
void input() {
cin >> N >> X;
for(int i = 0; i < N; i++) {
for(int j = 0; j < N; j++) {
cin >> map[i][j];
}
}
}
int main() {
int T;
cin >> T;
for(int t = 1; t <= T; t++) {
input();
cout << '#' << t << ' ' << solve() << '\n';
}
return 0;
}
'알고리즘 > SW Expert Academy' 카테고리의 다른 글
[모의 SW 역량테스트] 4012. 요리사 (0) | 2019.10.18 |
---|---|
[모의 SW 역량테스트] 4013. 특이한 자석 (0) | 2019.10.17 |
[모의 SW 역량테스트] 2117. 홈 방범 서비스 (0) | 2019.10.17 |
[모의 SW 역량테스트] 2112. 보호 필름 (0) | 2019.10.17 |
[모의 SW 역량테스트] 2115. 벌꿀채취 (0) | 2019.10.16 |