문제

 

 

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);
}
}

 

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

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

 

 

 

 

'알고리즘(인프런) > 8. DFS, BFS 활용' 카테고리의 다른 글

8-5. 동전교환 (DFS)  (0) 2023.01.05
8-2. 바둑이 승차(DFS)  (0) 2023.01.04
8-1. 합이 같은 부분 집합 (DFS)  (0) 2023.01.02
복사했습니다!