반응형
SMALL
17505번 링고와 수열
-
17505번 링고와 수열알고리즘 2023. 2. 9. 16:39
문제 설명 이번 문제는 1~N까지의 수로 이루어진 수열 A에서 i A[j]인 개수가 K개일 수 있는지 구하는 문제입니다. K개인 수열이 있다면 해당 수열을 출력(조건을 만족하는 수열의 개수가 여러 개라면 한 개만 출력)합니다. K개인 수열이 없다면 -1을 출력합니다. 문제 풀이 아이디어 문제의 조건을 이용하는 방법 수열 A에서 i A[j]를 만족할 수 있는 경우는 앞쪽의 원소가 뒤쪽의 원소보다 큰 경우입니다. N=5인 경우에 대한 예시를 들어보도록 하겠습니다. (A = [1,2,3,4,5]) 위의 조건을 만족하는 개수가 0인 경우를 생각해보면 앞쪽의 원소가 뒤쪽의 원소보다 항상 작은 경우입니다. -> [1, 2, 3, 4, 5] 위의 조건을 만족하는 개수가 ..