[백준 14890] 경사로 C++

14890번: 경사로

시뮬레이션

삼성 SW 기출

---

1. 문제 해결 아이디어

 

구슬 탈출 2 문제를 풀다가 코드가 너무 길어지고.. 구현이 더러워져서 도망치듯 풀게 된 문제다.

도망쳐왔지만 이 문제도 절대 만만하진 않았다.

 

분명 문제에는 경사로는 서로 겹치면 안 된다고 적혀있어서 가로와 세로 경사로끼리도 겹치면 안되는줄 알았다.

그런데 알보고니 가로 경사로와 세로 경사로는 서로 영향을 주지 않기 때문에 문제가 더 쉬워졌다!

가로길 + 세로길 해주면 답이 나오게 되었다!

문제 설명이 부실한듯해서 시간을 좀 잡아먹었다. 나만 이해 못한 걸 수도ㅠ

 

 

문제를 이해하고 앞으로 구현할 풀이를 주석으로 길게 써봤다.

 

같은 높이가 연속해서 나타나면 몇 개 나타났는지 기록,
높이가 1 증가하고 지금까지 지나온 길이가 L 이상이면 경사로 가능
높이가 1 감소하면 그때부터 동일한 높이가 몇 개 나타나는지 기록,
연속으로 L개 나타난 순간 경사로 가능, 새로 카운팅
아직 경사로 가능하다고 판단하기 전에 높이가 달라지면 해당 행/열은 길 안됨, 다음 행/열로 넘어간다

 

처음 적었던 주석 그대로 구현하려고 했다.

---

2. 코드

#include <iostream>
 
using namespace std;
 
int Map[101][101];
int N, L;
 
void input(){
    cin >> N >> L;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> Map[i][j];
        }
    }
}
 
int row_road(){
    int road_count = 0;
    int bheight, cnt;
    bool downslide;
    
    for(int r = 0; r < N; r++){
        bheight = Map[r][0];
        cnt = 1;
        downslide = false;
        for(int c = 1; c < N; c++){
            if(Map[r][c] == bheight) cnt++;
            else if(bheight + 1 == Map[r][c]){
                if(cnt >= L){
                    cnt = 1;
                    bheight = Map[r][c];
                }
                else{
                    cnt = -1;
                    break;
                }
            }
            else if(Map[r][c] + 1 == bheight){
                if(downslide){
                    break;
                }
                downslide = true;
                bheight = Map[r][c];
                cnt = 1;
            }
            else{
                cnt = -1;
                break;
            }
            if(downslide && cnt >= L){
                cnt = 0;
                downslide = false;
            }
        }
        if(!downslide && cnt >= 0) road_count++;
    }
    
    return road_count;
}
 
int col_road(){
    int road_count = 0;
    int bheight, cnt;
    bool downslide = false;
    
    for(int c = 0; c < N; c++){
        bheight = Map[0][c];
        cnt = 1;
        downslide = false;
        for(int r = 1; r < N; r++){
            if(Map[r][c] == bheight) cnt++;
            else if(bheight + 1 == Map[r][c]){
                if(cnt >= L){
                    cnt = 1;
                    bheight = Map[r][c];
                }
                else{
                    cnt = -1;
                    break;
                }
            }
            else if(Map[r][c] + 1 == bheight){
                if(downslide) break;
                downslide = true;
                bheight = Map[r][c];
                cnt = 1;
            }
            else{
                cnt = -1;
                break;
            }
            if(downslide && cnt >= L){
                cnt = 0;
                downslide = false;
            }
        }
        
        if(!downslide && cnt >= 0) road_count++;
    }
    
    return road_count;
}
 
void solve(){
    // 같은 높이가 연속해서 나타나면 몇 개 나타났는지 기록,
    // 높이가 1증가하고 지금까지 지나온 길이가 L이상이면 경사로 가능
    // 높이가 1감소하면 그때부터 동일한 높이가 몇 개 나타나는지 기록,
    // 연속으로 L개 나타난 순간 경사로 가능, 새로 카운팅
    // 아직 경사로 가능하다고 판단하기 전에 높이가 달라지면 해당 행/열은 길 안됨, 다음 행/열로 넘어간다
    
    cout << row_road() + col_road();
}
 
 
int main(){
    ios_base::sync_with_stdio(false); cin.tie(0);
    
    input();
    solve();
    
    return 0;
}
 

 

최근에 구현문제를 거의 안풀어서 그런지 참 오래걸렸다.. 거의 2시간?ㅠㅠ

그리고 디버깅 한다고 세부적인 코드 조정하니 1시간정도..

 

구현 문제 자주 풀자