BOJ_1548 : 부분 삼각 수열

👉 문제링크

1548번: 부분 삼각 수열

---

---

🔸 문제 분석 🔸

• 입력받은 리스트의 원소로 만들 수 있는 삼각 수열의 최대 길이를 출력한다.
• 그리디적인 관점과 브루트포스의 접근이 모두 필요하다.
  • 입력받은 리스트를 오름차순 정렬했을때, arr[i] + arr[i+1] > arr[n] 을 만족하면 i부터 n 사이의 모든 수들도 삼각관계이다. (그리디)
  • 가장 앞이나 가장 뒤를 빼가며 가장 긴 부분 삼각 수열을 찾는다. (브루트포스)
    • 0 ~ n-1 >> 1 ~ n-1 >> ... >> n-2 ~ n-1
    • 1 ~ n-2 >> 2 ~ n-2 >> ... >> n-3 ~ n-2
    • 순서는 뒤에꺼 하나빼보고 앞에거 하나 빼보고..(반복)

🔸 코드 🔸

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

def solution(N, arr):
    for n in range(N, 0, -1):
        for i in range(N - n + 1):
            print(n, i)
            if n < 3 or arr[i]+arr[i+1] > arr[i+n-1]:
                return n

print(solution(n, arr))

🔸 코드 해석 🔸

• 뒤, 앞 순으로 인덱스를 줄여가보며 삼각 수열인지 확인한다.
• 최초로 발견된 삼각 수열의 길이가 최대값이다.

 

🔸 오답 코드 🔸

##########################################
# dfs를 사용한 풀이 : 시간초과
##########################################
n = int(input())
arr = list(map(int,input().split()))
arr.sort()

answer = 0
before = -1

def triple(b):
    for i in range(len(b)-1):
        for j in range(i+1,len(b)):
            for k in b:
                if b[i]+b[j] <= k:
                    return False
    return True

def dfs(d, b):
    global answer

    if n-d <= answer:
        return

    if triple(b):
        if answer < n-d:
            answer = n-d
        return

    for i in range(len(b)):
        if b[i] == b[i-1]:
            continue
        
        temp = b[:]
        temp.pop(i)
        dfs(d+1, temp)

dfs(0, arr)
print(answer)
##########################################

🔸 코드 해석 🔸

• 수 많은 조합을 dfs의 층을 하나씩 내려가며 확인하는 코드이다.
• 예제는 모두 정답이 나오지만 제출시 시간초과가 나온다.

---

🔸 end 🔸

• 브루트포스라고 dfs 하나만 계속 활용하려고 했더니 문제를 분석하는걸 간과하게 된 것 같다.
• dfs로 시간을 가능한 줄여보려고 했지만 택도 없는것 같아서 결국 풀이 포스팅을 찾아보게 되었다.
• 태그에 브루트포스와 그리디가 같이 써있었는데, 저번에 풀었던 문제처럼 두 가지 방법이 있는 줄 알았더니 두 개념
  모두 사용해야하는 문제였다.
• 문제 분석부터 잘못 접근한 케이스인데, 1시간 제한을 두고 이런저런 시도를 하는걸 겁내지 말아야겠다.