[코드업] 4040 : 펜션 (C)

알고리즘

그리디

힌트

손님이 펜션에서 가장 오랫동안 머물 수 있는 방을 찾아준다.

 

풀이

아이디어는 간단하다. 손님이 오늘부터 가장 오랫동안 머물 수 있는 방을 찾아주면 된다.

여기서 잔재주를 부려보면 펜션의 상태를 char형으로 그대로 저장 말고 0,1로 바꾸어 저장해준다. (O : 1, X : 0)

이러면 비교 연산자를 사용하지 않고 조건문 처리가 가능하다.

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

#include<iostream>   using namespace std;   int in[101][31];   int main(){     int n,m;     cin>>n;     cin>>m;          for(int i=1;i<=n;i++){         for(int j=1;j<=m;j++){             char tmp;             cin>>tmp;             if(tmp=='X')                 in[i][j]=0;             else                 in[i][j]=1;         }     }          int start,end;     cin>>start;     cin>>end;          int ans=-1;          while(start<end){         //cout<<start<<"\n";         int index=0;         for(int j=1 ; j<=m ; j++){             if( in[start][j] ){                 for(int k=start+1 ; k<=end ; k++){                     if( !in[k][j] ){                         index=max(index,k-1);                                 break;                     }                                          if(k==end){                         index=end;                     }                 }             }         }                  if(index==0){             ans=-1;             break;         }         start=index+1;         ans++;              }     cout<<ans; }