#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
int main()
{
int n, min = 2147000000, p2, p3, p5;
scanf("%d", &n);
vector<int> a(1501, 0);
vector<int> b;
a[1] = 1;
p2 = 1;
p3 = 1;
p5 = 1;
for(int i = 2; i <= n; i++)
{
b.push_back(a[p2] * 2);
b.push_back(a[p3] * 3);
b.push_back(a[p5] * 5);
a[i] = *min_element(b.begin(), b.end());
if(a[i] == b[0])
p2++;
if(a[i] == b[1])
p3++;
if(a[i] == b[2])
p5++;
b.clear();
}
printf("%d", a[n]);
return 0;
}1. 포인터 3개 p2, p3, p5 로 소인수로만 이루어진 vector를 만들고 그 vector의 n번째 요소를 출력하는 코드이다.
vector a의 idx가 1부터 10까지를 나타낸 것이다.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1 |
문제에서 1은 Ugly Number의 첫 번째라는 조건이 있기 때문에 a[1] = 1 이다.
p2, p3, p5를 모두 1로 초기화해준다.(곱의 항등원)
p2 포인터가 가리키는 수에는 2를, p3 포인터가 가리키는 수에는 3을, p5 포인터가 가리키는 수에는 5을 곱한다.
곱한 수를 vector b에 추가한다.
<algorithm> 라이브러리의 *min_element() 를 이용하여 vector b의 최솟값을 추출하여 a[i]에 대입한다.
a[p2] * 2 = 2
a[p3] * 3 = 3
a[p5] * 5 = 5
vector b = [2, 3, 5]
a[i] = a[2] = 2;
최솟값이 된 포인터에 1을 더해준다.
p2++;
위 과정을 거치면 아래와 같다.
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1 | 2 |
a[p2] * 2 = 2* 2 = 4
a[p3] * 3 = 3
a[p5] * 5 = 5
a[3] = 3
p3++;
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1 | 2 | 3 |
a[p2] * 2 = 2 * 2 = 4
a[p3] * 3 = 2 * 3 = 6
a[p5] * 5 = 5
a[4] = 4
p2++;
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1 | 2 | 3 | 4 |
a[p2] * 2 = 3 * 2 = 6
a[p3] * 3 = 2 * 3 = 6
a[p5] * 5 = 5
a[5] = 5
p2++;
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1 | 2 | 3 | 4 | 5 |
a[p2] * 2 = 3 * 2 = 6
a[p3] * 3 = 2 * 3 = 6
a[p5] * 5 = 2 * 5 = 10
a[6] = 6
p2++;
p3++;
| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 1 | 2 | 3 | 4 | 5 | 6 |
이후 반복
