8-3. 최대점수 구하기(DFS)

---

문제

 

 

package test;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

//백준
public class Main {

	static int[] array;
	static int[] visited;
	static int size;
	static int total;
	static int re = Integer.MIN_VALUE;


	public static void dfs(int point, int time, int sum) {
		
		int ch = sum;
		


		if(time<=total&&sum>re) re=sum;

		if(time<total&&point<size*2) {
			
			
			//	System.out.println("sum("+(sum + array[point-1] )+") = sum["+sum+"] + array["+(point-1)+"] = "+ch+" + "+array[point-1]);
				dfs(point+2, time + array[point], sum+array[point-1]);
				dfs(point+2, time, sum );
			
		}

	}

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		// Queue<Integer> q = new LinkedList<>();

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		size = Integer.parseInt(st.nextToken());
		total = Integer.parseInt(st.nextToken());


		array = new int[size*2];
		// visited = new int[size];


		for (int i = 0; i < size*2; i++) {
			 st = new StringTokenizer(br.readLine(), " ");
			array[i] = Integer.parseInt(st.nextToken());
			i++;
			array[i] = Integer.parseInt(st.nextToken());
		}

		dfs(1,0,0);
		System.out.println(re);

	}

}

 

시간이 초과되기 전까지 합을 다 구해본다.

이차배열로 값을 해도되고 지금과 같은 문제는 홀/짝으로 구분이 가능해서 짝에 점수 홀에 시간을 두고 계산했다.