lis2 (c++) LIS BOJ 2565번: 전깃줄 https://www.acmicpc.net/problem/2565 2565번: 전깃줄 첫째 줄에는 두 전봇대 사이의 전깃줄의 개수가 주어진다. 전깃줄의 개수는 100 이하의 자연수이다. 둘째 줄부터 한 줄에 하나씩 전깃줄이 A전봇대와 연결되는 위치의 번호와 B전봇대와 연결되는 www.acmicpc.net 문제 개요 문제만 보면 LIS를 어떻게 이용할지 감이 안 잡히는데 겹친다는 개념을 생각해보면 답이 나온다. 전봇대는 오름차순 순서대로 두 개가 세워져있고, 그 사이 전깃줄이 있는 형태이다. 전깃줄이 겹치려면 아래의 경우를 만족해야 한다. 왼쪽에 있는 숫자가 작은 것이 연결되어있는 오른쪽 숫자가 더 클 경우 ex) 1 - 4, 2 - 1 겹침 왼쪽 전봇대가 정렬되있는 순서대로 오른쪽 전봇대에 연결된 숫자를.. 2024. 1. 18. (c++) 11054번: 가장 긴 바이토닉 부분 수열 https://www.acmicpc.net/problem/11054 11054번: 가장 긴 바이토닉 부분 수열 첫째 줄에 수열 A의 크기 N이 주어지고, 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (1 ≤ N ≤ 1,000, 1 ≤ Ai ≤ 1,000) www.acmicpc.net 문제 개요 백준 11053번의 응용문제이다. 11053번은 커지는 수열의 개수만 구했다면, 11054번은 커지는 수열과 작아지는 수열을 동시에 고려해야 한다. 나는 각 자리에서 커지는 수열의 개수와 작아지는 수열을 각각 메모이제이션을 하고, 둘을 더해주는 형식으로 풀었다. int lis(int start) { int& ret = cache[start]; if (ret != 0) return ret; ret = 1; .. 2024. 1. 16. 이전 1 다음