개발일지/Algorithm
백준 - 2565 전깃줄 [LIS]
E-room
2023. 10. 19. 13:46
728x90
2565번: 전깃줄
첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는
www.acmicpc.net
1. 문제 요약
전깃줄의 좌표가 주어지고 전깃줄이 꼬여있지 않도록 하기 위해 제거해야 할 전깃줄의 최솟값을 구하시오.
2. 접근 방법
- A전봇대를 기준으로 정렬한 뒤, B전봇대 값으로 LIS를 사용하면 쉽게 답을 구할 수 있습니다.
백준 - 11053 가장 긴 증가하는 부분 수열 [LIS]
11053번: 가장 긴 증가하는 부분 수열 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열을 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부
e-room.tistory.com
참고)
문제에서 최대 전봇대수는 500개로 제한되어 있습니다.
따라서, 최대 전봇대 수만큼 미리 1차원 배열을 생성한 뒤, A값을 인덱스로 하여 B값을 해당 배열에 입력하여 사용하는 것이 시간복잡도 측면에서 좀 더 유리합니다.
3. 파이썬
n = int(input())
arr = sorted([list(map(int, input().split())) for _ in range(n)])
dp = [1] * n
for i in range(n):
for j in range(i):
if arr[i][1] > arr[j][1]:
dp[i] = max(dp[i], dp[j] + 1)
print(n - max(dp))
4. 자바
Arrays.sort(arr, Comparator.comparingInt(a -> a[0]));
int answer = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[i][1] > arr[j][1]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
answer = Math.max(answer, dp[i]);
}
System.out.print(n - answer - 1);
5. 전체 코드
728x90