[백준] 1248 - Guess (G3)
·
알고리즘 (PS)/BOJ
https://www.acmicpc.net/problem/1248어떤 수열의 연속하는 모든 부분수열 ai ~ aj 에 대한 합의 부호값 (+, 0, -) 를 알고 있을 때, -10 ~ 10 사이의 숫자를 사용하여 만들 수 있는 수열을 찾는 문제 처음에는 어떻게 해야할 지 감이 안왔는데, 보통 이렇게 알고리즘이 감이 안오는 문제는 입력 크기를 줄이고 완전탐색으로 풀도록 유도하는 경우가 많다. 이 문제도 수열의 길이가 최대 10으로 -10 ~ 10 까지 숫자 10개를 모두 시도해보면서 풀 수 있다.그렇다고 정말 나이브하게 완탐으로가면 21^10 이라는 경우의 수를 체크해야 한다.하지만 모든 부분수열의 ai ~ aj 부호값을 모두 만족해야 하는점에서 경우의 수를 치다보면 체크할 경우의 수가 확 줄어든다는 것을..