[C++,구현] 백준 14890번 경사로 문제풀이

문제 링크

백준 14890번 경사로

14890번: 경사로

 

오늘 종일 고민한 문제이다. 다른일이랑 같이 하려니 정신이 분산되어 머리만 더 복잡해지는거 같다ㅜㅜ

앞으로 조용한 곳에서 단시간 집중하고 해치워야겠다.

아이디어가 생각 나지 않아 구현이 어려웠다. 찾아보니 핵심아이디어는 현재까지 연속된 높이의 계단수를 세는것!

아이디어를 얻어 완성한 후 한번 WA를 받았는데 조건에 계단의 높이가 1일 차이일때만 경사로를 설치할 수 있다는 조건이 있었다. 문제도 제대로 읽자..ㅜ

 

#include <cstdio>
#include <cmath> 
int n, L, ans = 0, t1 = 0, t2 = 0;
int map[100][100];
main(){
    scanf("%d%d", &n, &L);
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            scanf("%d", &map[i][j]);
    
    //행 검사
    for (int i = 0; i < n; i++){
        int cnt = 1;//현재까지의 연속된 같은 높이의 계단 수
        int f1 = 1; //길을 만들수 있는지의 플레그
        for (int j = 0; j + 1 < n; j++){
            if (map[i][j] == map[i][j + 1]) cnt++; //높이가 같다면 연속된 같은 높이 계단 수 증가
            else if (map[i][j] - map[i][j + 1] == -1)//높이가 높아질 경우 
            { 
                if (cnt >= L) //지금까지의 연속된 계단수가 경사로를 놓을 수 있을지 없을지를 결정
                    cnt = 1; // 놓을 수 있다면 다시 연속된 계단수는 1
                else f1 = 0; //놓을 수 없다면 길을 만들 수 없다
            }
            else if (map[i][j] - map[i][j + 1] == 1)//높이가 낮아질 경우
            { 
                if (cnt < 0) f1 = 0; //같은 높이수가 음수 즉,필요가 더 많은데 또 경사로가 필요하는 경우는 불가한 경우이므로 플레그 표시
                else cnt = -(L - 1); // 앞으로 L-1개의 같은 높이수가 필요하므로 
            }
            else f1 = 0;//위의 사례를 제외하면 모두 불가
        }
        if (cnt >= 0 && f1){/*printf("\n %d\n",i);*/t1++; } //이미 불가한지(f1)와 필요한 같은 높이의 계단수가 충족됬는지 확인
    }
    //열 검사 
    for (int i = 0; i < n; i++){
        int cnt = 1;
        int f2 = 1; 
        for (int j = 0; j + 1 < n; j++){
            if (map[j][i] == map[j + 1][i]) cnt++;
            else if (map[j][i] - map[j + 1][i] == -1)
            { 
                if (cnt >= L) cnt = 1;
                else f2 = 0; 
            }
            else if (map[j][i] - map[j + 1][i] == 1)
            { 
                if (cnt < 0) f2 = 0; 
                else cnt = -(L - 1); 
            }
            else f2 = 0;
        }
        if (cnt >= 0 && f2){/*printf("\n %d\n",i);*/t2++; }
 
    }
    printf("%d", t1 + t2);
}