[코드트리 챌린지] 4주차 - K개 중 하나를 N번 선택하기(Simple)

최고기록 달성!! 

많이는 아니지만 Backtracking 문제를 몇 문제 풀었더니,

실력 진단 테스트를 하면서 그동안 막혔던 Backtracking 문제를 잘 풀 수 있었다.ㅎㅎ

dp에 대한 학습이 더 필요하다고 나왔다.

그렇긴 하지만 아직 Backtrackin, DFS, BFS 문제들을 다 풀어서 완벽하게 하고,

dp를 학습할 계획이다.

 

겹치지 않게 선분 고르기 

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

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

고민은 좀 한 문제지만 1시간 반 안에 넉넉히 풀 수 있는 문제인 것 같다.

 

아래는 본인이 작성한 테스트케이스를 통과한 정답 코드이다.

n = int(input())
lines = []
for _ in range(n):
    x1, x2 = map(int, input().split())
    lines.append([x1, x2])

def selectMaxLine(selectedLines, i):
    global maxCnt
    if len(selectedLines) > maxCnt:
        maxCnt = len(selectedLines)
    
    if i >= n:
        return

    isOverlap = False
    for line in selectedLines:
        if (line[0] <= lines[i][0] and lines[i][0] <= line[1]) or (line[0] <= lines[i][1] and lines[i][1] <= line[1]) or (lines[i][0] < line[0] and lines[i][1] > line[1]):
            isOverlap = True
            break
    if not isOverlap:
        selectMaxLine(selectedLines + [lines[i]], i+1)
    selectMaxLine(selectedLines, i+1)


maxCnt = 0
selectMaxLine([], 0)
print(maxCnt)