[코드트리 조별과제] 4회차(8/05 ~ 8/11)

4주 차도 Backtracking에 대해 학습했습니다.

 

실력 진단을 수행했는데, 해당 유형의 문제를 풀지 못했습니다.

https://www.codetree.ai/missions/2/problems/select-segments-without-overlap?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

n = int(input())
lines = [tuple(map(int, input().split())) for _ in range(n)]
answer = 0
selected_lines = []

def search(idx):
    global answer
    
    if idx == n:
        for i, line1 in enumerate(selected_lines):
            for j, line2 in enumerate(selected_lines):
                if i < j and line1[0] <= line2[1] and line2[0] <= line1[1]:
                    return
        answer = max(answer, len(selected_lines))
        return

    selected_lines.append(lines[idx])    
    search(idx + 1)
    selected_lines.pop()
    search(idx + 1)

search(0)
print(answer)

 

1. 선분을 순서대로 선택
2. 모든 선분에 대해 선택 작업(비선택 포함)이 끝났다면 유효성 판단
3. 선택된 선분들 비교
   • i > j 혹은 i != j도 가능(하지만 중복된 검사 수행)
   • 등호를 제외하거나 등호가 아닐 때 검사하는 이유는 주어진 입력으로 하나의 선분만 있는 경우가 있기 때문
     • 이는 검사 상, 무조건 겹치지만 자기 자신이기 때문에 항상 선택되어야 함
4. 겹치지 않은 경우, 정답 갱신

겹치는 여부 방법은 다음 그림을 보며 설명하겠습니다.

처음은 line2[1]과 line1[0]가 겹치는 상태로 line1을 주어진 화살표에 따라 이동한다고 가정합니다.

그렇게 계속해서 이동하는 동안, line1은 여전히 line2에 겹치는 상태입니다. 즉, line1[0] <= line2[1]과 line2[0] <= line1[1]에 부합합니다.

지속적인 이동을 하게 된다면 line1[1]은 line2[0]와 멀어지게 됩니다. 이 경우, line1[0] <= line2[1]은 여전히 성립하지만 line2[0] <= line1[1]은 line2[0] > line1[1]이 되므로 성립하지 않게 됩니다. 두 선분이 반대가 되는 경우도 마찬가지입니다.