[BOJ] #14830 경사로

시간 제한	메모리 제한	정답 비율
2 초	512 MB	52.919 %

 

14890번: 경사로

 

문제

해결

• 가로, 세로로 나눠서 풀었다.
• 지나가려는 길에서 flg가 마지막위치까지 false면 지나갈 수 있다. → ans를 증가시킨다.
• pre는 이전까지 보고있던 칸의 높이, cnt는 pre의 개수이다.
• diff는 pre와 다음칸의 차이를 저장하였고 1이거나 -1이어야만 한다.
  • 1이라면 다음으로 넘어갈 칸의 높이가 더 큰것이므로 현재 보고왔던 칸의 개수가 l 이상인지 확인해야하고
  • -1이라면 앞으로 볼 위치에 경사로를 두어야 하기 때문에 for문으로 l개 이상 같은 칸이 있는지 확인해줬다.
  • 이 때 이미 경사로를 놨던 곳에 또 경사로를 놓을 수 있으므로
  • 매 시각을 num이라는 변수에 저장해 놓고 경사로를 둘 때 chk[i][j]에 num으로 갱신시켜 같은 num일 때 또 경사로를 놓지 않게 판단하였다.
• 이 방법을 가로와 세로 모두 반복한 후 ans을 출력하면 정답이다.

 

코드

메모리	시간
2068 KB	ms

#include <iostream>
using namespace std;
int n, l, arr[105][105], chk[105][105], num = 1, ans;
int main() {
    scanf("%d%d", &n, &l);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            scanf("%d", &arr[i][j]);
        }
    }
 
    // 가로
    for (int i = 0; i < n; i++, num++) {
        int pre = arr[i][0], cnt = 1;
        bool flg = false;
        for (int j = 1; j < n; j++) {
            if (pre == arr[i][j]) {
                cnt++;
            }
            else {
                int diff = arr[i][j] - pre;
                if (diff == -1) {
                    int cntt = 0;
                    for (int k = j; k < j + l; k++) {
                        if (arr[i][k] != arr[i][j]) {
                            flg = true;
                            break;
                        }
                        else cntt++;
                    }
                    if (cntt >= l) {
                        for (int k = j; k < j + l; k++) {
                            chk[i][k] = num;
                        }
                        pre = arr[i][j];
                        cnt = cntt; j = j + l - 1;
                        continue;
                    }
                    else break;
                }
                else if (diff == 1) {
                    if (j > l) {
                        for (int k = j - 1; k >= j - l; k--) {
                            if (chk[i][k] == num) {
                                flg = true; break;
                            }
                        }
                    }
                    if (cnt < l || flg) {
                        flg = true;    break;
                    }                    
                }
                else {
                    flg = true; break;
                }
 
                pre = arr[i][j];
                cnt = 1;
            }
        }
        if (!flg) ans++;
    }
 
    // 세로
    for (int j = 0; j < n; j++, num++) {
        int pre = arr[0][j], cnt = 1;
        bool flg = false;
        for (int i = 1; i < n; i++) {
            if (pre == arr[i][j]) {
                cnt++;
            }
            else {
                int diff = arr[i][j] - pre;
                if (diff == -1) {
                    int cntt = 0;
                    for (int k = i; k < i + l; k++) {
                        if (arr[k][j] != arr[i][j]) {
                            flg = true;
                            break;
                        }
                        else cntt++;
                    }
                    if (cntt >= l) {
                        for (int k = i; k < i + l; k++) {
                            chk[k][j] = num;
                        }
                        pre = arr[i][j];
                        cnt = cntt; i = i + l - 1;
                        continue;
                    }
                    else break;
                }
                else if (diff == 1) {
                    if (i > l) {
                        for (int k = i - 1; k >= i - l; k--) {
                            if (chk[k][j] == num) {
                                flg = true; break;
                            }
                        }
                    }
                    if (cnt < l || flg) {
                        flg = true;
                        break;
                    }
                }
                else {
                    flg = true; break;
                }
 
                pre = arr[i][j];
                cnt = 1;
            }
        }
        if (!flg) ans++;
    }
    
    printf("%d", ans);
    return 0;
}

 

the 멋진 코드

배열의 가로줄, 세로줄을 각각 보면서 지나갈 수 있는지 알아보는 문제이다. 행 기준으로 해당 행에 있는 모든 열을 보는 것을 가로, 열 기준으로 해당 열에 있는 모든 행을 살펴보는 것이 세로라고 하면 이 방법은

배열을 [2*n][n] 크기로 선언하고

• 0 ~ n -1행까지는 원래 배열을,
• n 행부터는 원래 배열의 세로줄을 가로로 바꾼 모양으로 저장한다.

이렇게 저장해두면 항상 가로로만 탐색하면 되어 편하다.

지나갈 수 있는지 없는지 판단하기 위해서는

• c가 0 이상이면 가능
• c가 0 미만이면 불가능

이렇게 판별 가능한 이유는 왼쪽부터 오른쪽으로 차례대로 본다고 하면,

• 오른쪽이 더 큰 경우
  • 현재까지 탐색했던 왼쪽에 경사로를 l 크기만큼 두어야 함.
  • 따라서 c가 l이상인지만 판별하면 됨.
  • 그리고 c를 1로 갱신
• 왼쪽이 더 큰 경우앞으로 탐색할 오른쪽에 경사로를 l 크기만큼 두어야 함.
  • 따라서 c를 -l + 1로 갱신한다.
  • 경사로를 둘 수 있었다면 l 만큼 c가 늘어날 것이므로 c는 0 이상이고
  • 경사로를 둘 수 없었다면 c는 음수일 것이다.

메모리	시간
1112 KB	0 ms

#include <cstdio>
int main() {
    int n, l, ans = 0, i, j, c;
    short a[200][100];
    scanf("%d %d", &n, &l);
    for (i=0; i<n; i++)
        for (j=0; j<n; j++)
            scanf("%hd", &a[i][j]);
    for (i=0; i<n; i++)
        for (j=0; j<n; j++)
            a[i + n][j] = a[j][i];
    for (i=0; i<n * 2; i++) {
        c = 1;
        for (j=0; j<n - 1; j++) {
            if (a[i][j] == a[i][j + 1]) c++;
            else if (a[i][j] + 1 == a[i][j + 1] && c >= l) c = 1;
            else if (a[i][j] - 1 == a[i][j + 1] && c >= 0) c = -l + 1;
            else break;
        }
        if (j == n - 1 && c >= 0) ans++;
    }
    printf("%d", ans);
    return 0;
}