728x90 반응형 LIS2 2022.02.09 [백준] C# 전깃줄 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 풀이 최소한의 겹쳐진 전깃줄을 제거하여 전부 겹치지 않게 만들라고 하는 문제이다. 이 문제를 반대로 생각하면 겹치지 않은 전깃줄의 최장증가수열을 찾은 뒤 전체 전깃줄의 수에서 빼면 제거해야하는 최소한의 전깃줄의 갯수를 구할 수 있다. 주어진 배열을 arr배열에 담고 최장 증가수열의 길이를 담을 count배열을 만들어 전체에 1을 설정해준다.(자기 자신만 있어도 최장 증가수열은 1이기 때문) 그리고 이중f.. 2022. 2. 9. 2022.02.08 [백준] C# 가장 긴 바이토닉 부분 수열 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 풀이 이 문제는 1~n까지의 LIS를 구해서 upper배열에 저장하고 반대로 n~1까지 LIS를 구해서 lower배열에 저장했다. num의 배열에 순서대로 하면 최장 증가수열이고, 반대로 하면 최장 감소 수열이기 때문이다. 그리고 upper[i] + lower[i] -1 (-1을 해주는 이유는 i가 겹치기 때문)을 해주어 답을 구했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 .. 2022. 2. 8. 이전 1 다음 728x90 반응형
