[삼성SW테스트] 백준 14890번 - 경사로 (정답률 52%)

https://www.acmicpc.net/problem/14890

14890번: 경사로

삼성 SW테스트 마지막 기출문제 업로드다. (유형: 시뮬레이션)

이문제를 끝으로 총 28문제의 삼성SW기출문제 업로드가 끝난다.

이제는 SWEA 문제들을 업로드할 예정.

 

경사로를 놓을 수 있는 1. 조건(경사로 설치여부, 높이 차)과 2. 범위(경사로 길이와 지도의 크기)를 잘 따져 시뮬레이션을 구현하면 된다.

아래는 전체 소스코드 (C++, 0ms/2초)

#include <iostream>
#include <vector>
#include <algorithm>
#define maxN 100
using namespace std;
int N, L;
int map[maxN][maxN];
int answer = 0;
bool CanPass(vector<int>& road){
    vector<bool> check(N, false);
    for (int c = 1; c < N; c++){
        int diff = abs(road[c] - road[c - 1]);
        if (diff > 1) return false;
        else{
            if (road[c] - road[c - 1] == 1){
                if (c - L < 0) return false;
                for (int j = 1; j <= L; j++){
                    if (check[c - j]) return false; // 놓은 곳이면 못가는 길임.
                    if (road[c - 1] != road[c - j]) return false; // 길 놓는 공간에서 높이차 있다면 못가는길임.
                    check[c - j] = true;
                }
            }
            else if (road[c] - road[c - 1] == -1){
                if (c + L - 1 >= N) return false;
                for (int j = 1; j <= L; j++){
                    if (check[c + j - 1]) return false;
                    if (road[c] != road[c + j -1]) return false;
                    check[c + j - 1] = true;
                }
            }
        }
    }
    return true;
}
 
int main(){
    cin >> N >> L;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> map[i][j];
    for (int i = 0; i < N; i++){
        vector<int> road;
        for (int j = 0; j < N; j++){
            road.push_back(map[i][j]);
        }
        if (CanPass(road)) answer++;
        road.clear();
        for (int j = 0; j < N; j++){
            road.push_back(map[j][i]);
        }
        if (CanPass(road)) answer++;
    }
    cout << answer << '\n';
    return 0;
}