늦었지만 답글 남겨봅니다.
n개의 수가 주어질때 계산을 하기 위해 필요한 연산자의 수는 n - 1 개 입니다.
예를 들어 n = 11 이고 각 연산자의 갯수는 10 10 10 10 이라고 한다면
저희는 10개의 연산자 조합만 구하면 되는 것이지요. 이때 단순히 모든 경우의 수를 구한다면 (40 Permutation 10) 시간이 초과됩니다.
ex) + + - 인 연산자 조합만 생각해봐도 중복되는 경우의 수가 엄청나게 많음
이런 중복문제를 해결하기 위해 10개의 연산자 중 첫번째 자리에 (+, -, * , /) 중 사용가능한 것 하나 넣어주고, 두번째 자리에 남은 (+, -, * / ) 중 사용가능한 것 하나 넣어주고 ...
이런식으로 조합을 구해보시면 중복없이 실제 가능한 경우들만 구할 수 있습니다.
yky2798 3년 전
조언 부탁드립니다.
기본 컨셉은 싹 다 모든 경우의 수를 나열해서 최대값,최소값을 구하는 것으로 잡았습니다.
입출력 관련 시간은 최대한 단축시킨 것 같습니다.
그런데 이 문제는 가지치기(?)를 잘 해야 시간안에 통과하는 문제인 것으로 보이는데
가지치기를 어떤 식으로 하면 될지 컨셉 측면에서 힌트를 받고 싶습니다.
ex>
곱셈의 개수가 입력받은 배열보다 압도적으로 많으면 max 값은 뻔하므로 계산을 한번만 하면 되겠지만 이런 걸 예외처리 한다고 시간 단축이 될까용 ??