[백준] 1239 차트 2%에서 틀렸습니다 반례

백준 1239번 차트
https://www.acmicpc.net/problem/1239

백준 1239 차트 문제에서 테스트케이스는 전부 통과되나 2%에서 오답이 발생했다.

문제의 코드는

from itertools import permutations
from collections import deque

N = int(input())
data = list(map(int, input().split()))
ans = 0

charts= list(permutations(data, N))

visited = set()
for chart in charts:
    if chart not in visited:
        chart_q = deque(chart)
        line_count = 0
        for i in range(N):
            chart_q_copy = chart_q.copy()
            left_sum = 0
            for j in range(N):
                left_sum += chart_q_copy.popleft()
                if left_sum == 50:
                    line_count += 1
                    break
                elif left_sum > 50:
                    break
            left = chart_q.popleft()
            chart_q.append(left)
        if line_count > ans:
            ans = line_count
    visited.add(chart)

print(ans)

차트의 가능한 순열을 모두 돌면서,
그래프를 회전해보며 한쪽이 정확히 50이라면 절반을 차지하므로 그래프 상 직선이 생긴다고 판단하여 카운트를 하는 방식이다.

반례는 다음과 같다.

5
50 10 10 10 20

정답
1
출력
2

위 코드에서의 문제점은, 이중for문에서 deque로 그래프를 회전시킬 때 한바퀴를 돌기 때문에 같은 직선을 두번씩 볼 수 있다는 문제가 있었다.

아래와 같이 코드를 수정하여 문제를 해결했다.

from itertools import permutations
from collections import deque

N = int(input())
data = list(map(int, input().split()))
ans = 0

charts= list(permutations(data, N))

visited = set()
for chart in charts:
    if chart not in visited:
        chart_q = deque(chart)
        line_count = 0
        for i in range(N):
            chart_q_copy = chart_q.copy()
            left_sum = 0
            for j in range(N - i - 1): # deque가 더하는 범위를 제한
                left_sum += chart_q_copy.popleft()
                if left_sum == 50:
                    line_count += 1
                    break
                elif left_sum > 50:
                    break
            left = chart_q.popleft()
            chart_q.append(left)
        if line_count > ans:
            ans = line_count
    visited.add(chart)

print(ans)