[백준/2694] 합이 같은 구간

Problem : https://www.acmicpc.net/problem/2694

 

Difficulty : Gold 3

 

Status : Solved

 

Time : 00:15:24

 

---

 

문제 설명

 

 

어떤 수열이 있을 때, 순서를 유지하면서 적절히 그룹으로 나누면서, 각 그룹에 들어있는 수의 합을 같게 만들 수 있다.

예를 들어, 2, 5, 1, 3, 3, 7은 (2, 5), (1, 3, 3), (7)와 같이 나누면 각 그룹에 들어있는 수의 합이 7로 모두 같아진다.

양의 정수로 이루어진 수열이 주어졌을 때, 이를 합이 같은 구간으로 나누는 방법은 여러 가지가 있다. 이때, 합의 최솟값을 구하시오.

참고로 수열을 통째로 그룹 1개에 넣을 수 있다. 그럼 이때, 수의 합은 수열의 합이 된다.

 

입력 및 출력

 

입력

 

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 50)가 주어진다. 각 테스트 케이스는 첫째 줄에 수열의 크기 M이 주어진다. (1 ≤ M ≤ 10,000) 그 다음 줄부터는 그 수열에 들어있는 수가 주어지고, 한 줄에 10개씩 나누어서 주어진다. 따라서 마지막 줄은 수가 10개가 아닐 수도 있다. 수는 10,000보다 작거나 같은 자연수이다.

 

출력

 

각 테스트 케이스에 대해 한 줄에 하나씩 문제에서 설명한 가장 작은 합을 출력한다.

 

입력 예시

 

3
6
2 5 1 3 3 7
6
1 2 3 4 5 6
20
1 1 2 1 1 2 1 1 2 1
1 2 1 1 2 1 1 2 1 1

 

출력 예시

 

7
21
2

 

 

---

 

풀이

 

브루트포스로 풀되, 전략적으로 경우의 수를 나누어 보는 것이 중요하다.

 

• 모든 합이 같도록 구간을 나누려면, 합의 경우의 수는 전체합의 약수인 경우만 가능하다.
• 또한, 구간은 최소 1개 원소를 보유해야 하므로, 최종적으로 모든 합이 같으려면 그 경우의 수는 전체 구간 중 최댓값보다는 크거나 같아야 한다.

 

 

풀이 코드(Python)

import sys

input = sys.stdin.readline


def is_enable_sum(array, target):
  tmp = 0
  for a in array:
    tmp += a
    if tmp > target:
      return False
    if tmp == target:
      tmp = 0

  return tmp == 0


def search(array):
  min_val, sum_val = max(array), sum(array)
  check_list = []
  for i in range(1, int(sum_val**0.5) + 1):
    if sum_val % i != 0 :
      continue
    if i >= min_val:
      check_list.append(i)
    if i**2 != sum_val:
      check_list.append(sum_val // i)

  check_list.sort()
  for c in check_list :
    if is_enable_sum(array, c) :
      return c
  return 0


def init():
  N = int(input())
  array = []
  cnt = N // 10
  if N % 10:
    cnt += 1
  for _ in range(cnt):
    array += list(map(int, input().split()))
  return array


def solve():
  Q = int(input())
  for _ in range(Q):
    array = init()
    print(search(array))


if __name__ == "__main__":
  solve()

 

풀이 코드(Go)

package main

import (
	"bufio"
	"fmt"
	"math"
	"os"
	"sort"
)

const max int = 10001

var reader *bufio.Reader = bufio.NewReader(os.Stdin)
var writer *bufio.Writer = bufio.NewWriter(os.Stdout)

func isEnableSum(array []int, target int) bool {
	tmp := 0
	for _, a := range array {
		tmp += a
		if tmp > target {
			return false
		}
		if tmp == target {
			tmp = 0
		}
	}
	return tmp == 0
}

func search(array []int) int {
	minVal := max
	sumVal := 0
	for _, a := range array {
		if minVal > a {
			minVal = a
		}
		sumVal += a
	}

	checkList := []int{}
	for i := 1; i <= int(math.Sqrt(float64(sumVal))); i++ {
		if sumVal%i > 0 {
			continue
		}
		if i >= minVal {
			checkList = append(checkList, i)
		}
		if i*i != sumVal {
			checkList = append(checkList, sumVal/i)
		}
	}

	sort.Ints(checkList)
	for _, c := range checkList {
		if isEnableSum(array, c) {
			return c
		}
	}
	return 0
}

func initalize() []int {
	var n, lines int
	fmt.Fscanln(reader, &n)
	array := make([]int, n)
	for i := 0; i < n; i = i + 10 {
		lines = 10
		if n-i < 10 {
			lines = n - i
		}
		for j := 0; j < lines; j++ {
			fmt.Fscan(reader, &array[i+j])
		}
	}
	fmt.Fscanln(reader)
	return array
}

func main() {
	defer writer.Flush()
	var q int
	fmt.Fscanln(reader, &q)
	for i := 0; i < q; i++ {
		array := initalize()
		fmt.Fprintln(writer, search(array))
	}
}

풀이 완료!