2로 나누어 떨어지는 정수를 짝수(even number)라고 합니다. 이 글에서는 숫자 n이 주어졌을 때, 자릿수의 합이 짝수인 n번째 숫자를 찾는 방법을 다룹니다. 자릿수의 합이 짝수인 첫 다섯 개의 숫자는 2, 4, 6, 8, 11입니다. 예를 들어 다음과 같습니다.
입력 : n = 5 출력 : 11 설명 : 자릿수의 합이 짝수인 처음 5개의 숫자는 2, 4, 6, 8, 11이며, 즉 5번째 숫자는 11입니다. 입력 : n = 12 출력 : 24
문제 해결 접근 방식
주어진 문제를 해결하기 위한 두 가지 서로 다른 방법을 소개합니다.
1. 단순 접근법(Naive Approach)
가장 직관적인 해결 방법은 1부터 차례대로 숫자를 탐색하면서 각 숫자의 자릿수 합이 짝수인지 확인하는 것입니다. 자릿수의 합이 짝수라면 카운터를 1씩 증가시키고, 카운터 값이 n과 같아질 때까지 이 과정을 반복합니다. 최종적으로 도달한 n번째 숫자가 바로 우리가 찾는 답이 됩니다. 다만 이 방법은 큰 n값에 대해 많은 연산 시간이 필요하다는 단점이 있습니다.
2. 효율적인 접근법(Efficient Approach)
더 효율적인 방법은 자릿수의 합이 짝수인 초반 숫자들을 나열해 보고 규칙성(패턴)을 찾아내는 것입니다. 자릿수의 합이 짝수인 처음 20개의 숫자는 다음과 같습니다.
2, 4, 6, 8, 11, 13, 15, 17, 19, 20, 22, 24, 26, 28, 31, 33, 35, 37, 39, 40
이 숫자들을 관찰하면 흥미로운 패턴을 발견할 수 있습니다. n의 일의 자리 숫자가 0~4 사이라면 n번째 숫자는 2 × n이 되고, 일의 자리 숫자가 5~9 사이라면 n번째 숫자는 (2 × n) + 1이 됩니다. 이 공식을 활용하면 반복문 없이 O(1)의 시간 복잡도로 답을 즉시 구할 수 있습니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int main () {
long long int n = 13;
long long int result;
// n의 마지막 자릿수(일의 자리) 구하기
int last_digit = n % 10;
// 마지막 자릿수가 0~4 사이인지 확인
if (last_digit >= 0 && last_digit <= 4)
result = 2 * n;
// 마지막 자릿수가 5~9 사이인 경우
else
result = (2 * n) + 1;
cout << "자릿수의 합이 짝수인 n번째 숫자: " << result;
return 0;
}
실행 결과
자릿수의 합이 짝수인 n번째 숫자: 26
코드 설명
- 나머지 연산자(%)를 사용해 n의 마지막 자릿수를 구하고, 해당 값이 0~4 사이에 있는지 확인합니다. 조건을 만족하면 result 변수에 2 × n을 저장합니다.
- 그렇지 않은 경우, 즉 마지막 자릿수가 5~9 사이라면 result 변수에 (2 × n) + 1을 저장합니다.
- 마지막으로 result 변수에 저장된 값을 출력하여 자릿수의 합이 짝수인 n번째 숫자를 구합니다.
결론
이 글에서는 자릿수의 합이 짝수인 n번째 숫자를 찾는 문제를 다루었으며, 단순 탐색 방식과 수학적 패턴을 활용하는 효율적인 방식, 두 가지 해결 방법을 살펴보았습니다. 특히 패턴 기반 접근법을 사용하면 불필요한 반복 계산 없이 매우 빠르게 답을 구할 수 있습니다. 동일한 로직은 C, Java, Python 등 다른 프로그래밍 언어로도 손쉽게 구현할 수 있습니다. 이 글이 여러분의 코딩 문제 해결에 도움이 되기를 바랍니다.