[G4] 백준 1253 - 좋다 (python3)

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

1253번: 좋다

---

해결방법

투 포인터를 이용해서 문제를 해결할 수 있다.

풀이👀

이번 문제에서 투 포인터를 활용하기 위해선, 반드시 입력되는 배열이 정렬되어야 한다. 왜냐하면 투 포인터의 head와 tail 인덱스로 어떤 값이 나올지 예측해야 하기 때문이다. 만약 target과 비교했을 때, 값이 작으면 head를 +1 해주고, 반대로 작으면 tail을 -1 해주는 식으로 말이다.

곰곰이 생각해보면 이 로직은 이분탐색의 로직과 같다. (이분탐색으로도 이 문제를 해결 할 수 있을 것 같다.)

---

코드🐱‍👓

def sol(target, array, idx):
    s = 0
    e = len(array) - 1

    while s < e:
        add = array[s] + array[e]
        # print("sol: ",s, e, add, target)
        if s == idx:
            s += 1
            continue
        elif e == idx:
            e -= 1
            continue
            
        if add == target:
            return 1
        elif add < target:
            s += 1
        else:
            e -= 1
    return 0

N = int(input())
arr = list(map(int, input().split()))
arr.sort()

cnt = 0
for idx in range(N-1, -1, -1):
    cnt += sol(arr[idx], arr, idx)
print(cnt)

코드 설명

        if s == idx:
            s += 1
            continue
        elif e == idx:
            e -= 1
            continue

이 문제에는 함정아닌 함정이 존재한다. "수의 위치가 다르면 값이 같아도 다른 수이다."라는 조건을 잘 이해해야 했다.

즉, 달리 생각하면 수의 위치가 같으면 같은 수인 것이니 같은 위치의 숫자에 대해서는 반드시 예외 처리가 필수이다.

 

한 가지 예제로, N은 3이고, A = [0, 0, 0]이 있다. 배열 A의 i번째 수 Ai에 대해서 다른 두 수의 합으로 나타내야 한다.

• A1 = A2 + A3
• A2 = A1 + A3
• A3 = A1 + A2

 

모두 0을 다른 수로 만들었으므로 답은 3이다.

 

반례로는 N은 3이고, A = [0, 0, 1]이 있다. 이 경우의 답은 0이다.

---

(사지방이라 캡쳐가..ㅠㅠ)