[백준] 14890번 경사로

생각

Github - https://github.com/hellojdh/Code/blob/master/src/baekjoon/swtest/Q14890.java

SW Expert의 활주로 건설과 같은 문제이다. 다른 점이 있다면 경사로문제는 밑면이 1일 때도 처리를
해주어야한다. 활주로 건설 문제는 밑면이 2부터이다.
[SW Expert] 4014. [모의 SW 역량테스트] 활주로 건설

풀이후 생각

이전에 풀었던 [활주로 건설]문제 보다는 좀 더 효율적으로 푼 느낌아닌 느낌이다.

처음 생각

우선 같은 칸의 개수를 세어가다가 높이가 1차이나는 큰 블록을 만날경우는 크게 고려해줄게 없다. 하지만 요번에도 생각했던건 큰 블록에서 낮아질 경우를 처리해 주는것이 문제가 된다.

▶ 이 경우를 위해 boolean형 flag 변수를 두어 내려왔다는 체크를 해주었다. 내려왔을 경우 진행을 하다 연속 블록 개수 변수 cnt가 해당 L값에 도달하면 cnt에서 L을 빼주었다. 즉, L만큼 사용해서 경사로를 만들어 준것이다. 

▶ 이 flag의 처리는 모든 과정에서 있어야한다. 왜냐면 낮아짐 처리가되고나서 같은 블록이 없이 바로 올라갈 수도 있고 또 내려갈 수도 있기 때문이다.

다음 생각

또 고려해주어야할게 경사로의 높이는 무조건 한 칸이므로 높낮이가 변했을 때, 차이가 2이상이면 불가능으로 return 해주었다.

다다음 생각

이전엔 행을 쭉보고 열도 쭉보고 했었지만 이번엔 묶어서 switch 변수 sw를 이용해서 0일 경우는 행을 1일 경우는 열을 보도록 해줘보았다. 

방안

1) 2개를 묶을 수 있다면 묶어주는편이 보기 쉬웠다.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71

package baekjoon.swtest;   import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer;   public class Q14890 {     static int n,l;     static int[][] arr;     public static void main(String[] args) throws IOException{         BufferedReader br = new BufferedReader(new InputStreamReader(System.in));         StringTokenizer st = new StringTokenizer(br.readLine());         n = Integer.parseInt(st.nextToken());         l = Integer.parseInt(st.nextToken());         arr = new int[n][n];         for(int i=0;i<n;i++) {             st = new StringTokenizer(br.readLine());             for(int j=0;j<n;j++)                 arr[i][j] = Integer.parseInt(st.nextToken());         }                  int result = 0;         for(int i=0;i<n;i++) {             if(solve(i,0,0)) result++;             if(solve(0,i,1)) result++;         }         System.out.println(result);     }          private static boolean solve(int x,int y,int sw) {         int t = arr[x][y]; // 처음위치 저장         int cnt = 0;         boolean flag = false; // 낮아진 부분 판단         for(int i=0;i<n;i++) {             // 이전것 tt sw의 값에 따라 행검사 열검사             int tt = (sw==0?arr[x][i]:arr[i][y]);             // 이전 것과 같다면 개수 +1             if(tt==t) {                 cnt++;                 // 낮아졌단은 판단이 있을 때, 세는 개수가 L개가 된다면                 if(flag && cnt>=l) {                     flag = false;                     cnt-=l; // 쌓은거에서 l개만큼 빼주기                 }             }else if(Math.abs(tt-t)!=1) {                 // 높이 차이가 1이 넘으면 false                 return false;             }else if(tt>t) {                 // flag 가 true일 경우 개수를 따져줘서 아니면 false                 if(flag) {                     if(cnt<l) return false;                     else cnt-=l;                     flag = false;                 }                 // 이전 것 보다 크다면 이태까지 cnt의 개수로 판단                 if(cnt<l) return false;                 cnt=1; // cnt 초기화             }else if(tt<t) {                 // flag가 true일 경우, cnt개수로 따져주기                 if(flag) if(cnt<l) return false;                 // 이전 것 보다 작아진다면 앞으로 L개가 모이면 가능.                 flag = true;                 cnt=1;             }             t = tt;         }         if(flag) if(cnt<l) return false;         return true;     } }