[boj] 백준 14890 경사로 (c++) - 구현

[문제]

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

14890번: 경사로

 

[풀이]

복잡하게 구현을 하다가 숏코딩 버전을 보게 되어서 해당 코드로 이해하려고 노력했다.

 

일단 행과 열을 모두 체크해야 하는데, for 문을 두번 돌릴 수도 있으나 같은 배열에 transpose 배열까지 저장해서 한 번에 처리하고 있다.

 

이 문제에서 고려해야 하는 부분은 낮은 길->높은 길, 높은 길->낮은 길에 경사로를 놓을 수 있느냐이다. 이는 연속된 타일이 L 이상인지를 체크함으로써 알 수 있다. 따라서 변수 c에 연속된 타일의 개수를 계속 갱신해준다.

높이가 같으면 단순히 c를 증가시켜주고, 낮은 길->높은 길로 갈 때는 지금까지 센 c (연속된 타일의 개수) 값이 L 이상이어야 경사로를 놓을 수 있다. 경사로를 놓을 수 있다면 다시 c값을 1로 갱신해준다.

문제는 높은 길->낮은 길로 갈 때이다. 이때는 경사로를 놓은 자리를 낮은 길에 반영해주어야 한다. 현재의 c 값에 경사로의 길이 L 만큼을 더한 c+l 값이 경사로 옆에 놓인 타일의 위치에 해당하는 c 값이 된다. 따라서 c + l = 1이므로 c = -1 + 1로 갱신해준다.

 

for 문을 끝까지 돌아서 j == n-1 이 되고, 이때의 c 값이 0 이상이 되어야 지나갈 수 있는 길이다.

 

[코드]

 

#include <iostream>
#include <algorithm>
#include <string>
#include <queue>
#define INF 987654321

using namespace std;

int n, l;
int board[200][100];

int main(){
    ios::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 >> board[i][j];
        }
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            board[i+n][j] = board[j][i]; //트랜스포즈 행렬 저장 -> 행과 열을 한번에 확인
        }
    }

    int i, j, c, ans = 0; //c 조건을 확인하여 연속된 타일이 l 이상인지 체크함.
    for(i=0; i<2*n; i++){
        c = 1;
        for(j=0; j<n-1; j++){
            if(board[i][j] == board[i][j+1]) c++; //같은 높이인 경우 연속된 타일의 개수 증가
            else if(board[i][j]+1 == board[i][j+1] && c >= l){ //낮은->높은인 경우 연속된 타일이 l 이상이어야 경사로를 놓을 수 있음
                c = 1;//연속된 타일 수 갱신
            }
            else if(board[i][j] == board[i][j+1] + 1 && c >= 0) {
                //높은->낮은인 경우 경사로가 놓인 자리를 반영해줌 -> c+l 자리가 1로 다시 시작하도록
                c = -l + 1;
            }
            else break;
        }

        if(j == n-1 && c >= 0){
            ans++;
        }
    }

    cout << ans;
}