네 개의 기본값이 정해진 순서로 주어진다. 네 값을 모두 쓰고 사칙연산과 괄호를 섞어 계산 결과가 24가 되는 식을 만드는 놀이가 있다. 기본값이 3 5 5 2이면 5*5-3+2, (3+5)*(5-2)처럼 24를 만드는 방법이 여럿이다. 곱셈과 나눗셈은 덧셈과 뺄셈보다 먼저 계산하고, 우선순위가 같은 연산자는 왼쪽에서 오른쪽으로 계산한다.
식에는 점수를 매긴다. 0점이 가장 좋은 점수다. 괄호를 한 쌍 쓸 때마다 1점이 붙고, 원래 순서에서 인접한 두 값을 한 번 교환할 때마다 2점이 붙는다. 교환 횟수는 원래 순서를 사용한 순서로 바꾸는 데 필요한 최소 교환 횟수로 센다. 위의 첫 번째 식 5*5-3+2는 3을 세 번째 자리로 옮기는 데 교환이 두 번 필요하므로 4점이다. 두 번째 식 (3+5)*(5-2)는 순서를 그대로 두고 괄호를 두 쌍 썼으므로 2점이다. 기본값이 3 6 2 3이면 (3+6+3)*2는 3점이고 3*6+2*3은 0점이다. 점수가 낮을수록 좋은 식이다.
규칙이 둘 더 있다. 단항 마이너스는 쓸 수 없어서 기본값 3 5 5 2로 -3+5*5+2를 만들 수 없다. 나눗셈은 그 나눗셈의 결과가 정수일 때만 쓸 수 있어서 기본값 2 3 4 9로 2/3*4*9를 만들 수 없다. 네 기본값은 각각 정확히 한 번씩 쓴다.
기본값이 주어지면 값이 24가 되는 식 중 가장 낮은 점수를 구하라.
cho.sh