파이썬 백준 1253번 : 좋다

문제

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

 

 

풀이

알고리즘

투포인터

자료구조

리스트

 

 

start와 end를 설정해두고 값의 합에 따라 start또는 end를 이동시키며 해결했다. 

import sys

n = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
nums.sort()
result=0

for i in range(len(nums)):
    start=1 if i==0 else 0 #start 설정
    end=i-1 if i==len(nums)-1 else len(nums)-1 #end 설정
    while True:
        if start>=end or start<0 or end>=len(nums): #종료조건 
            break
        if nums[start]+nums[end]>nums[i]: #더한 값이 target보다 크면 end를 줄임
            end-=1
            if end==i:
                end-=1
        elif nums[start]+nums[end]<nums[i]: #더한 값이 target보다 작으면 start를 늘림
            start+=1
            if start==i:
                start+=1
        else: # 더한 값과 target이 같다면 result증가
            result+=1
            break

print(result)

 

 

덧)

처음 N의 범위가 2000이여서 N^2으로 풀어도 되겠다! 하고 조합으로 모든 2개의 조합을 만들고 해당하는 값의 수를 출력하는 방식으로 코드를 작성했다. 

import sys
from itertools import combinations
n = int(sys.stdin.readline())
nums = list(map(int, sys.stdin.readline().split()))
nums.sort()

add_nums={sum(pair) for pair in combinations(nums,2)}
result=0
for add_num in add_nums:
    result+=nums.count(add_num)

print(result)

 위 코드로 시간 초과가 발생해서 투포인터로 변경했다..

 

덧2)

처음에 start=0, end=len(nums)-1로만 설정했는데 60~70%에서 틀렸다.

반례는 아래의 경우이다.

2
0 1
#ans=0