문제 개요
이 문제에서는 정수 N이 주어지며, 숫자 4와 7로만 구성된 수열을 다룹니다.
수열은 다음과 같은 규칙으로 진행됩니다: 4, 7, 44, 47, 74, 77, …
즉, 두 자릿수(4와 7)만 허용되는 이 수열에서 n번째 원소를 찾는 것이 과제입니다.
예제로 문제 이해하기
입력
N = 4
출력
47
설명
수열: 4, 7, 44, 47, …
N이 4이므로 수열의 네 번째 값인 47이 결과가 됩니다.
해결 접근 방법
가장 간단한 해결 방법은 N번째 항까지 수열을 직접 만들어 가는 것입니다. 이 수열에는 규칙성이 있어, 현재 수의 마지막 자릿수가 7이라면 인접한 수들의 마지막 자릿수는 4가 됩니다.
따라서 첫 번째와 두 번째 항부터 시작하여 차례대로 다음 원소를 계산해 나갈 수 있습니다.
이를 위해 크기가 N+1인 배열 series[]를 생성합니다.
series[1]에 4 저장 series[2]에 7 저장
그다음 3번째 항부터 N번째 항까지, 인덱스 i에 대한 값을 다음 규칙으로 구합니다.
i가 홀수이면: series[i] = series[i/2] * 10 + 4 i가 짝수이면: series[i] = series[i/2] * 10 + 7
이렇게 하면 각 항은 이전 항에 4 또는 7을 이어 붙이는 방식으로 생성되며, N번 반복 후 series[N] 값을 반환하면 됩니다.
솔루션 구현 코드
#include <iostream>
using namespace std;
int findNthSeriesElement(int N) {
int series[N+1];
series[1] = 4;
series[2] = 7;
for (int i=3; i<=N; i++) {
if (i%2 != 0)
series[i] = series[i/2]*10 + 4;
else
series[i] = series[(i/2)-1]*10 + 7;
}
return series[N];
}
int main() {
int N = 9;
cout<<"The "<<N<<"th element of the array is "<<findNthSeriesElement(N);
return 0;
}출력 결과
The 9th element of the array is 474
코드 설명 및 복잡도 분석
위 코드는 배열 기반 동적 계획법(DP) 방식으로 수열을 구성합니다. 홀수 인덱스일 때는 부모 항 뒤에 4를 붙이고, 짝수 인덱스일 때는 7을 붙이는 규칙을 활용합니다.
- 시간 복잡도: O(N) — N번째 항까지 한 번씩 순회하며 계산합니다.
- 공간 복잡도: O(N) — 크기 N+1의 배열을 사용합니다.
또한, 각 항을 이진수처럼 취급하여(4를 0, 7을 1로 대응) 비트 연산으로 직접 계산하는 최적화 기법도 존재합니다. 이 경우 추가 배열 없이 O(N) 시간에 상수 공간으로 해결할 수 있습니다.