글 읽기 - 이 방식은 안되는걸까요

sibaek 2년 전 0

잘 안돼서 알아보던 중 LIS 알고리즘을 활용하면 된다는 사실을 알 수 있었는데요,

일단 그 사실을 알기 전 작성한 코드는 어디에 문제가 있는 것인지 잘 모르겠습니다.

코드는

1. 두 전깃줄 번호 간격차가 큰 순으로 정렬한다.

2. 자연수 1부터 1씩 더하면서 각 전깃줄 범위를 탐색한다. 자연수가 두 개 이상의 전깃줄에 소속된다면 겹치는 줄이 있는 것이므로 if not ok: 로 간다.

3. if not ok: 전깃줄 범위 중 자연수를 포함하는 전깃줄을 찾아 한 줄 제거한다. 제거 카운트를 1 올린다.

알고리즘 자체가 잘못된 것인지, 또는 다른 문제가 있는지 설명해 주세요.

n = int(input())

lines = []
total = 0
for _ in range(n):
    a, b = map(int, input().split())
    if max(a, b) > total:  # 최댓값 확인 (전봇대 총 위치 길이)
        total = max(a, b)
    lines.append([abs(a - b), a, b])

lines.sort(reverse=True)  # 두 수의 간격차 큰 순으로 정렬

for i in range(n):
    del lines[i][0]


cnt = 0
ix = 1
while True:  # total 까지 ix를 1씩 값 올려 탐색한다.
    ok = True
    px = 0
    if not lines:
        break
    if ix > total:
        break

    for j in range(n - cnt):  # 한 값마다 전체 전깃줄 탐색
        temp_list = []

        if abs(min(lines[j]) - max(lines[j])) == 1:
            temp_list.append(min(lines[j]))
            temp_list.append(max(lines[j]))
        elif abs(min(lines[j]) - max(lines[j])) == 0:
            temp_list.append(lines[j][0])
        else:
            for k in range(min(lines[j])+1, max(lines[j])):
                temp_list.append(k)
        
        if ix in temp_list:
            px += 1
        if px >= 2:  # 중복 있으면
            ok = False
            break

    if not ok:
        #숫자 범위에서 ix 값이 있는 라인을 찾아서 제거해야 함.
        for j in range(n - cnt):
            temp_list = []

            if abs(min(lines[j]) - max(lines[j])) == 1:
                temp_list.append(min(lines[j]))
                temp_list.append(max(lines[j]))
            elif abs(min(lines[j]) - max(lines[j])) == 0:
                temp_list.append(lines[j][0])
            else:
                for k in range(min(lines[j])+1, max(lines[j])):
                    temp_list.append(k)
            
            if ix in temp_list:
                del lines[j]
                break
        cnt += 1
        ix = 0
    else:
        ix += 1

print(cnt)

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

이 방식은 안되는걸까요

sibaek 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말