2798 - 블랙잭(브루트포스, 백트래킹)

2798 - 블랙잭(브루트포스, 백트래킹)

# 주소

https://www.acmicpc.net/problem/2798

# 문제

# 문제 해설 및 코드 리뷰

import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main{ static int[] arr; static int n; static int m; static boolean visit[]; static int max = 0; public static void main(String[] args) throws IOException{ BufferedReader br =new BufferedReader(new InputStreamReader(System.in)); String s = br.readLine(); StringTokenizer st = new StringTokenizer(s," "); n = Integer.parseInt(st.nextToken()); m = Integer.parseInt(st.nextToken()); visit = new boolean[n]; arr = new int[n]; s = br.readLine(); st = new StringTokenizer(s, " "); for(int i = 0; i < n; i++) { arr[i] = Integer.parseInt(st.nextToken()); } dfs(0, 0); System.out.println(max); } public static void dfs(int t, int sum){ if(t == 3){ if(sum <= m){ max = Math.max(max, sum); } return; } for(int i = 0; i < n; i++){ if(!visit[i]){ visit[i] = true; dfs(t + 1, sum + arr[i]); visit[i] = false; } } } }

백트래킹으로 풀이를 하려고 했는데 기존의 코드랑 큰 차이는 없습니다.

근데 자꾸만 시간초과가 떠서 뭘까.. 뭘까 고민하다가 return을 if 문이 끝나고 넣으니까 잘 작동하네요

시간제한 거는거 참 까다로운거 같습니다.. ㅠㅠㅠㅠ

원래는 Scanner로 풀려고 했는데 시간초과 나서 Buffered로 다 바꾼 코드입니다.

그리고 n과 m은 띄어쓰기를 하고 받아야 하므로 StringTokenizer로 n과 m을 입력받습니다.

boolean타입의 visit을 선언하고 arr에 Integer를 입력받습니다!

늘 그렇듯 dfs(0,0)을 실행하되 dfs의 인자 2개는 정수형으로 입력받습니다.

하나는 index값인 t, 하나는 블랙잭의 세 카드의 합이될 sum입니다!

그리하여 t가 3이 될 때 sum이 m보다 작거나 같은 전제하에 max에 값을 담습니다.

단, max에 들어가는 값은 sum과 기존의 max값과 비교하여 큰 값을 넣도록 합니다.

(여기서 시간초과가 났습니다. arraylist에 합들을 다 담고 arraylist를 정렬해서 가장 큰 값을

답으로 출력하려고 했는데,,,)

이후 return하여 재귀함수로 돌아오면 되겠습니다.

어려운 문제는 전혀 아닙니다. 다만 늘 시간초과 때문에 애먹는거같네요... 오늘도 화이팅

감사합니다

from http://codingrapper.tistory.com/49 by ccl(A) rewrite - 2021-10-11 03:27:57