BOJ 14890번: 경사로

1. 문제

문제 바로가기> BOJ 14890번: 경사로

14890번: 경사로

 

2. 풀이

2N 개의 길 모두를 살펴보면서 지나갈 수 있는 길의 개수를 세어주면 된다.

 

이때, 총 4가지 경우의 수가 있다.

 

1. 이전 칸과 높이가 같은 경우

  ▶ 같은 높이의 칸을 세어주는 변수인 `cnt` 를 1 증가시켜준다. 

 

2. 높이가 낮아지는 경우 (높이 차 = 1)

  ▶ 해당 칸을 제외하고, 앞으로 1-L개의 칸의 높이가 같아야, 경사로를 건설할 수 있다.

 

3. 높이가 높아지는 경우 (높이 차 = 1)

  ▶ 지금까지 L개 이상의 칸의 높이가 같아야, 경사로를 건설할 수 있다.

 

4. 높이차 > 1

  ▶ 경사로는 높이가 항상 1이므로, 이 경우 경사로를 만들어 길을 지나갈 수 없다.

 

위 과정을 지났을 때,

① ismake = true 이고,

② cnt >= 0 (높이가 낮아지는 경우, 경사로 건설 가능) 이라면,

해당 길을 건너갈 수 있으므로 `ans++`을 해주면 된다!

 

2.0.1. C++

      

      

      

    
    

      <cpp />
    
#include<iostream>
#define MAX 101
using namespace std;

int N, L;
int map[MAX][MAX];

void input(){
    cin >> N >> L;
    for(int i=0; i<N; i++){
        for(int j=0; j<N; j++) cin >> map[i][j];
    }
}

void solution(){

    int ans = 0;
    
    // row check
    for(int r=0; r<N ; r++){
        
        int cnt=1;
        bool ismake = true;
        for(int c=0; c+1<N; c++){
            if(map[r][c] == map[r][c+1]) cnt++;
            else if(map[r][c]-map[r][c+1] == 1){ // 높이가 낮아지는 경우
                if(cnt >= 0) cnt = 1-L;
                else{
                    ismake = false;
                    break;
                }
            }
            else if(map[r][c]-map[r][c+1] == -1){ // 높이가 높아지는 경우
                if(cnt >= L) cnt = 1;
                else {
                    ismake = false;
                    break;
                }  
            }
            else { // 높이 차가 1 이상인 경우
                ismake = false;
                break;
            }
        }
        if(cnt>=0 && ismake) ans++;
    }

    // column check
    for(int c=0; c<N ; c++){ 

        int cnt=1;
        bool ismake = true;
        for(int r=0; r+1<N; r++){
            if(map[r][c] == map[r+1][c]) cnt++;
            else if(map[r][c]-map[r+1][c] == 1){ // 높이가 낮아지는 경우
                if(cnt >= 0) cnt = 1-L;
                else{
                    ismake = false;
                    break;
                }
            }
            else if(map[r][c]-map[r+1][c] == -1){ // 높이가 높아지는 경우
                if(cnt >= L) cnt = 1;
                else {
                    ismake = false;
                    break;
                } 
            }
            else { // 높이 차가 1 이상인 경우
                ismake = false;
                break;
            }
        }
        if(cnt>=0 && ismake) ans++;
    }

    cout << ans;
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    input();
    solution();
}

 

2.0.2. Java

      

      

      

    
    

      <cpp />
    
import java.io.*;
import java.util.*;

public class Main {
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int X = Integer.parseInt(st.nextToken());
        int[][] map = new int[N][N];
        
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for(int j=0; j<N; j++)
                map[i][j] = Integer.parseInt(st.nextToken());
        }
        
        int ans = 0; // 활주로를 건설할 수 있는 경우의 수
        
        // row 체크
        for(int c=0; c<N; c++) {
            boolean possible = true;
            int before=map[0][c], cnt=0;
            for(int r=0; r<N; r++) {
                if(map[r][c] == before) cnt++;
                else {
                    int diff = Math.abs(map[r][c]-before);
                    if(diff!=1 || cnt<0) possible = false;
                    if(before < map[r][c]) {
                        if(cnt<X) possible = false;
                        else cnt=1;
                    }
                    else cnt = -X+1;// before > now
                    before = map[r][c];
                }
            }
            if(cnt < 0) possible = false;
            if(possible) ans++;
        }
        
        // column 체크
        for(int r=0; r<N; r++) {
            boolean possible = true;
            int before=map[r][0], cnt=0;
            for(int c=0; c<N; c++) {
                if(map[r][c] == before) cnt++;
                else {
                    int diff = Math.abs(map[r][c]-before);
                    if(diff!=1 || cnt<0) possible = false;
                    if(before < map[r][c]) {
                        if(cnt<X) possible = false;
                        else cnt=1;
                    }
                    else cnt = -X+1;// before > now
                    before = map[r][c];
                }
            }
            if(cnt < 0) possible = false;
            if(possible) ans++;
        }

        System.out.println(ans);
        br.close();
	}
}