[백준] 1548번 부분 삼각 수열 _ Python

[초기 접근 방법]

core : 제일 작은 2개가, 제일 큰 것보다 커야 함

1. 그러면 제일 작은 2개의 숫자를 먼저 선택하자. (연속된 수)

2. 삼각형 조건을 만족하는 수를 count

 

[생각]

맞았다! 그런데 더 효율적으로 풀 수 있었다!!

기준이 되는 start 인덱스와, end(=start+2)를 매개변수로 던져준다.

그리고 함수 내에서 end 인덱스부터 탐색을 하면서 end+=1 로 범위를 넓혀주며 카운트를 한다.

 

기존 코드와 개선된 코드 모두 첨부하겠다

 

 

[기존 코드]

# 풀이 시간 : 1시간
# 시간복잡도 : O(n^2)
# 공간복잡도 : O(n)
# 참고 : -

# core : 제일 작은 2개가, 제일 큰 것보다 커야 함
# 1. 그러면 제일 작은 2개의 숫자를 먼저 선택하자. (연속된 수)
# 2. 삼각형 조건을 만족하는 수를 count

def solve(a, b):
    sumAB = a + b
    maxAB = max(a, b)

    if a == b: # 완탐을 하면서 카운트 되니, 이전에 카운트 할 필요가 없음
        count = 0
    else: # minAB 카운트
        count = 1

    for i in lst:
        # 삼각형 조건 만족
        # i는 가장 긴 변이어야 함
        if maxAB <= i < sumAB:
            count += 1

    return count


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

if N == 2:
    print(2)
elif N == 1:
    print(1)
else:
    long = 0
    for i in range(len(lst)-1):
        result = solve(lst[i], lst[i+1])
        if long < result:
            long = result

    print(long)

 

 

[개선된 코드]

# 풀이 시간 : 1시간
# 시간복잡도 : O(n^2)
    # 이전 코드는 항상 lst에 있는 수를 항상 완전탐색을 했는데,
    # 개선된 코드에서는 효율적으로 범위 수를 포함하지 않은 채 적절히 break를 함
# 공간복잡도 : O(n)
# 참고 : https://kau-algorithm.tistory.com/970

# core : 제일 작은 2개가, 제일 큰 것보다 커야 함
# 1. 그러면 제일 작은 2개의 숫자를 먼저 선택하자. (연속된 수)
# 2. 삼각형 조건을 만족하는 수를 count

def solve(start, end):
    count = 2 # 제일 작은 숫자 2개는 항상 포함.
    while True:
        if end == N: #indexOut 방지
            break

        if lst[start] + lst[start+1] > lst[end]:
            count += 1
            end += 1 # 범위를 넓혀줌

        else: # 그 뒤는 더 살펴볼 필요도 없음
            break

    return count


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

if N == 2:
    print(2)
elif N == 1:
    print(1)
else:
    result = 0
    for i in range(len(lst)-2):
        end = i+2
        result = max(result, solve(i, end))

    print(result)

 

 

cf. 더 빨라질 줄 알았지만 똑같네요.. ㅎㅎ