#14809 경사로

문제 링크: https://www.acmicpc.net/problem/14890

14890번: 경사로

 

 

경우의 수를 일일이 따져주는게 생각보다 시간이 오래 걸렸다.

 

먼저, 지도를 왼쪽에서 오른쪽, 위에서 아래로 훑으며 각각의 행, 열이 길이 될 수 있는지를 확인하고 길이라면 길의 개수를 1씩 증가시켜 줄 것이다.

 

 

그렇다면 이제는 길이 될 수 있는지를 판별하는 로직을 짜기만 하면 된다.

 

로직을 설명하기 전, 변수를 정의하자

 

• l = 경사로의 가로 길이
• prev_h = 이전 칸의 높이
• height[i][j] = (i, j) 의 높이
• accum = 연속된 같은 높이의 누적 칸수
• up_down = 이전에 높은 칸에서 낮은 칸으로 경사로를 둘 수 있는지 판별되지 않았을 때 true, 초기값은 false

 

현재 칸이 (i, j) 라고 할 때,

1. prev_h + 1 == height[i][j] (현재 높이가 이전 높이보다 1 큰 경우)
   1. up_down == true || accum < l (경사로를 둘 수 없는 경우)
      -> 길이 될 수 없음
   2. 이 외 (이전 칸들에 경사로를 둘 수 있는 경우)
      accum = 1
2. prev_h == height[i][j] + 1 (현재 높이가 이전 높이보다 1 작은 경우)
   1. up_down == true (경사로를 둘 수 없는 경우)
      -> 길이 될 수 없음
   2. l == 1 (바로 경사로를 둘 수 있는 경우, edge case)
      accum = 0
   3. 이 외 (경사로를 둘 수 있는지 판별해야 하는 경우)
      accum++
      up_down = true
3. prev_h == height[i][j] (이전 높이와 현재 높이가 같을 때)
   accum++
   
   1. up_down == true && accum >= l (경사로를 둘 수 있는 경우)
      accum = 0
      up_down = false
4. 이 외 (prev_h 와 height[i][j] 높이 차이가 1 초과일 때)
   -> 길이 될 수 없음

 

함수 만들어서 분리시키면 조금 더 짧은 코드를 짤 수 있을 것 같다.

 

#include <bits/stdc++.h>

using namespace std;

int main()
{
   int height[100][100];
   
   int n, l;
   scanf("%d %d", &n, &l);
   
   for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
         scanf("%d", &height[i][j]);
      }
   }   
   
   int ret = 0;
   for (int i = 0; i < n; i++) {

      int prev_h = height[0][i], accum = 1;
      bool up_down = false, is_path = true;
      for (int j = 1; j < n; j++) {
         if (prev_h + 1 == height[j][i]) {
            if (up_down || accum < l) {
               is_path = false;
               break;
            }
            accum = 1;

         } else if (prev_h == height[j][i] + 1) {
            if (up_down) {
               is_path = false;
               break;
            }
            
            if (l == 1) {
               accum = 0;
            } else {
               up_down = true;
               accum = 1;
            }
            
         } else if (prev_h == height[j][i]) {
            accum++;
            
            if (up_down && accum >= l) {
               accum = 0;
               up_down = false;
            }
            
         } else {
            is_path = false;
            break;
         }
         
         prev_h = height[j][i];
      }
      
      if (!up_down && is_path) {
         ret++;
      }
      
      is_path = true;
      prev_h = height[i][0];
      accum = 1;
      up_down = false;
      for (int j = 1; j < n; j++) {
         if (prev_h + 1 == height[i][j]) {
            if (up_down || accum < l) {
               is_path = false;
               break;
            }
            accum = 1;

         } else if (prev_h == height[i][j] + 1) {
            if (up_down) {
               is_path = false;
               break;
            }
            
            if (l == 1) {
               accum = 0;
            } else {
               up_down = true;
               accum = 1;
            }
            
         } else if (prev_h == height[i][j]) {
            accum++;
            
            if (up_down && accum >= l) {
               accum = 0;
               up_down = false;
            }
            
         } else {
            is_path = false;
            break;
         }
         
         prev_h = height[i][j];
      }
      
      if (!up_down && is_path) {
         ret++;
      }
   }
   
   printf("%d", ret);
   return 0;
}