[Python] 백준 2565 전깃줄

https://www.acmicpc.net/problem/2565

2565번: 전깃줄

<알고리즘을 아직 안배워서, 관련내용은 없습니다>

문제분석

두 전봇대 A와 B가 있는데, 전선을 겹치치않게 하려면 최소 몇개를 빼야 하는가?

해결 아이디어-1(실패함)
나만 이생각한줄 알았는데, 검색해보니 그냥 사람이라면 떠오르는 보편적인 아이디어였다..

가장 많이 겹치는 전깃줄부터 제거.

예시도 한번에 통과하길래...그냥 프리패스일줄 알았으나...

어림도 없다고 합니다

이유를 게시판에서 반례찾다가 알게되었다
https://www.acmicpc.net/board/view/84972

글 읽기 - 2565 전깃줄 반례 공유

같은 수만큼 겹쳐진 전깃줄이 있으면...꽤 곤란해진다.

케이스를 나눠서 해결하려 했으나, 도저히 엄두가 안나서 접고 다른방법으로 풀기로했다(2457정원 풀때 케이스 전부나눠도 안풀리길래 이방법은 앞으로 지양...)

해결과정

전깃줄 사진을 보면 알겠지만, 일대일함수...고등학교때 배운 내용이 떠오르게끔 한다. 그래서 일단 좌표평면에

왼쪽을X,오른쪽을Y로 하고 1>3번전깃줄을 (1,3)으로 그려서 나타내보기로 했다.

or은 두 점중 아무거나 없에도 큰 덩어리에 들어갈 수 있게됨. 파란 덩어리 입장에선 두 점중 하나만 취하면 됨.

증가함수를 그리는 전선들만 남겨야 하고, 최대한 적은 전선을 없에야 하므로

중요!

주어진 점들로 증가함수 덩어리들을 만들어서, 가장 큰 덩어리를 제외한 모든 점들을 지운다. 

이걸 코드로 나타내기 위해서 입력받은 값들을x기준으로 정렬시켜주었다. 이후 하나씩 탐색해나간다.

각 점 기준, 앞점들과 덩어리를 이룰 수 있는 숫자를 저장시켜주기 위해 전깃줄 수만큼 원소를 가지고있는 1차원 배열temparr을 만들어줬다. 기본적으로 자기 자신은 덩어리의 필수요소이므로, 1로 초기화시켜주었다.

탐색한 점 기준 본인 앞 값들중 자신과 덩어리를 이룰 수 있는 점이 있으면, 그 점과 같은 위치의 temparr을 본인의 temparr에 더해주었다. 이를 반복한 후 가장 큰 덩어리는 temparr중 가장 큰 수이므로 전깃줄수-max(temparr)이 답이다.

n=int(input())
arr=[]#전깃줄연결 저장
for i in range(n):
    temp=input().split()
    arr.append([int(temp[0]),int(temp[1])])#전깃줄을 2차원배열로 저장,[[왼쪽칸,오른쪽칸]....]
arr.sort(key=lambda x:(x[0]))#첫번째값기준 정렬
temparr=[1 for _ in range(n)]#덩어리들확인하기위해
for i in range(len(arr)):
    for k in range(i):
        if arr[i][1]>arr[k][1]:#어차피 x는 오름차순정렬, 따라서 y값만 비교하면됨
            if temparr[i]<temparr[k]+1:
                temparr[i]=temparr[k]+1
print(len(arr)-max(temparr))#가장 큰 덩어리를빼면, 빼야할 전선들만 남음









# 가장 많이 꼬인전깃줄순으로 보는법, 물론틀림
#n=int(input())
# arr=[]#전깃줄연결 저장
# for i in range(n):
#     temp=input().split()
#     arr.append(tuple([int(temp[0]),int(temp[1])]))#튜플로해야 키값으로쓸수있음
# arr.sort(key=lambda x:(x[0]))
# tuple1=tuple(arr)
# count=0#교차점 수
# num=0#전깃줄 뺀 값
# dictionary={}#배열
# for i in range(len(arr)):#전깃줄을 배치하고, 그 후에 앞과 비교
#     cross=0
#     dictionary[tuple1[i]]=[cross]
#     for k in range(len(arr)):
#         if (arr[i][0]>arr[k][0] and arr[i][1]<arr[k][1])or(arr[i][0]<arr[k][0] and arr[i][1]>arr[k][1]):
#             dictionary[tuple1[i]][0]+=1
#             dictionary[tuple1[i]].append([arr[k][0],arr[k][1]])
#             count+=1
# #dictionary는 {전깃줄:[겹치는수,[겹치는줄1],[겹치는줄2].....]}여기서 벨류 첫째항을 기준으로 정렬
# #예시
# #{(1, 8): [5, [2, 2], [4, 1], [6, 4], [7, 6], [9, 7]], (3, 9): [4, [4, 1], [6, 4], [7, 6], [9, 7]],
# dictionary=dict(sorted(dictionary.items(),key=lambda x:x[1][0],reverse=True))#겹치는거큰수부터
# for i in dictionary:#i는 딕셔너리 키갑의미
#     #dictionary에 있는 전선에 가서 벨류index0값 하나씩 빼기(0이 아니면)
#     if dictionary[i][0]!=0:#i키에 벨류(배열) index0(겹치는수)
#         count-=dictionary[i][0]*2#겹치는전깃줄확인
#         num+=1#전깃줄 한개 뺀거 의미
#         for k in range(len(dictionary[i])-1):#두번째값부터마지막까지 전깃줄정보있음
#             dictionary[tuple(dictionary[i][k+1])].remove(list(i))
#             dictionary[tuple(dictionary[i][k+1])][0]-=1
#         #본인도빼야됨
#         dictionary[i][0]=0
#         dictionary=dict(sorted(dictionary.items(),key=lambda x:x[1][0],reverse=True))#정렬한번다시함
#     elif count==0:
#         break
#     print(dictionary)
# print(num)