[백준] 1253번 좋다 (python)

https://www.acmicpc.net/problem/1253

1253번: 좋다

 

시험기간이라 그런지 알고리즘 푸는 게 더 재밌다..ㅠ

이 문제는 처음에 이해를 못해서 건너뛰었다가 다른 투포인터 문제를 푼 후에 다시 도전한 문제다.

처음에 착각한 부분이 있었는데, 4도 다른 수로 표현이 가능하길래 2 + 2가 되는 줄 알고 1 + 1 = 2도 가능할 줄 알았다. 그런데 문제를 잘 읽어보면 

라고 명시되어 있다.

즉, 4는 2+2가 아니라 1+3이 가능해서 "좋다"에 포함되는 것이다.

 

 

이후 문제를 다시 잘 파악하여 아래 로직대로 풀어나갔다.

1. 입력받은 수들을 정렬한다. (투포인터로 접근할 때는 정렬하고 접근하는 게 좋다.)
2. 이 문제는 각 숫자마자 "좋다" 여부를 판단해야 하기 때문에 for문으로 하나씩 접근한다.
3. while문은 다른 두 수의 합으로 이루어져야 하기 때문에 left와 right가 같으면 안 되므로, left < right로 작성한다.
4. 만약 두 수의 합이 목표 숫자와 일치하는 경우,
   • left가 목표 숫자의 인덱스와 같으면, left의 인덱스를 증가시킨다.
   • right가 목표 숫자의 인덱스와 같으면, right의 인덱스를 증가시킨다.
   • 둘 다 아니면 count를 +1 해준다.
5. 만약 두 수의 합이 목표 숫자와 일치하지 않는 경우
   • 합이 목표 숫자보다 작으면, left += 1을 하여 작은 수를 큰 수로 올린다.
   • 합이 목표 숫자보다 크면, right -= 1을 하여 큰 수를 작은 수로 내린다.

4번에서 left와 right가 목표 숫자의 인덱스와 같으면 안 되는 이유는, 문제에 나와있듯이 "어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 ..." 때문이다. 이에 따라 left, right는 목표 숫자의 인덱스와 같으면 안 된다.

사실 좀 더 정확히 말하자면 "어떤 수가 어떤 수가 아닌 다른 수 두 개의 합으로 ..."라고 하는 게 더 정확할 것 같지만, 문제에는 저렇게 명시되어 있다. 

 

정답 코드

import sys
input = sys.stdin.readline

n = int(input())
numbers = list(map(int, input().split()))

numbers.sort()
count = 0

for idx in range(n):
    left = 0
    right = n - 1

    while left < right:
        left_number = numbers[left]
        right_number = numbers[right]

        sum_ = left_number + right_number
        if sum_ == numbers[idx]:
            if left == idx:
                left += 1
            elif right == idx:
                right -= 1
            else:
                count += 1
                break

        elif sum_ < numbers[idx]:
            left += 1

        elif sum_ >= numbers[idx]:
            right -= 1

print(count)