[C++] 백준 - #14890 경사로

문제 링크

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

14890번: 경사로

풀이

구현 문제인데 왜 난 못할까 후;

내가 접근할 때는 다른 블로그들과 다르게 경사로를 놓은 것을 일일이 기록해주었다.

그래서 경사로를 놨는지 체크하는 배열이 필요했고, 입력받은 배열도 +1을 해주면서 경사로를 설치하는 것을 표시해주었다.

그리고 나서 마지막에 이어져있는지 확인하는 코드를 짰다.

가뜩이나 구현 잘 못하는데 다른 분들은 다 나처럼 풀지 않으니까 참고를 못하고 도움을 받을 길이 없어서 이 방법은 그냥 포기했다..

 

그래서 다른 분들 풀이를 보고 이해하면서 풀기 시작했다.

경사로 놨는지 체크하거나 경사로를 실제로 놓는 것을 배열에 구현을 하지 않아도 된다.

배열을 처음부터 보면서 검사해야할 것들이 있는데,

1. 옆에 있는 칸과 높이가 같을 때 => 카운트하면서 계속 보기
2. 옆에 있는 칸과 높이가 1차이가 나는데, 앞에 있는 칸이 더 높을 때 => 뒤에 경사로를 놓을 수 있는지 검사하고, 놓을 수 있다면 놓기
3. 옆에 있는 칸과 높이가 1차이 나는데, 뒤에 있는 칸이 더 높을 때 => 앞에 봤던 것들을 검사 (카운트 했던 것이 경사로 길이인 L보다 크거나 같으면 경사로를 놓았음을 표시
4. 높이 차가 2 이상 날 때 => 즉시 종료

이렇게 간단한(?) 문제였다.

뭐든 내 머릿속에서 미리 정리하는 게 진짜진짜 중요한 것 같다.

 

처음엔 다른 분이 짠 알고리즘을 이해하고

그 다음엔 코드로 옮겼는데, 여기서 모르는 부분은 참고해가며 짰다.

그리고나서는 안보고 코드를 짰다. 

안보고 코드를 짜니까 기존에 그냥 아하~ 하고 넘어갔던 부분에서 걸리면서 내가 부족한 부분을 알 수 있었다.

//
// Created by ღ 𝚂𝚑𝚒𝚗𝚎 𝚈𝚎𝚘𝚗 ღ on 2022/07/28.
//

#include <iostream>
using namespace std;
int N, L;
int map1[101][101];
int map2[101][101];

bool canPut(int road[][101], int x, int y) {
    int standard = road[x][y+1];
    for(int i=y+1; i<y+1+L; i++){
        if(standard != road[x][i])
            return false;
    }
    return true;
}

int sol(int road[][101]) {
    int ans = 0;
    for(int i=0; i<N; i++){
        int count = 1;
        bool canMake = true;
        for(int j=0; j<N-1; j++){
            if(road[i][j] == road[i][j+1]) {
                count++;
            }
            else if(road[i][j] == road[i][j+1] +1) { //앞에꺼가 1 더 높을 때
                if(canPut(road, i, j)) { //뒤에다가 경사로를 놓을 수 있는지 확인,
                    j = j+L-1; //놓을 수 있으면 j를 이동시켜야 함
                    count = 0; //경사로를 이미 놨으니까 0을 만들어 줘야 함. (길이 L만큼만 경사로 놓기)
                }
                else{
                    canMake = false; //놓을 수 없으면 canMake변수를 false로 만들어주고 탈출
                    break;
                }
            }
            else if(road[i][j]+1 == road[i][j+1]) { //뒤에꺼가 1 더 높을 때
                if(count >= L) { //경사로 놓을 수 있는 경우
                    count = 1; //이건 이어서 진행하는 거니까 1로 만듦 (최초에 1에서 시작한 것처럼 -왜냐면 인덱스가 0->1이 하나임)
                }
                else{
                    canMake = false;
                    break;
                }
            }
            else if(abs(road[i][j] - road[i][j+1]) >= 2) {
                canMake = false;
                break;
            }
        }
        if(canMake)
            ans++;
    }
    return ans;
}

int main() {
    cin>>N>>L;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++) {
            int tmp;
            cin>>tmp;
            map1[i][j] = tmp;
            map2[j][i] = tmp;
        }
    }
    cout<<sol(map1) + sol(map2) <<"\n";

}

코드를 짜면서 헷갈렸던 부분은,

앞의 블럭이 한 칸 더 높을 때는 count 변수를 0으로 초기화하는데

뒤의 블럭이 더 높을 때는 count 변수를 1로 초기화하는 점이다.

 

이 부분에 대해서 고민해본 결과, 

앞 블럭이 한 칸 더 높을 때는 canPut함수에 진입했다가 돌아와서 뒤에 경사로를 설치할 수 있으면 경사로를 설치하고 j변수도 옮긴다. 이 때 옮기는 곳이 경사로가 끝나는 부분인데, 여기서부터 다시 탐색하려면 count 변수가 0으로 초기화 되어야 한다.

반면, 뒷 블럭이 한 칸 더 높을 때는 인덱스가 그대로 (경사로 끝난 다음) 진행되기 때문에 count 변수가 1로 초기화되어야 한다.

 

제출 결과