C++로 홀수를 제거한 범위 [1, n]에서 k번째로 작은 수 찾기

이 문제에서는 두 개의 정수 n과 k가 주어집니다. 우리가 해야 할 일은 1부터 n까지의 범위에서 모든 홀수를 삭제한 뒤, 남아 있는 수들 중 k번째로 작은 수를 찾는 것입니다.

즉, 짝수만 남게 된 범위 [1, n] 안에서 k번째로 작은 값을 구해야 합니다.

예를 들어, 범위 [1, 5]에서 홀수를 모두 지우면 남는 수는 2와 4뿐입니다.

문제 이해를 위한 예시

입력: n = 12, k = 4

출력: 8

설명:

범위 [1, 12]에 포함된 짝수는 다음과 같습니다.

2, 4, 6, 8, 10, 12

이 중 4번째로 작은 수는 8입니다.

해결 접근 방법

풀이 방법은 매우 간단합니다. 홀수를 모두 제거하면 남는 수는 짝수뿐이므로, 결국 1부터 n 사이의 짝수 나열에서 k번째 원소를 찾는 것과 같습니다. 짝수는 2부터 시작해 2씩 증가하기 때문에 다음 공식으로 바로 계산할 수 있습니다.

k번째 수 = 2 × k

단, 한 가지 주의할 점이 있습니다. 구하려는 값인 2×k가 n보다 커지면 해당 값은 범위 [1, n] 안에 존재하지 않으므로, 답을 구할 수 없다는 메시지를 출력해야 합니다. 따라서 코드에서는 n > 2*k 조건을 먼저 확인합니다.

솔루션 동작을 보여주는 프로그램

예제 코드

#include <bits/stdc++.h>
using namespace std;

int main() {
   
   int n = 124, k = 12;
   if(n > 2*k){
      cout<<"k번째로 작은 수는 "<<(2 * k);  
   }
   else
      cout<<"k번째로 작은 수를 찾을 수 없습니다";
   return 0;
}

출력 결과

k번째로 작은 수는 24

코드 설명

위 프로그램에서 n = 124, k = 12로 설정했습니다. 먼저 n > 2*k, 즉 124 > 24 조건이 참인지 확인합니다. 참이므로 공식에 따라 2×k = 24를 출력합니다. 만약 k가 너무 커서 2×k가 n을 초과한다면, 범위 내에 존재하지 않는 값을 요구하는 것이므로 답을 찾을 수 없다고 알려줍니다.

이 풀이의 시간 복잡도는 단순한 산술 연산만 수행하므로 O(1)이며, 추가적인 메모리 사용도 없어 매우 효율적입니다.