서울에서 대구 가는 길에 푼 문제 !!!

17103: 골드버그 파티션

1. 내 풀이 1: 실패

import sys

T = int(sys.stdin.readline())
cnt = 0

decimal = [True for _ in range(1000001)]

for i in range(2, 1000001):
    if decimal[i]:
        for k in range(i+i, 1000001, i):
            decimal[k] = False
decimal[0], decimal[1] = False, False

while T != cnt:
    answer = 0
    num = int(sys.stdin.readline())
    if num == (0 or 2):
        print(0)
    else:
        for i in range(3, int(num/2)+1):
            if decimal[i] and decimal[num-i]:
                answer += 1
        print(answer)
    cnt += 1

사실 지금 생각하면 틀린 게 이해가 되기도 한다. 소수에 2도 포함이 되는데 왜 !!!! range(3~)으로 걸었을까?

분명 전체적인 풀이는 맞는데 계속 틀려서 의문이었다.

2. 내 풀이 2: 성공

import sys

T = int(sys.stdin.readline())
cnt = 0

decimal = [True for _ in range(1000001)]

for i in range(2, 1000001):
    if decimal[i]:
        for k in range(i+i, 1000001, i):
            decimal[k] = False
decimal[0], decimal[1] = False, False

while T != cnt:
    answer = 0
    num = int(sys.stdin.readline())
    if num == (0 or 2):
        print(0)
    else:
        for i in range(2, int(num/2)+1):
            if decimal[i] and decimal[num-i]:
                answer += 1
        print(answer)
    cnt += 1

BOJ에서 채점할 때 계속 100%까지 찍었다가 틀렸다고 나와서, 찬찬히 고민해보았다. 그 결과... 2에 대한 일종의 예외처리만 해주고 2를 소수로 포함 시키지 않아서 발생한 문제로 예상되었다.

하나씩 살펴보자. 자 일단 3번 복창하고 시작해야한다.

• 소수: 에라토스테네스의 체
• 최대공약수 & 최소공배수: 유클리드 호제법

꼭 기억하자!
그리고 웬만하면... 소수 관련 문제가 나오면 일단 "소수 리스트를 만들어 놓는 게 어떨까?" 라는 합리적인 의심을 해보자!

import sys

T = int(sys.stdin.readline())
cnt = 0

decimal = [True for _ in range(1000001)]

for i in range(2, 1000001):
    if decimal[i]:
        for k in range(i+i, 1000001, i):
            decimal[k] = False
decimal[0], decimal[1] = False, False

이것이 바로 그 과정이다. 0부터 1,000,000까지 True(소수이다) 라고 가정하고 True 리스트를 만들어준다. 그 후 2부터 배수별로 False 값으로 해당 인덱스 값을 변경해준다. 이와 관련된 설명 자료는 인터넷에 많으니 참고하자.

while T != cnt:
    answer = 0
    num = int(sys.stdin.readline())
    if num == (0 or 2):
        print(0)
    else:
        for i in range(2, int(num/2)+1):
            if decimal[i] and decimal[num-i]:
                answer += 1
        print(answer)
    cnt += 1

그 후에는 골드버그 파티션을 구해준다. 0이나 2의 경우 0개이기 때문에 0으로 설정해준다. 사실 이에 대한 예외처리는 해주지 않아도 상관없긴 하다.

만약 num의 값이 0이나 2가 아니라면, decimal 리스트를 통해 구해준다.
그 과정은 다음과 같다.

10을 예로 들어보자. (10 = 5 + 5 = 3 + 7)
num = 10 이므로 for 문의 range는 2부터 int(10/2)+1 = 6이다. (range(2,6))
그럼 처음으로 판단하는 값은 i가 3일 때, decimal[3] = True가 될 것이다. 그리고 10에서 3을 뺀 7 역시, decimal[7] = True 이므로 answer에 1이 더해진다.

이때 for문을 마지막 값을 저렇게 계산한 이유는 같은 골드버그 파티션 (8의 경우, 3&5 와 5&3)이 다른 골드버그 파티션으로 계산되어 카운트되기 때문이다.

3. 다른 풀이

다들 나와 유사하게 풀었다!!!! 내가 그들과 유사하게 푼 거겠지 ㅎㅎ
여튼 오늘도 맞춰서 기분이 좋다 야호 ~!~!