백준- 3985번 롤케이크

www.acmicpc.net/problem/3985

3985번: 롤 케이크

---

조합으로 풀이

주어진 방청객 중에 1개를 뽑아서 exnum, realnum을 비교하여

가장 많은 조각을 받을것으로 기대되는 방청객의 번호

실제로 가장 많은 조각을 받은 번호

(만약 가장많은조각을 받을것같은 방청객이 여럿이라면 번호가 작은사람을 res값으로)

를 저장함.

 

import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class 롤케이크 {
	static int L,N;
	static int [] arr;
	static People [] p;
	static class People{
		int start;
		int end;
		int num;
		public People(int start, int end, int num) {
			super();
			this.start = start;
			this.end = end;
			this.num = num;
		}
	}
	public static void main(String[] args) throws FileNotFoundException {
		System.setIn(new FileInputStream("input/롤케이크.txt"));
		Scanner sc = new Scanner(System.in);
		L= sc.nextInt();//롤케이크길이
		N= sc.nextInt();//사람수
		arr = new int[L];
		exnum=0;//제일큰값 출력해야하므로 0으로둠
		exres=0;
		realnum=0;
		realres=0;
		p = new People[N];
		for (int i = 0; i < N; i++) {
			p [i] = new People(sc.nextInt(), sc.nextInt(), i);//start end num저장 (0~num-1)
		}
		for (int i = 0; i < p.length; i++) {
			for (int j = p[i].start-1 ; j <= p[i].end-1 ; j++) {
				if(arr[j]==0) arr[j]=i+1;//만약 0이라면 p의번호를 삽입 (이때번호는 1,2,3)		
			}
		}
		
		//가장많은조각 받을것으로 예상되는 방청객의번호출력
		//조합 (3개중에 1개뽑아서 비교)
		expect(0,0,new People[1]); //1명뽑을거니까 크기1짜리 People배열선언	
		System.out.println(exres+1);//people의 num은 0부터 2이므로 +1을해주어야 진짜 인덱스값
		//실제로 가장많은조각을 받은 방청객의번호출력
		//조합 (3개중에 1개뽑아서비교)
		real(0,0,new People[1]);
		System.out.println(realres+1);//모든인덱스값은 0부터였으므로 +1해줌
		
	}
	static int realnum;//실제로 가장 많이받은조각
	static int realres;//실제로 가장 많이조각을받은 방청객의 번호
	private static void real(int idx, int k, People[] sel) {
		if(k==sel.length) {
			int cnt=0;//방청객의 조각수 
			for (int i = 0; i < L; i++) {
				if((sel[0].num+1)==arr[i]) cnt++;
			}
			if(realnum<cnt) {//만약 해당방청객의조각수가 전체결과보다 크다면
				realnum =cnt;//조각수 업데이트
				realres =sel[0].num;//번호 업데이트
			}
			if(realnum==cnt) {//만약 해당방청객의조각수가 전체결과와 같다면
				realres = Math.min(sel[0].num, realres);//방청객의 번호중에 작은값
			}
			return;
		}
		for (int i = 0; i < N; i++) {
			sel[k] =p[i];
			real(idx+1, k+1, sel);
		}
		
	}
	private static void print() {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i]+" ");
		}
	}
	static int exnum;
	static int exres;
	private static void expect(int idx, int k, People[] sel) {
		if(k==sel.length) {
			int sum=0;
			sum += sel[0].end - sel[0].start;
			if(sum>exnum) {
				exnum = sum;
				exres = sel[0].num;
				
			}
			if(sum==exnum) {
				exres = Math.min(exres, sel[0].num);
			}
			return;
		}
		for (int i = 0; i < N; i++) {
			sel[k]=p[i];
			expect(idx+1, k+1, sel);
		}
	}

}