글 읽기 - 2565 전깃줄 반례좀 찾아주세요

tkqlzz 7년 전 0

이렇게 푸는게 아닌건지 잘 모르겟습니다

ㅠㅜㅠ

루프가 한번 돌때마다 각 전기줄이 겹치는 개수를 체크한다음 겹치는 개수의 최대값이 0이 될때까지 반복하도록 짯습니다.

개수가 0이 아니면 겹치는 개수가 제일 많은 전기줄을 제거하는 방식으로 했습니다.

import sys
read = sys.stdin.readline

n = int(read())
arr = [0] * n
cache = [0] * n

for i in range(n):
    a, b = map(int, read().split())
    arr[i] = (a, b)

res = 0
while True:
    for i in range(n):
        cnt = 0
        for j in range(n):
            if i == j:
                continue
            a, b = arr[i]
            c, d = arr[j]
            if (a > c and b > d) or (a < c and b < d):
                pass
            else:
                cnt += 1
        cache[i] = (cnt, i)

    cnt, i = max(cache)
    if cnt == 0:
        break
    arr.pop(i)
    cache.pop()
    n -= 1
    res += 1

print(res)

doju 7년 전 4

가장 많이 겹치는 것이 여러 개일 경우 뭘 먼저 지우느냐에 따라 답이 달라질 수 있습니다.

tkqlzz 7년 전 0

아 그런경우를 생각못했네요 감사합니다

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

문제

문제

출처

ICPC

2565 전깃줄 반례좀 찾아주세요

tkqlzz 7년 전 0

doju 7년 전 4

tkqlzz 7년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말