문제

문제 링크

해설

조건이 많아서 까다로운 문제입니다. 최대한 자신만의 언어로 조건을 단순화 하는 것이 중요합니다.

• 저는 이렇게 단순화했습니다.

• " 길이 L, 높이 1 경사로를 평탄한 면 위에 중복없이 놓아서 지나갈 수 있는 길 카운트"

• 이제 세부조건은 다음과 같습니다.
  

  • 가로 길에서는
    • 오른쪽에 내려가는 경사로를 놓는 경우: 길이 L 경사로를 오른쪽에 놓을 수 있는 공간이 있는지 확인해야 합니다.
    • 오른쪽에 올라가는 경사로를 놓은 경우: 길이 L 경사로를 놓을 공간이 없거나, 왼쪽에 내려가는 경사로가 이미 놓여있는지 확인해야 합니다.
  • 세로 길에서는
    • 아래에 내려가는 경사로를 놓는 경우: 길이 L 경사로를 놓을 공간이 있는지 확인해야 합니다.
    • 아래에 올라가는 경사로를 놓는 경우: 공간이 없거나, 위쪽에 올라가는 경사로가 이미 놓여있는지 확인해야 합니다.

• 결국 아래와 같은 구조가 4가지 경우에 대해 반복됩니다.

bool is_valid = true;
bool road_exist[100];

for (int y = 0; y < N - 1; ++y) {
	int diff = road[y + 1][x]  - road[y][x];    // 인접한 칸 높이 차이
	if (diff == 1) {    // 올라가는 경사로를 놓습니다.
		if ( 경사로 놓을 수 없는지 ) is_valid = false;
		else {
			for () {
				...
				road_exist[i] = true;
			}
		}
	}
	else if (diff == -1) {    // 내려가는 경사로를 놓습니다.
		if ( 경사로 놓을 수 없는지 ) is_valid = false;
		else {
			for () {
				...
				road_exist[i] = true;
			}
		}
	}
}

코드

#include <iostream>
#include <array>
#include <bitset>
using namespace std;

int N, L;
array<array<int, 100>, 100> road;

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    
    cin >> N >> L;
    for (int y = 0; y < N; ++y)
        for (int x = 0; x < N; ++x)
            cin >> road[y][x];

    int answer = 0;
    // Step #1. 가로줄 N개를 검사합니다.
    for (int y = 0; y < N; ++y) {
        
        bool is_valid = true;
        bitset<100> road_exist;
        
        for (int x = 0; x < N - 1; ++x) {
            int diff = road[y][x + 1] - road[y][x];
            if (diff != 0) {
                // Case #1. 오른쪽에 (올라가는) 경사로를 놓는 경우
                if (diff == 1) {
                    /* 왼쪽에 (올라가는) 경사로를 놓을 수 없는 경우
                    또는, 이미 왼쪽에 (내려가는) 경사로가 놓여있는 경우 */
                    if (x < L - 1 || road_exist.test(x)) is_valid = false;
                    else {
                        for (int i = x - 1; i > x - L; --i) {
                            if (road_exist.test(i) || road[y][i] != road[y][x]) {
                                is_valid = false;
                                break;
                            }
                            road_exist.set(i);
                        }
                    }
                    if (is_valid == false) break;
                }
                // Case #2. 오른쪽에 (내려가는) 경사로를 놓는 경우
                else if (diff == -1) {
                    // 오른쪽에 (내려가는) 경사로를 놓을 수 없는 경우
                    if (x + L >= N) is_valid = false;
                    else {
                        for (int i = x + 1, h = road[y][x] - 1; i <= x + L; ++i) {
                            if (road_exist.test(i) || road[y][i] != h) {
                                is_valid = false;
                                break;
                            }
                            road_exist.set(i);
                        }
                    }
                    if (is_valid == false) break;
                    x += (L - 1);   // 경사로를 놓은 부분은 생략합니다.
                }
                // Case #3. 경사로를 놓을 수 없는 경우
                else {
                    is_valid = false;
                    break;
                }
            }
        }
        // 정상적으로 지나갈 수 있는 길일 때 카운트 합니다.
        if (is_valid == true) answer++;
    }

    // Step #2. 세로줄 N개를 검사합니다.
    for (int x = 0; x < N; ++x) {

        bool is_valid = true;
        bitset<100> road_exist;

        for (int y = 0; y < N - 1; ++y) {
            int diff = road[y + 1][x] - road[y][x];
            if (diff != 0) {
                // Case #4. 아래에 (올라가는) 경사로를 놓는 경우
                if (diff == 1) {
                    /* 위쪽에 (아래로 내려가는) 경사로를 놓을 수 없는 경우
                    또는 위쪽에 이미 경사로가 놓여있는 경우*/
                    if (y < L - 1 || road_exist.test(y)) is_valid = false;
                    else {
                        for (int i = y - 1; i > y - L; --i) {
                            if (road_exist.test(i) || road[i][x] != road[y][x]) {
                                is_valid = false;
                                break;
                            }
                            road_exist.set(i);
                        }
                        if (is_valid == false) break;
                    }
                }
                // Case #5. 아래에 (내려가는) 경사로를 놓는 경우
                else if (diff == -1) {
                    // 아래에 공간이 없어서 경사로를 놓을 수 없는 경우
                    if (y + L >= N) is_valid = false;
                    else {
                        for (int i = y + 1, h = road[y][x] - 1; i <= y + L; ++i) {
                            if (road_exist.test(i) || road[i][x] != h) {
                                is_valid = false;
                                break;
                            }
                            road_exist.set(i);
                        }
                        if (is_valid == false) break;
                        y += (L - 1);       // 경사로를 놓은 부분은 생략합니다.
                    }
                }
                // Case #6. 아래에 경사로를 놓을 수 없는 경우
                else {
                    is_valid = false;
                    break;
                }
            }
        }
        // 정상적으로 지나갈 수 있는 길일 때 카운트 합니다.
        if (is_valid == true) answer++;
    }
    cout << answer << '\n';
}

소스코드 링크

결과