[19622]회의실 배정3

package coding;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	static int answer=0;

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int total = Integer.parseInt(br.readLine());
		int[][] info = new int[total][3];
		for(int i=0; i<total; i++) {
			String[] sArr = br.readLine().split(" ");
			
			for(int j=0; j<3; j++) {
				info[i][j] = Integer.parseInt(sArr[j]);
			}
		}
		
		Arrays.sort(info,(o1,o2)->o1[0]-o2[0]);
		fn(0,info,0);
		fn(1,info,0);
		
		System.out.println(answer);
		
		br.close();
	}
	
	 static void fn(int idx, int[][] info, int sum) {
		
		if(idx>=info.length) {
			answer = Math.max(sum, answer);
		}else {
			sum+=info[idx][2];
			fn(idx+2, info, sum);
			fn(idx+3, info, sum);
		}
		
	}
	

}

풀이 과정

시간초과 나옴
탐색이아닌 dp를 이용해야 통과 된다.
아래는 dp를 이용한 풀이

package coding;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int total = Integer.parseInt(br.readLine());
		
		
		int[][] info = new int[total][3]; // 시작, 끝, 인원 배열
		int[] dp = new int[total]; // 주어진 순서 까지 최대로 가질 수 있는 인원을 나타내는 배열
		int answer=0;
		
		for(int i=0; i<total; i++) {
			String[] sArr = br.readLine().split(" ");
			
			for(int j=0; j<3; j++) {
				info[i][j] = Integer.parseInt(sArr[j]);
			}
		}
		
		//문제에서 k가 k-1, k+1 하고 무조건 겹치고 그외에는 겹치지 않으므로 
		//시작 시간으로만 배열해 주면 됨.
		Arrays.sort(info,(o1,o2)->o1[0]-o2[0]);
		
		//total이 최소 1이상이므로 기본으로 넣어준다.
		dp[0] = answer = info[0][2];
		
		//만얀 total이 2이상이면 두번째도 기본으로 넣어준다.
		if(total>=2) {
			dp[1]= info[1][2];
			answer = Math.max(dp[1], answer);
		}
		
		
		//total이 3이상일때만 돌아감.
		for(int i=2; i<total; i++) {
			
			//3이상 부턴 기본적으로 dp[자신의 번호-2]와 자신의 인원을 더한 값을 가진다
			dp[i] = dp[i-2] + info[i][2];
			
			//만약 total 4이상일 경우
			if(i>2) {
				
				//4이상 부턴 dp[자신의 번호-3]과 자신의 인원을 더한 값을 위에서 구한 기본 값과 비교해서 큰 걸 가진다.
				dp[i] = Math.max(dp[i], dp[i-3]+info[i][2]);
			}
		}
		
		//만약 total이 3이상일 경우
		if(total>2) {
			
			//2개만 비교해서 큰걸 가지면 된다.
			answer = Math.max(dp[total-1], dp[total-2]);
		}
		
		System.out.println(answer);
		
		br.close();
	}
	
	 
	

}

다른사람풀이

import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner s=new Scanner(System.in);
		int n=s.nextInt(),i=0;
		long a[][]=new long[n+2][3],d[][]=new long[1000001][2];
		for(;i++<n;s.next(),s.next(),a[i][2]=s.nextInt());
		d[1][1]=a[1][2];
		d[2][1]=a[2][2];
		d[2][0]=a[1][2];
		for(i=0;i++<n;d[i][0]=Math.max(d[i-1][0],d[i-1][1]),d[i][1]=d[i-1][0]+a[i][2]);
		System.out.println(Math.max(d[n][0],d[n][1]));
	}
}

ㅋㅋ;;