알고리즘 - Python / 백준 - 1239번 : 차트

1239번: 차트 (acmicpc.net)

1239번: 차트

 

---

풀이

• 파이차트의 퍼센트를 입력받고 중앙을 지나는 라인의 최대 수를 구하는 문제이다.
• 항목의 수인 N이 8이 최대 이므로 모든 경우를 다 살펴보는 경우는 8! = 40,320 이다.
• 따라서 파이썬으로도 시간내에 모든 경우를 살펴볼 수 있다고 생각하여 전수조사 하였다.
• 이후 해당 경우에 라인이 어느 포인트에 그려지는지 리스트에 추가하고 리스트 항목에 +50 한 수가 포함되어 있는지 확인하는 식으로 라인 개수를 세었다.
• 또한 한 항목이 50%를 초과하는 범위를 가지면 나오는 라인의 개수는 무조건 0이므로 예외처리 하였다.

 

import sys
import itertools

def check(lst):
    line = []
    c = 0
    ans = 0
    for i in lst:
        c += i
        line.append(c)
    for i in range(0,len(line)-1):
        for t in range(i+1,len(line)):
            if line[i] + 50 == line[t]:
                ans += 1
    return ans

ans = 0
n = int(sys.stdin.readline())
s = list(map(int, sys.stdin.readline().split(" ")))
s.sort()
if max(s) > 50:
    print(0)
else:
    brt = list(itertools.permutations(s))
    for i in brt:
        ch = check(list(i))
        if ch > ans:
            ans = ch
    print(ans)

---