월영교 건너기

 

2023 SFPC에서 제일 재밌던 문제였다

 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <iomanip>

using namespace std;
 
int sum(vector<int>& nums){
	int sum = 0;
	for(int i=0 ;i<nums.size();i++){
		sum+=nums[i];
	}
	return sum;
}


int main() {
	int min = 0, a=0;
	vector<int> arr; //다리의 상태 
	vector<int> classes; //각 반 학생 수 
	int w,b,n,temp;
	
	cin >> w >> b >> n; //w는 최대인원, b는 다리 구간 수, n은 학급 수 
	
	arr.resize(b);
	classes.resize(n);
	
	for(int i=0; i<n; i++){
		cin >> temp;
		classes[i] = temp;
	}
	
	// 0 1 2 3 4 5 6 7을 순차적으로 집어넣음
	//넣으면 오른쪽으로 rotate가 일어남 (1분 증가)
	
	// roatate 이후에 arr배열의 sum + 다음번 학급사람수 확인
	// 		만약 최대인원수 이상이 아닐 경우에만 0번째 인덱스에 다음학급 추가. a++
	// 		만약 최대인원수보다 많다면 다시 맨 위로.
	
	//반복이 끝나는 조건은 모든 반이 다 건넜을 때이므로 마지막 반이 배열에 들어오는 순간 반복 끝내고 min에 5를 더하면 됨 
	
	arr[0] = classes[0];
	min++;
	a++; // 0반을 미리 넣고, 1반부터 넣게 함 
	
	/*
	for(int i=0; i<b; i++){
		cout << arr[i] << " ";
	}
	cout << "\t" << min << "분때" <<"\n";
	*/
	 
	while(1){
		if(arr[b-1]!=0) arr[b-1] = 0; //마지막칸이 0이 아니라면 0으로 바꿈 (rotate 시 0번째 인덱스로 건너가는거 방지) 
		
		rotate(arr.begin(),arr.end()-1,arr.end()); //오른쪽으로 한 칸씩 밀리고 회전함 
		
		if(sum(arr) + classes[a] <= w){
			arr[0] = classes[a]; //마지막 값이 0번째 인덱스로 되돌아올텐데 그 값을 수정
			a++;
		}
		
		min++;
		
		/*
		for(int i=0; i<b; i++){
			cout << arr[i] << " ";
		}
		cout << "\t" << min << "분때" <<"\n";
		*/
		if(a==n) break; 
		
	} 
	
	min = min + b;
	cout << min;
	
    return 0;
}

 

처음 while 문의 조건을 sum(arr)!=0 으로 해서 배열이 최대값 100에 66 44가 들어오는 상황일 때 문제가 생겼었다.

그 후에 수정해서 마지막 학급이 들어오는 순간 루프를 멈추고 다리 구간 수를 더한 값을 출력하게 했다.