백준 / 차트 / 1239번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 차트 / 1239번 (골드 5단계)

문제 사이트: https://www.acmicpc.net/problem/1239

 

문제 설명

 

---

 

나의 풀이

 

N = input()

data = list(map(int, input().split()))
st = []
count = 0

data.sort()

if data[-1] > 50:
    count = 0
else:
    while data:
        st.append(data.pop())
        if st and st[0] == 50:
            count = 1
            break
        if st and data and st[-1] == data[-1]:
            count += 1
            data.pop()
            st.pop()

print(count)

1. 데이터 값 중에서 50이 넘어가면 0개를 출력한다.

2. 데이터의 쌍을 찾아서 최대가 되는 값을 찾는다.

 

1번과 2번의 규칙을 적용해서 데이터가 가장 많이 나오는 값을 찾으려고 했지만 테스트만 통과하고 제출에선 틀렸다.

import sys
import itertools

def check(lst):
    prefix_sums = set()
    current_sum = 0
    center_lines = 0

    for value in lst:
        current_sum += value
        if current_sum == 50 or (current_sum - 50) in prefix_sums:
            center_lines += 1
        prefix_sums.add(current_sum)

    return center_lines

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

n = data[0]
s = data[1:]

if max(s) > 50:
     print(0)
else:
    ans = 0
    s.sort()

    for perm in itertools.permutations(s):
        center_lines = check(perm)
        if center_lines > ans:
            ans = center_lines

    print(ans)

순열의 조합을 사용하여 모든 경우의 수를 계산해서 가장 많이 경우의 수를 뽑아서 결과가 값을 출력하려고 했지만 이건 시간 초과가 발생했다.

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)

다른 사람의 풀이를 참고해서 풀었다. 이 풀이는 리스트를 사용하여 모든 중간 합계를 저장하고, 이중 for 루프를 통해 중심을 지나는 선을 계산하는 방밥을 사용했다.

---

※ 알아야 할 것

 

https://ddggblog.tistory.com/152

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