-
반응형
https://www.acmicpc.net/problem/21943
풀이
백트래킹을 이용하여 모든 경우의수를 구해주었습니다.
이때 만약 곱셈이 2개가 있다면, 아래와 같이 3개의 그룹을 생성해준 뒤, 곱해주며 갱신하는 방식으로 백트래킹을 진행했습니다.
시간복잡도
백트래킹의 시간복잡도이고, N개 각각 최대 N-1개의 선택지가 있기때문에 O(N^(N-1)) 이 됩니다.
코드
import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import java.util.StringTokenizer; public class Main { static int answer = 0; public static void dfs(int[] arr, int[] mult, int q, int ind) { if (ind == arr.length) { int result = Arrays.stream(mult).reduce(1, (x, y) -> x * y); answer = Math.max(answer, result); return; } for (int i = 0; i < mult.length; i++) { mult[i] += arr[ind]; dfs(arr, mult, q, ind + 1); mult[i] -= arr[ind]; } } public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.valueOf(br.readLine()); int[] arr = new int[n]; StringTokenizer st = new StringTokenizer(br.readLine()); for (int i = 0; i < n; i++) { arr[i] = Integer.valueOf(st.nextToken()); } st = new StringTokenizer(br.readLine()); int p = Integer.valueOf(st.nextToken()); int q = Integer.valueOf(st.nextToken()); int[] mult = new int[q + 1]; dfs(arr, mult, q, 0); System.out.println(answer); } }
반응형'문제풀이 > 백준oj' 카테고리의 다른 글
[백준OJ] 16985번 Maaaaaaaaaze - Java (0) 2022.12.31 [백준OJ] 18511번 큰 수 구성하기 - Java (0) 2022.12.28 [백준OJ] 12837번 가계부 (Hard) - Java (0) 2022.12.28 [백준OJ] 1473번 미로 탈출 (Java) (0) 2022.12.28 [백준OJ] 8980번 택배 (Java) (0) 2022.12.27 댓글