수식 최대화

여러 개의 정수가 순서대로 나열되어 있고, 이 정수들 사이에 빼기(-) 기호가 있는 수식이 주어진다.

여러분의 목표는 이 수식에 괄호를 적절히 추가하여 수식의 값을 최대화하는 것이다.

예를 들어 수식이 와 같을 때, 괄호를 추가하지 않고 계산하면 가 되지만, 와 같이 괄호를 추가하면 이 되어 더 큰 값을 얻을 수 있다.

여러분은 두 개의 부분문제를 해결해야 한다. 각 부분문제는 독립적이며, 각각 추가할 수 있는 괄호의 개수 제한이 있다.

• 부분문제 1: 9개의 정수가 주어지며, 최대 10개의 괄호 쌍을 추가할 수 있다.
• 부분문제 2: 18개의 정수가 주어지며, 최대 20개의 괄호 쌍을 추가할 수 있다.

조작 방법

"(수식의 값) = (수식)" 형태로 표시된다. 수식의 각 정수는 원 안에 표시되어 있고, 원들 사이에는 빼기 기호가 있다.

괄호 추가하기:

• 시작 원을 클릭하여 첫 번째 원을 선택한다.
• 끝 원을 클릭하여 두 번째 원을 선택한다.
• 선택한 두 원과 그 사이의 모든 원들을 포함하는 괄호 쌍 (와 )가 추가된다. 추가한 괄호가 짝이 맞아야만 추가할 수 있다.

괄호 제거하기:

• 기존 괄호 위에 마우스를 올리면, 짝이 맞는 두 괄호가 강조 표시된다.
• 괄호를 클릭하면 강조된 해당 괄호 쌍이 제거된다.

화면 하단에는 현재 상황에 맞는 안내 메시지가 표시된다. 언제든지 "다시 하기" 버튼을 눌러 처음부터 다시 시작할 수 있다.

채점 기준

각 부분문제를 해결했다는 것은, 해당 부분문제에서 수식의 계산 결과가 이론적으로 가능한 최댓값과 같다는 것이다.

• 부분문제 1을 해결하면 전체 점수의 20%를 받는다.
• 부분문제 2를 해결하면 전체 점수의 80%를 받는다.
• 부분문제를 해결하지 못하면 해당 부분문제의 점수를 받지 못한다.

최종 점수는 각 부분문제에서 얻은 점수의 합이다.

문제 형식

인터랙티브

출처

• KOI 2025 1차대회 고등부 1교시 19번
• KOI 2025 1차대회 중등부 1교시 20번