[백준] 14890. 경사로

[문제]

 

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

14890번: 경사로

 

시뮬레이션 문제로 

 

높이가 같은 경우 -> 다음 index로 넘어감

높이가 다른 경우 -> 차이가 1보다 큰지 확인 

 

행과 열을 올렸다 하나의 일차원 배열에 옮겨서 확인 

(어차피 행과 열 확인하는 방법은 같으니까)

 

 

[풀이]

 

1. check 함수

 

 

다음 인덱스랑 높이 비교  

높이차가 같은 경우 다음 인덱스로 넘어감. 

높이차가 1보다 크다면 check 함수 바로 return.

높이차가 1인 경우 comp 함수 호출.

 

0부터 N-1까지 확인 

N-1까지 도달한 경우 cnt (지나갈 수 있는 길의 갯수 ) 1 증가 

 

 

2. comp 함수

 

경사로를 추가할 수 있는지 확인

 

추가할 부분의 길이가 경사로의 길이보다 짧으면 안된다.

 

 

 

[그림 1]

 

조심해야될 부분은 위의 [그림 1]과 같이 경우에는 경사로를 무조건 2개 추가하는 경우부터 가능하다. 

(코드 25번째 line에서 처리 ) 

 

 

 

[ 그림 2]

또 [그림 2]의 경우 return tmp+1을 해줬는데 

 

 

4 4 3 3 3 2 2 , 경사로 : 3 

 

위의 경우 통과하지 못하는 케이스인데 tmp+1 (arr[5])부터 체크하므로 통과하게 된다.

=> 따라서 return tmp로 바꿔서 arr[4]부터 체크하도록 해줬다. (코드 24번째 line) 

(이 부분 놓쳐서 계속 틀렸다.) 

 

 

[코드]

 

시간 : 0ms

#include <iostream>
#define MAX 100

using namespace std;

int N,L;
int map[MAX][MAX]={0,};
int cnt =0;

int comp(int pos , int arr[100])
{
    int tmp;
    
    if ( arr[pos] > arr[pos+1]){
        tmp = pos+1;
        int len=1;
        while(tmp < N-1){
            if(arr[tmp] != arr[tmp+1])  break;
            len++;
            tmp++;
        }
        if(len < L )    return 0;
        else if(tmp == N-1)  return N-1;
        else if((arr[pos]-arr[tmp+1])== 2)   return tmp;
        else if((len/L) >= 2 &&  (arr[pos] == arr[tmp+1]))  return tmp+1;
        else  return 0;
    }
    else {
        tmp = pos;
        int len =1;
        while(tmp > 0){
            if(arr[tmp] != arr[tmp-1])  break;
            len++;
            tmp--;
        }
        if(len < L )    return 0;
        else    return pos+1;
    }
}

void check(int idx,bool flag)
{
    
    int arr[N];
    
    if(flag)    for(int i=0;i<N;i++)    arr[i] = map[i][idx];
    else    for(int i=0;i<N;i++)    arr[i] = map[idx][i];
    
    int pos =0;
    
    while(pos < N-1 ){
        
        int diff = arr[pos] - arr[pos+1];
        
        if( diff == 0)  pos++;
        else if(diff==1 || diff == -1){
            pos = comp(pos , arr);
            if(pos ==0) return ;
        }
        else    return ;
    }
    
    cnt++;
}

int main(void)
{
    cin >> N >> L;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++)    cin >> map[i][j];
    }
    
    for(int i=0;i<N;i++){
        check(i,0); // row
        check(i,1); // col
    }
    
    cout << cnt;
    
    return 0;
}

 

조언, 질문 환영입니다!

댓글 남겨주세요~