[백준] 14890 경사로

14890번: 경사로

문제 확인

 

구현 문제입니다.

 

풀이

 

세로로 이동하는 경우 입력받은 배열을 전치시켜 계산하여 메모리 접근 상 더 좋은 결과를 얻을 수 있습니다.

 

ary[i-1] , ary[i]를 비교하여 3가지 경우로 나눌 수 있습니다.

1. ary[i-1] == ary[i] : 경사로를 놓을 수 있는 공간이 하나 늘어납니다. => count++
2. ary[i-1] + 1 == ary[i] : 경사로가 ary[i] 왼쪽에 필요하며 이전 경사로를 놓을 수 있는 공간이 L개 이상인 경우 이동이 가능합니다. => if(count >= L) count = 1
3. ary[i-1] - 1 == ary[i] : 경사로가 ary[i] 오른쪽에 필요하며 다음 경사로가 나오기 전까지 L개의 공간이 더 필요합니다. => if(count >= 0) count = 1 - L

2의 경우에는 이전에 공간이 1번 경우에 의하여 구할 수 있으며 3의 경우에는 경사로를 놓은 후 L개의 추가 공간이 필요하므로 마지막 가능 여부에서 count가 음수일 시 3번 경우를 만족하지 못한다고 볼 수 있습니다.

 

코드

#include <cstdio>
 
int main() {
    int n, l, res = 0;
    scanf("%d%d", &n, &l);
 
    int ary[100][100], tary[100][100];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &ary[i][j]);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            tary[j][i] = ary[i][j];
    for (int i = 0; i < n; i++) {
        int cnt = 1, j = 1;
        for (; j < n; j++) {
            if (ary[i][j - 1] == ary[i][j])    ++cnt;
            else if (ary[i][j - 1] + 1 == ary[i][j] && cnt >= l)    
                cnt = 1;
            else if (ary[i][j - 1] - 1 == ary[i][j] && cnt >= 0)    
                cnt = 1-l;
            else    break;
        }
        if (j == n && cnt>=0)
            res++;
    }
    for (int i = 0; i < n; i++) {
        int cnt = 1, j = 1;
        for (; j < n; j++) {
            if (tary[i][j - 1] == tary[i][j])    ++cnt;
            else if (tary[i][j - 1] + 1 == tary[i][j] && cnt >= l)    
                cnt = 1;
            else if (tary[i][j - 1] - 1 == tary[i][j] && cnt >= 0)    
                cnt = 1-l;
            else    break;
        }
        if (j == n && cnt >= 0)
            res++;
    }
    printf("%d\n", res);
}