글 읽기 - 반례를 찾지 못하겠습니다...

nw4611 1년 전 0

누적합을 역으로 탐색하면서 배열의 모든 수의 합을 4로 나눈 값(= val)의 2 * val, 3 * val, 4 * val을 만난 경우에는 해당 위치로 나눌 수 있으므로 만난 횟수를 dict에 저장한 다음 누적합이 val인 경우에 조합 가능한 모든 경우의 수를 더해주도록 했는데

https://www.acmicpc.net/source.. 다음과 같이 실패하는데 반례를 못찾겠습니다. 어떤 부분이 문제인지 알려주시면 감사드리겠습니다!

# 문제 링크: https://www.acmicpc.net/problem/21757

import sys
input = sys.stdin.readline
n = int(input())

nums = list(map(int, input().split()))

for i in range(1, n):
    nums[i] += nums[i - 1]

if nums[-1] % 4:
    print(0)
else:
    if nums[-1] == 0:
        zero_count = 0
        for cur in nums:
            if cur == 0:
                zero_count += 1
        print((zero_count - 1) * (zero_count - 2) * (zero_count - 3) // 6)
    else:
        val = nums[-1] // 4

        dict = [0, 0, 0, 0, 0]

        answer = 0

        for i in range(n - 1, -1, -1):
            if nums[i] == val:
                answer += (dict[2] * dict[3] * dict[4])
            elif nums[i] == 2 * val or nums[i] == 3 * val or nums[i] == 4 * val:
                dict[(nums[i] // val)] += 1

        print(answer)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

반례를 찾지 못하겠습니다...

nw4611 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말