[백준] 14890 경사로 (C++)

백준 14890 경사로

1. 문제

문제 링크

2. 접근법

[ 문제 접근 ]

 

경사로를 놓을 수 있는 방법은 아래 네 가지 조건을 판단하면 된다.

 

1. 두 땅의 높이가 같은 경우

- 높이가 같은 땅의 수(cntRoad)를 하나씩 증가시킨다.

2. 앞의 땅의 높이가 1만큼 더 높은 경우

- 뒤의 땅부터 경사로의 길이만큼 땅이 평평한지 확인해준다. (calcLen 함수 사용)

3. 뒤의 땅의 높이가 1만큼 더 높은 경우

- 앞의 땅, 즉 높이가 같은 땅의 수(cntRoad)가 경사로의 길이만큼 평평한지 확인해준다. 

4. 두 땅의 높이 차가 2보다 큰 경우

- 더 이상 확인할 필요가 없으므로 break 시킨다.

 

위 조건에 따라 구현한 코드는 아래와 같다.

3. 코드

#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int n, l;
int map[101][101];
int map2[101][101];
//앞의 땅의 높이가 1만큼 더 높은 경우 
//경사로의 길이만큼 땅이 평평한지 확인
bool calcLen(int m[101][101], int r, int c)
{
    int init = m[r][c + 1];
    for (int j = c + 1; j < c + 1 + l; ++j)
    {
        if (m[r][j] != init)
            return false;
    }
    return true;
}
int make_road(int m[101][101])
{
    int ans = 0;
    for (int i = 0; i < n; ++i)
    {
        bool makeRoad = true;
        int cntRoad = 1;

        for (int j = 0; j < n - 1; ++j)
        {
            //땅의 높이가 같은 경우 
            if (m[i][j] == m[i][j + 1])
                cntRoad++;
            //앞의 땅의 높이가 1만큼 더 높은 경우
            else if (m[i][j] == m[i][j + 1] + 1)
            {
                //경사로의 길이만큼 땅이 평평하다면
                //j와 cntRoad 초기화
                if (calcLen(m, i, j))
                {
                    j = j + l - 1;
                    cntRoad = 0;
                }
                else
                {
                    makeRoad = false;
                    break;
                }
            }
            //뒤의 땅의 높이가 1만큼 더 높은 경우
            else if (m[i][j] + 1 == m[i][j + 1])
            {
                //연결된 땅의 길이가 경사로 보다 크거나 같은 경우에
                //경사로 설치 가능
                if (cntRoad >= l)
                    cntRoad = 1;
                else
                {
                    makeRoad = false;
                    break;
                }
            }
            //높이 차이가 2이상인 경우 
            else if (abs(m[i][j] - m[i][j + 1]) >= 2)
            {
                makeRoad = false;
                break;
            }
        }
        //땅을 만들 수 있다면 ans++해준다.
        if (makeRoad)
            ans++;
    }
   return ans; 
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> l;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            cin >> map[i][j];
            map2[j][i] = map[i][j];
        }
    }

    int a = make_road(map);
    int b = make_road(map2);

    cout << a + b << "\n";
    return 0;
}

4. 시간 복잡도

n*n-1번 수행한다.

5. 결과