[C/C++] 코드업(codeup) 4040번 펜션

▽문제 바로가기

https://codeup.kr/problem.php?id=4040

펜션

 

---

입력

1. 첫째 줄에 두 개의 정수 n과 m이 주어진다. n은 펜션에서 관리하는 여름 성수기 총 기간을 나타내고, m은 펜션이 보유하고 있는 방의 개수이다(1≤n≤100, 3≤m≤30). 편의상 성수기 기간을 1일부터 n일까지로 표시하고, 펜션의 방을 1부터 m까지의 번호로 구분한다.

2. 그 다음 n개의 줄에는 각 줄마다 길이가 m인 문자열이 주어진다. 입력에서 i+1 번째 줄의 j-번째 문자는 여름 성수기 기간 중 i-번째 날에 방 번호가 j인 방의 예약 상태를 나타낸다(1≤i≤n, 1≤j≤m). 이 문자는 방이 이미 예약된 경우에는 'X', 그렇지 않으면 'O'이다. k-번째 날을 예약하면 그 다음 날 정오까지 방을 사용할 수 있다는 것을 의미한다.

3. 마지막 줄에는 고객의 일정을 나타내는 두 개의 정수 s, t가 주어진다, s는 펜션에 도착하는 날이고 t는 펜션을 떠나는 날이다(1≤s<t≤n+1).

 

출력

1. 첫째 줄에 예약 기간 동안 방을 옮기는 최소 횟수를 출력한다.

2. 만일, 방을 옮기지 않아도 되는 경우는 0, 예약이 불가능한 경우는 -1을 출력한다.

3. 고객이 1번 방, 2번 방, 1번 방을 차례로 이용하게 된다면 방을 두 번 옮긴 것으로 본다.

 

문제 풀이

 

그리디 문제입니다.

 

방 옮기는 횟수를 최소로해야하는데 이는 해당 날짜에대하여 가장 길게 머물수 있는 방을 선택하는 것이 무조건 최선입니다.

 

따라서 2일부터 펜션에 머문다고 가정하면 2일예약현황을 확인하고 가장 오랫동안 머물 수 있는 방을 선택하면 됩니다.

 

#include <iostream> 

using namespace std;

int n, m;
int day_begin, day_end;
char arr[101][31];

//가장 오래 머물 수 있는 방 찾기 
int greedy(int index){
	
	int max = 0;
	for(int i=0;i<m;i++){	//1번방부터 m번방까지
		int day = 0;
		for(int j=index;j<day_end-1;j++){	//index일부터 
			if(arr[j][i]=='O') day++;	//머물수 있다면 다음날 해당방 확인(루프계속) 
			else break;
		}
		if(max<day) max = day;
	}
	return max;
}

int main(){
	
	scanf("%d%d", &n, &m);
	
	for(int i=0;i<n;i++){
		for(int j=0;j<m;j++){
			cin >> arr[i][j];
		}
	}
	
	//s와 t입력
	scanf("%d%d", &day_begin, &day_end);
	
	int cnt = -1;	//옮긴 횟수 
	//s일부터 t일까지
	for(int i=day_begin-1;i<day_end-1;){
		cnt++;
		//예약이 불가능한 경우
		if(greedy(i)==0){
			cnt = -1;
			break;
		}
		//날짜에 대하여 가장 오래 머물수 있는 방 찾기 
		i += greedy(i);	//그 기간만큼 더해주기
	}
	
	printf("%d", cnt);
}