[C++/백준] 14890번: 경사로

문제 링크

14890번: 경사로

 

풀이

구현 문제

1. 길은 세로, 가로로 있기 때문에 입력받으면서 arr1에는 가로, arr2에는 세로를 넣는다.
2. 한 줄씩 길을 체크할 것이다.
   1. 먼저 현재 길인 i와 다음 길인 i+1을 비교해간다.
   2. 경사가 같을 때는 continue
   3. 1 올라가는 경우 (arr[i]+1 == arr[i+1])에는 앞에 i부터 l개를 확인하며 범위를 벗어나거나, 경사의 차이가 나서 경사로를 못놓거나, 이미 지어진 경우에는 return 0을 한다. slope[i] = 1을 해서 경사로를 넣는 것을 빼먹지 않는다.
   4. 1 내려가는 경우 (arr[i]-1 == arr[i+1])에는 뒤에 i+1부터 l개를 확인하며 3번과 같이 return하고 경사로를 놓는다.
   5. 1,2,3번 경우가 아니라면 경사의 차이가 2 이상이라는 것이므로 return 0한다.
   6. 앞에서 return 되지 않았다면 길이 된다는 것이므로 1을 return 한다.
3. answer에 앞에 return 값을 더해주어 출력한다.

 

코드

#include <iostream>
#include <vector>
using namespace std;

int check(int l, vector<int> &arr)
{
    // 경사로가 있는지 확인
    vector<int> slope(arr.size(),0); 
    for (int i = 0; i < arr.size() - 1; i++)
    {
        if (arr[i] == arr[i + 1]) continue;
        else if (arr[i] + 1 == arr[i + 1]) // 경사가 올라갈 때
        {
            // 앞에꺼 확인
            for (int j = i; j > i - l; j--)
            {
                if (j < 0) return 0; // 범위 밖이면
                else if (arr[j] != arr[i] || slope[j] == 1) // 경사로를 지을 수 없거나, 이미 지어진 경우
                {
                    return 0;
                }
                slope[j] = 1;
            }
        }
        else if (arr[i] - 1 == arr[i + 1]) // 경사가 내려갈 때
        {
            // 뒤에꺼 확인
            for (int j = i + 1; j <= i + l; j++)
            {
                if (j >= arr.size()) return 0; // 범위 밖이면
                else if (arr[j] != arr[i] - 1 || slope[j] == 1) // 경사로를 지을 수 없거나, 이미 지어진 경우
                {
                    return 0;
                }
                slope[j] = 1;
            }
        }
        else // 경사가 2 이상일 때
        {
            return 0;
        }
    }
    return 1;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, l;
    cin >> n >> l;

    vector<vector<int>> arr1(n, vector<int>(n));
    vector<vector<int>> arr2(n, vector<int>(n));
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            int tmp;
            cin >> tmp;
            arr1[i][j] = tmp;
            arr2[j][i] = tmp;
        }
    }

    int answer = 0;
    for (int i = 0; i < n; i++)
    {
        answer += check(l, arr1[i]);
        answer += check(l, arr2[i]);
    }

    cout << answer;
}