[Study] 19.최대 실행 횟수 구하기

1. Problem

 

각 세션의 시작시간은 StartTime 함수에 들어있고 각 시작시간의 발표시간은 RunningTime에 들어있다.

시간당 한 세션밖에 발표할 수 없다.

주어진 start_time과 running_time에서 발표가능한 최대 세션 횟수를 구하여라.

 

case1)

Input : n = 5; start_time : [1,3,3,5,7], running_time: [2,2,1,2,1]

Output : 3

 

case2)

Input : n = 3; start_time : [1, 3, 5], running_time: [2 ,2, 2]

Output : 3

 

case3)

Input: n = 1; start_time : [1], running_time: [1]

Output: 1

주어진 발표리스트에서 가능한 최대 세션 회수를 정하시오.

 

 

2. Code

import java.util.ArrayList;
import java.util.List;

public class ifKakao {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int n = 5;
		int[] start_time = {1,3,3,5,7};
		int[] running_time = {2,7,4,3,1};
		System.out.print(Max_run(n, start_time, running_time));
	}
	
	public static int Max_run(int n, int[] start_time, int[] running_time) {
		if(start_time.length == 1) {
			return 1;
		}
        
		List<Integer> start = new ArrayList<>();
		List<Integer> running = new ArrayList<>();

		for(int i = 0; i < n; i++) {
			if(i == 0) {
				if(start_time[i] + running_time[i] <= start_time[i+1]){
					start.add(start_time[i]);
					running.add(running_time[i]);
				} else {
					if(start_time[i] + running_time[i] <= start_time[i+1] + running_time[i+1]) {
						start.add(start_time[i]);
						running.add(running_time[i]);
					} else {
						start.add(start_time[i+1]);
						running.add(running_time[i+1]);
					}
					i++;
				}
			} else {
				if(start.get(start.size()-1) + running.get(running.size()-1) <= start_time[i]) {
					start.add(start_time[i]);
					running.add(running_time[i]);
				} else {
					if(start.get(start.size()-1) + running.get(running.size()-1) > start_time[i+1] + running_time[i+1]) {
						start.set(start.size()-1 , start_time[i]);
						running.set(running.size()-1 ,running_time[i]);
					} 
				}
			}
		}
		return start.size();
}

 

3. Report

처음엔 재귀로 모든 경우의 수를 구해야 되는지 알았다.

생각해보다가 start_time[i] + running_time[i] 와 start_time[i+1] + running_time[i+1]중에 작은걸 넣으면 항상 최댓값이 나온다고 생각이 들어 코드를 짰다.

실행 시간이 n이라 빠른 편인거같다 (결과모름)