[SWEA][모의 SW 역량테스트][C++] 4014 활주로 건설

문제

SWEA 모의 SW 역량 테스트 - 4014 활주로 건설

SW Expert Academy

 

---

문제 풀이

접근 방식

설치 가능한 경사로를 찾기 위해 가로 방향과 세로 방향으로 각각 탐색해주어야 한다.

그래서 편의를 위해 map 벡터를 2N×N 크기로 만들어서 가로 방향과 세로 방향으로 넣어주었다.

이렇게 하면 나중에 이중 for문을 두번 돌리지 않아도 된다.

vector<vector<int>> map(N * 2, vector<int>(N));
for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
		cin >> map[i][j];
		map[j + N][i] = map[i][j];
	}
}

 

활주로 건설이 가능한 길인지는 3가지 조건으로 판단해 볼 수 있다.

 

1. 같은 높이인 경우

2. 1칸 더 높으나, 경사로를 설치할 수 있는 경우

3. 1칸 더 낮으나, 경사로를 설치할 수 있는 경우

 

2번의 경우는, 지금까지 탐색한 같은 높이의 칸의 수가 X(경사로의 가로 길이)보다 크거나 같은 경우이다.

이를 쉽게 판단하기 위해 1번의 경우일 때, count 변수를 1씩 증가시켜주었다.

 

3번의 경우는, 앞으로 가야할 칸과 같은 높이의 칸수가 X만큼 되는 경우이다.

이는 X 크기만큼 for문을 돌려 확인해주었다.

 

위의 조건들을 만족하지 못하면 check 변수를 false로 바꾸고 반복문을 나가도록 설정해주었고,

모두 만족하여 check가 true인 경우에는 answer++를 실행해주어 최종 답을 구하였다.

 

---

풀이 코드 - C++

#include <iostream>
#include <vector>

using namespace std;

int main(int argc, char **argv)
{
	int test_case;
	int T, N, X;

	// freopen("input.txt", "r", stdin);
	cin >> T;
	for (test_case = 1; test_case <= T; ++test_case) {
		cin >> N >> X;
		vector<vector<int>> map(N * 2, vector<int>(N));
		for (int i = 0; i < N; i++)	{
			for (int j = 0; j < N; j++)	{
				cin >> map[i][j];
				map[j + N][i] = map[i][j];
			}
		}
		int answer = 0;
		for (int i = 0; i < N * 2; i++)	{
			int now = map[i][0];
			int count = 1;
			bool check = true;
			for (int j = 1; j < N; j++)	{
				if (map[i][j] == now) { // 같은 높이인 경우
					count++;
					continue;
				}
				if (map[i][j] - now == 1) { // 1칸 더 높은 경우
					if (count >= X)	{
						now = map[i][j];
						count = 1;
						continue;
					}
					check = false;
					break;
				}
				if (map[i][j] - now == -1) { // 1칸 더 낮은 경우
					now = map[i][j];
					count = 1;
					for (int k = 1; k < X; k++) {
						j++;
						if (j < N && map[i][j] == now)
							count++;
					}
					if (count == X) {
						count = 0;
						continue;
					}
					check = false;
					break;
				}
				check = false;
				break;
			}
			if (check)
				answer++;
		}
		cout << "#" << test_case << " " << answer << endl;
	}
	return 0;
}

실행 결과