CS/Algorithm
[SWEA][C++] 4014 활주로 건설
별토끼.
2018. 12. 20. 18:17
반응형
[SWEA][C++] 4014 활주로 건설
문제
https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWIeW7FakkUDFAVH
풀이
문제에서 주어진 조건들을 모두 충족시키도록 코드를 구현했습니다.
우선, col과 row 고정을 하여 두가지 과정으로 분리하였습니다. 이후, 현재 층과 다음 층을 비교하여 다음 층이 큰 경우와 작은 경우, 다음 층과 같은 경우, 2층 이상 차이나는 경우로 나누었습니다.
다음 층이 작은 경우, 범위를 체크하고 높이가 다음 층과 X의 범위 안에 들어오는 배열 값들을 비교해줍니다. 이 때, 활주로를 세웠다는 것을 possible배열을 이용해 체크합니다. 조건 충족이 안될 경우 isOK를 true로 바꿉니다.
다음 층이 큰 경우, 범위 체크 후 현재 층과 X의 범위 안의 값들을 비교하고 활주로가 세워졌는지 possible 배열을 통해 확인합니다. 조건 충족이 안될 경우 isOK를 true로 바꿉니다.
다음 층과 같을 경우 continue로 넘어가고, 다음 층과 2층 이상 차이 날 경우 isOK변수를 true로 바꾸고 for문을 빠져나갑니다.
한 줄을 마치고 isOK변수가 false일 경우 result값을 증가시켜줍니다.
추가로 코드를 고치다보니 코드가 지저분하네요ㅠㅠ다음에는 더 빨리 풀어야지.... (5시간 걸린건 안비밀...)
코드
#include <iostream>
using namespace std;
int N, X;
int **arr;
int main() {
int T;
cin >> T;
for (int t = 0; t < T; t++) {
/* t번째 케이스 시작 */
cin >> N >> X;
/* n크기의 동적 배열 생성 */
arr = new int*[N];
for (int n = 0; n < N; n++) {
arr[n] = new int[N];
}
/* 배열 값 입력 받기 */
for (int p = 0; p < N; p++) {
for (int q = 0; q < N; q++) {
cin >> arr[p][q];
}
}
int result = 0;
int *possible;
/* (row고정) 다음 층이 높은 층? 낮은 층? 인지 알아보기 */
for (int i = 0; i < N; i++) {
possible = new int[N];
fill_n(possible, N, 0);
int isOK = false;
for (int j = 0; j < N-1; j++) {
/*현재 층*/
int now = arr[i][j];
/*다음 층*/
int next = arr[i][j+1];
/*다음 층이 큰 경우*/
if (next - now == 1 ) {
/*j부터 (j+1)-(x)까지 같은 층인지 확인*/
/* 범위초과 경우 break */
if ((j + 1) - X < 0) {
isOK = true;
break;
}
for (int x = 1; x <= X; x++) {
/*높이 확인*/
if (arr[i][(j+1) - x] == now) {
/*이미 세웠는지 확인*/
if(possible[(j + 1) - x] == 0)
/*활주로 가능*/
continue;
else {
isOK = true;
break;
}
}
/*아닐 경우 break*/
else{
isOK = true;
break;
}
}
}
/*다음 층이 작은 경우*/
else if(next - now == -1){
/*범위 초과 break*/
if (j + X >= N) {
isOK = true;
break;
}
for (int x = 1; x <= X; x++) {
/*높이 확인*/
if (arr[i][j + x] == next) {
//활주로 세움 표시
possible[j + x] = 1;
continue;
}
else {
isOK = true;
break;
}
}
}
/*다음층과 같을 경우*/
else if (next - now == 0){
continue;
}
/*다음 층과 2이상 차이가 날 경우*/
else {
isOK = true;
}
if (isOK == true) break;
}
if (isOK == false) {
++result;
}
}
/* (col고정) 다음 층이 높은 층? 낮은 층? 인지 알아보기*/
for (int i = 0; i < N; i++) {
possible = new int[N];
fill_n(possible, N, 0);
int isOK = false;
for (int j = 0; j < N - 1; j++) {
/*현재 층*/
int now = arr[j][i];
/*다음 층*/
int next = arr[j+1][i];
/*다음 층이 큰 경우*/
if (next - now == 1) {
/*범위 확인*/
if ((j + 1) - X < 0) {
isOK = true;
break;
}
for (int x = 1; x <= X; x++) {
/*높이 확인*/
if (arr[(j + 1) - x][i] == now) {
if (possible[(j + 1) - x] == 0) {
continue;
}
else {
isOK = true;
break;
}
}
/*아닐 경우 break*/
else {
isOK = true;
break;
}
}
}
/*다음 층이 작은 경우*/
else if (next - now == -1) {
/*범위 확인*/
if (j + X >= N) {
isOK = true;
break;
}
for (int x = 1; x <= X; x++) {
/*높이 확인*/
if (arr[j + x][i] == next) {
possible[j + x] = 1;
continue;
}
else {
isOK = true;
break;
}
}
}
/*다음층과 같을 경우*/
else if (next - now == 0) {
continue;
}
/*다음 층과 2이상 차이가 날 경우*/
else {
isOK = true;
}
if (isOK == true) break;
}
if (isOK == false) {
++result;
}
}
cout << "#" << t+1 << " " << result << endl;
}
return 0;
}
반응형