[Python][BOJ 1239] 중심선 개수 세기

[BOJ 1239] 중심선 개수 세기 Python 풀이

📌 문제 분석

• 주어진 N개의 숫자에서 중심을 가로지르는 선의 개수를 구하는 문제입니다.
• 중심을 가로지른다는 것은 특정 조합의 합이 50이 되는 경우를 의미합니다.
• 모든 가능한 조합을 고려하여 최대 중심선 개수를 찾아야 합니다.

🚨 시행착오

• 처음에는 단순히 50을 만드는 조합의 개수를 세는 방식으로 접근했습니다.
• 하지만 문제의 의도는 중심선을 관통하는 선의 개수를 세는 것이었습니다.
• 이로 인해 잘못된 결과가 나왔고, 문제를 다시 분석하게 되었습니다.

처음 코드의 문제점

• 중심선을 세는 로직이 아닌, 단순히 50을 만드는 조합의 개수를 세고 있었습니다.
• 원형으로 배치된 숫자들을 고려하지 않았습니다.

어떻게 고쳤나요?

• 누적합을 사용하여 각 조합에서 중심선을 세는 방식으로 변경했습니다.
• 모든 가능한 순열을 고려하여 최대 중심선 개수를 찾도록 수정했습니다.

💡 해결 방안

import sys
from itertools import permutations

def count_center_lines(sequence):
    # 누적합 배열 생성
    prefix_sum = []
    current_sum = 0
    for num in sequence:
        current_sum += num
        prefix_sum.append(current_sum)

    # 중심선 개수 세기
    count = 0
    for i in range(len(prefix_sum)-1):
        for j in range(i+1, len(prefix_sum)):
            if prefix_sum[i] + 50 == prefix_sum[j]:
                count += 1
    return count

N = int(sys.stdin.readline())
numbers = list(map(int, sys.stdin.readline().split()))

# 50보다 큰 수가 있으면 중심선을 만들 수 없음
if max(numbers) > 50:
    print(0)
else:
    # 모든 순열에 대해 최대 중심선 개수 찾기
    max_lines = 0
    for perm in permutations(numbers):
        max_lines = max(max_lines, count_center_lines(perm))
    print(max_lines)

🎯 이 문제의 핵심 포인트

1. 중심선을 가로지르는 조건을 정확히 이해하기
2. 누적합을 활용하여 효율적으로 중심선 개수 세기
3. 모든 가능한 조합을 고려하기 위해 순열 사용
4. 문제 조건을 잘 활용하여 불필요한 계산 줄이기

✨ 이번 문제를 통해 배운 점

1. 문제의 의도를 정확히 파악하는 것이 중요하다.
2. 누적합을 활용하면 특정 조건을 만족하는 경우를 쉽게 찾을 수 있다.
3. itertools의 permutations를 활용하여 모든 조합을 쉽게 생성할 수 있다.

🔍 코드 설명

• count_center_lines 함수는 주어진 수열에서 중심선을 가로지르는 선의 개수를 세는 함수입니다.
• 메인 로직에서는 입력을 받고, 모든 순열에 대해 최대 중심선 개수를 찾아 출력합니다.
• 이 문제를 통해 알고리즘 문제 해결의 중요성을 다시 한 번 느꼈습니다.