글 읽기 - 반례가 있을까요

04_miffy 4년 전 0

반례가 있을까요..

시간초과면 이해가가는데 ㅠㅠㅠ 왜틀렸는지 모르겟어요 ㅠㅠㅠ

import sys

class Semiconductor:
    def __init__(self, n, line):
        self.n = n
        self.inform = []
        self.connected = []
        for i in range(n):
            self.inform.append([i+1, line[i], abs(i+1-line[i])])

    def make(self):
        self.inform = sorted(self.inform, key=lambda a: a[2])
        self.connected.append(self.inform[0])

        for item in self.inform[1:]:
            # print("{} 의 차례입니다".format(item))

            if not self.isCross(item):
                # print("{}은 가능합니다".format(item))
                self.connected.append(item)
            # print("")

        return len(self.connected)



    def isCross(self, item):
        length = len(self.connected)
        # print("connected: {}".format(self.connected))
        # print("{}이 connected에 있는 것들에게 cross되는지 검사합니다".format(item))

        for i in range(length):
            c = self.connected[i]
            # print("connected: {}, 검사할 item: {}".format(c, item))

            if item[0] > c[0] and item[1] < c[1]:
                # print("cross")
                return True

            elif item[0] < c[0] and item[1] > c[1]:
                # print("cross")
                return True

            elif i == length-1:
                # print("ok")
                return False




n = int(sys.stdin.readline())
line = input().split(" ")
for i in range(n):
    line[i] = int(line[i])
s = Semiconductor(n, line)
print(s.make())

nahwasa 4년 전 0

그쵸 틀렸으니 반례가.. 있죠!

10
1 10 2 9 3 8 4 7 5 6
답 : 6
출력 : 5

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

문제

문제

출처

ICPC

반례가 있을까요

04_miffy 4년 전 0

nahwasa 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말