BOJ 30897 0으로 만들기
문제 내용
이상 이하의 정수로 이루어진 길이 ()의 수열이 주어집니다. 모든 수의 쌍 사이에 + - * 중 하나를 끼워넣고 추가로 괄호를 최대 한 번 쳐서 결과를 0으로 만들 수 있는지 판단하고,
가능하다면 그러한 방법을 아무거나 하나 출력하시오.
문제 풀이
스포일러 1
최소 길이가 매우 길다는 점에서, 수열이 충분히 길면 항상 0으로 만들 수 있을 것이라고 추측할 수 있습니다. 또한 괄호를 최대 한 번 사용할 수 있으므로, 값이 0인 구간 하나를 잡아서 괄호로 묶고 나머지를 모두 곱하는 것을 생각할 수 있습니다.스포일러 2
시작점이 같은 두 부분 수열의 결괏값을 같게 만들 수 있으면, 짧은 쪽을 제외하여 답을 0으로 만들 수 있습니다. 따라서 이 결과가 겹치게 만들 수 있는지 생각해 봅니다.맨 앞에서부터 모든 부분 수열의 결괏값이 이상 이하가 되도록 +와 -를 할당할 수 있음을 보일 수 있습니다. 그러면 가능한 결괏값의 종류는 최대 가지입니다.
수열의 길이가 항상 이상이므로, 비둘기집의 원리에 의해 결괏값이 일치하는 서로 다른 두 지점을 반드시 찾을 수 있습니다.
이 구간의 시작점의 부호가 -라면 구간 내의 모든 수의 부호를 뒤집어 줍니다.