[Algorithm] 삼성전자 코딩테스트 - 경사로(c++)

행과 열을 기준으로 각각 구현하면 된다.

행을 기준으로 설명을 해보겠다.

1) 열마다 탐색하며 높이의 차이가 1만큼 나는 곳에 L길이의 경사로를 설치할 수 있는지 확인한다.

2) 경사로를 설치할 수 없으면 총 길의 개수에서 1만큼 빼준다.

 

*포인트는!! 양 방향으로 탐색해야한다는 것이다*

즉, 한 쪽 방향으로 탐색하고 반대쪽으로도 탐색해야 경사로를 설치할 수 있는 지 없는지 정확하게 파악할 수 있다.

_____|------ 이런 모양도 있는 반면, ----|______이렇게 내려가는 부분도 존재하기 때문이다.

 

 

코드 첨부

// 경사로
#include <iostream>
#include <cstdlib>
#include <cmath>
using namespace std;
 
int ans, n, l;
int area[101][101] = {0, };
 
void check()
{
    // 행 기준
    for(int i=0; i<n; i++){
        int visited[101] = {0, };
        bool check = true;
        for(int j=0; j<n-1; j++){
            // 내려감
            if((area[i][j]-area[i][j+1])==1){
                if((j+1+l)>n){
                    check = false;
                    break;
                }
 
                int num = 0;
                for(int k=j+1; k<j+1+l; k++){
                    if(area[i][j+1]==area[i][k] && !visited[k]){
                        visited[k] = 1;
                        num++;
                    }
                }
 
                if(num!=l){
                    check = false;
                }
            }else if((area[i][j]-area[i][j+1])==-1){ // 올라감
                if((j+1-l)<0){
                    check = false;
                    break;
                }
 
                int num = 0;
                for(int k=j+1-l; k<j+1; k++){
                    if(area[i][j]==area[i][k] && !visited[k]){
                        visited[k] = 1;
                        num++;
                    }
                }
 
                if(num!=l){
                    check = false;
                }
            }else if(abs(area[i][j]-area[i][j+1])>=2){
                check = false;
            }
        }
        if(check==false){
            ans--;
        }
    }
 
    // 열 기준
    for(int i=0; i<n; i++){
        int visited[101] = {0, };
        bool check = true;
        for(int j=0; j<n-1; j++){
            if((area[j][i]-area[j+1][i])==1){
                if((j+1+l)>n){
                    check = false;
                    break;
                }
 
                int num = 0;
                for(int k=j+1; k<j+1+l; k++){
                    if(area[j+1][i]==area[k][i] && !visited[k]){
                        visited[k] = 1;
                        num++;
                    }
                }
 
                if(num!=l){
                    check = false;
                }
            }else if((area[j][i]-area[j+1][i])==-1){
                if((j+1-l)<0){
                    check = false;
                    break;
                }
 
                int num = 0;
                for(int k=j+1-l; k<j+1; k++){
                    if(area[j][i]==area[k][i] && !visited[k]){
                        visited[k] = 1;
                        num++;
                    }
                }
 
                if(num!=l){
                    check = false;
                }
            }else if(abs(area[j][i]-area[j+1][i])>=2){
                check = false;
            }
        }
        if(check==false){
            ans--;
        }
    }
}
 
int main()
{
    cin>>n>>l;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin>>area[i][j];
        }
    }
 
    ans = 2*n;
 
    check();
    cout<<ans<<"\n";
 
    return 0;
}

 

문제 첨부

www.acmicpc.net/problem/14890

14890번: 경사로