숫자 n이 있다고 가정합니다. n번째 못생긴 숫자를 찾아야 합니다. 못생긴 숫자는 소인수가 2, 3, 5뿐인 숫자라는 것을 알고 있습니다. 따라서 10 번째 를 찾으려면 못생긴 숫자의 경우 처음 몇 개의 못생긴 숫자는 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 등이므로 출력은 12가 됩니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다.
- 크기(n + 1)의 배열 v 정의
- n이 1과 같으면 다음과 같습니다.
- 1을 반환
- 둘 :=2, 셋 :=3, 다섯 :=5
- twoIdx :=2, threeIdx :=2, fiveIdx :=2
- 초기화 i:=2의 경우 i <=n일 때 업데이트(i를 1만큼 증가), 다음을 수행합니다.
- curr :=최소 2, 3, 5
- v[i] :=커
- curr이 2와 같으면 다음과 같습니다.
- 두 :=v[twoIdx] * 2;
- (2Idx 1 증가)
- curr이 3과 같으면 다음과 같습니다.
- 3 :=v[threeIdx] * 3
- (3Idx를 1씩 증가)
- curr이 5와 같으면 다음과 같습니다.
- 5 :=v[fiveIdx] * 5
- (5Idx 1 증가)
- 반환 v[n]
더 나은 이해를 위해 다음 구현을 살펴보겠습니다.
예시
#include
using namespace std;
class Solution {
public:
int nthUglyNumber(int n) {
vector v(n + 1);
if(n == 1){
return 1;
}
int two = 2, three = 3, five = 5;
int twoIdx = 2;
int threeIdx = 2;
int fiveIdx = 2;
for(int i = 2; i <= n; i++){
int curr = min({two, three, five});
v[i] = curr;
if(curr == two){
two = v[twoIdx] * 2;;
twoIdx++;
}
if(curr == three){
three = v[threeIdx] * 3;
threeIdx++;
}
if(curr == five){
five = v[fiveIdx] * 5;
fiveIdx++;
}
}
return v[n];
}
};
main(){
Solution ob;
cout << (ob.nthUglyNumber(15));
} 입력
15
출력
24