[코드트리 조별과제] 겹치지 않게 선분 고르기

굉장히 시간이 오래 걸렸다 호호~~

 

처음에는 1) 재귀를 통해 중복을 포함해 모든 경우의 수를 생성하고,

2) 중복되는 경우의 수를 빼준다음

3) sort를 한번 해주고 각각 이웃하는 선분을 비교했으나 시간초과가 걸렸다. 

 

sort 해주는 것이 시간복잡도를 증가시키는 것 같아 그것을 제거했으나 여전히 시간초과...

그래서 해설을 봤다.

 

여기에서는 중복을 포함해 모든 경우의 수를 생성하지 않고

재귀를 두 가지 조건으로 돌려 문제 조건을 만족시켰다. 

 

def recursion(cnt):
    global candidate
    if cnt == n:
        if len(line_bag) > candidate and not check_connect(line_bag):
            candidate = len(line_bag)
        return

    line_bag.append(lines[cnt])
    recursion(cnt + 1)
    line_bag.pop()
    recursion(cnt + 1) # 여기

 

맨 마지막 줄이 결정적이었는데, 그 줄이 없다면 

3
1 2
3 4
5 6

1 [[1, 2]]
1 [[1, 2], [3, 4]]
1 [[1, 2], [3, 4], [5, 6]]

이렇게 까지 밖에 안 가는 데 마지막 줄에

pop 한 이후에도 다시 재귀로 들어가게 하면서 count는 올려주는 방법으로 (2로 시작하는 줄)

모든 조합을 만들어 낼 수 있었다.

1 [[1, 2]]
1 [[1, 2], [3, 4]]
1 [[1, 2], [3, 4], [5, 6]]
2 [[1, 2], [3, 4]]
2 [[1, 2]]
1 [[1, 2], [5, 6]]
2 [[1, 2]]
2 []
1 [[3, 4]]
1 [[3, 4], [5, 6]]
2 [[3, 4]]
2 []
1 [[5, 6]]
2 []

또 한 번 새로운 방법을 배워간다!!

 

[문제 풀이 코드]

 

import sys

# input 처리
n = int(sys.stdin.readline())
lines = []
line_bag = []
candidate = 0

for _ in range(n):
    lines.append(list(map(int, sys.stdin.readline().split())))


def connected(seg1, seg2):
    x1, y1 = seg1
    x2, y2 = seg2
    return (x1 <= x2 <= y1) or (x1 <= x2 <= y1) or (x2 <= x1 <= y2) or (x2 <= y1 <= y2)


def check_connect(bag):
    for i in range(len(bag)):
        for j in range(i + 1, len(bag)):
            if connected(bag[i], bag[j]):
                return True
    return False


def recursion(cnt):

    global candidate
    if cnt == n:
        if len(line_bag) > candidate and not check_connect(line_bag):
            candidate = len(line_bag)
        return

    line_bag.append(lines[cnt])
    recursion(cnt + 1)
    line_bag.pop()


recursion(0)
print(candidate)