목록12738 (1)

MODE::CREATIVE

[백준][c++] 12738번: 가장 긴 증가하는 부분 수열 3

문제 해석 주어진 수열 안에서 가장 긴 증가하는 부분 수열의 길이를 구하는 문제 입니다. 풀이 먼저, 숫자의 개수 N을 입력받습니다. N개의 숫자를 입력받아 numbers 벡터에 저장합니다. lis라는 벡터를 생성하고 첫번째 숫자를 추가합니다. 이 벡터는 가장 긴 증가하는 부분 수열을 저장하는 데 사용됩니다. numbers 벡터의 두 번째 원소부터 마지막 원소까지 순회하며, 현재 숫자가 lis의 마지막 원소보다 크면 lis에 추가합니다. 이는 현재 숫자가 lis에 포함될 수 있음을 의미합니다. 만약 현재 숫자가 lis의 마지막 원소보다 작다면, 현재 숫자가 들어갈 수 있는 lis 내의 위치를 이진 탐색으로 찾아서 그 위치의 값을 현재 숫자로 업데이트합니다. 이는 lis를 최대한 작은 값으로 유지하면서 길..
BOJ 2024. 1. 10. 16:57
이전 Prev 1 Next 다음