

문제

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 |