백준 2565번 문제(전깃줄) 파이썬(Python) 풀이 [로밍맨]

문제 링크

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

2565번: 전깃줄

 

정답 코드는 아래와 같습니다.

import sys
 
def lis(arr, n):
  rst = [1] * n
  for i in range(1, n):
    for j in range(i):
      if arr[j] < arr[i]:
        rst[i] = max(rst[i], rst[j] + 1)
  return max(rst)
 
def solve():
  n = int(sys.stdin.readline().rstrip())
  arr = []
  for _ in range(n):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    arr.append((a, b))
  arr.sort(key = lambda x: x[0])
  l = []
  for a, b in arr:
    l.append(b)
  print(n - lis(l, n))
 
solve()
 

 

이 문제는 LIS(Longest Increasing Subsequence) 대표 예제라고 볼 수 있습니다.

LIS 문제 풀이를 미리 알고 있지 않다면 처음 보고 바로 풀어내기는 매우 어려운 문제입니다.

LIS 문제 풀이의 경우 그 내용이 어렵지 않고 짧아서 아래 풀이 영상에 포함하였습니다.

 

오해가 없어야 할 내용이 하나 있는데요.

"풀이"가 쉬운 것과 "풀이를 생각해내는 것"이 쉬운 것은 서로 다릅니다.

LIS 풀이는 분명 그리 어렵지 않고 직관적이지만, 이것을 생각해내는 것은 쉽지 않습니다.

(생각해내기도 쉬웠다면 이렇게 이름이 붙지도 않았을 것입니다)

어렵게 느껴지는 것이 당연하므로 너무 절망하지 않아도 괜찮습니다.

 

728x90

 

초등학교 때 세 자릿수 곱셈 처음 배웠을 때를 생각해봅시다.

선생님이 하는 설명만 한 번 듣고 바로 쉽다고 생각한 사람은 아무도 없습니다.

기억은 잘 안 나지만 백번 정도 반복했더니 익숙해지지 않았나요?

코딩테스트 공부도 수학 공부와 유사합니다. 지속적인 반복을 통하여 익숙해져야 합니다.

 

풀이는 아래 영상을 참고 바랍니다.

https://www.youtube.com/watch?v=wn2dyWt9ml0 

 

저작권 라이선스: CC BY (출처만 표시하면 자유롭게 이용 가능)