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
'개발일지 > Algorithm' 카테고리의 다른 글
| 백준 - 3273 두 수의 합 [투포인터] (1) | 2023.10.21 |
|---|---|
| 백준 - 9251 LCS [LCS] (0) | 2023.10.20 |
| 백준 - 11053 가장 긴 증가하는 부분 수열 [LIS] (1) | 2023.10.18 |
| 백준 - 1520 내리막 길 [DP] (0) | 2023.10.17 |
| 백준 - 1937 욕심쟁이 판다 [DP] (0) | 2023.10.16 |
