16-5. 못생긴수

1. 문제

못생긴 수란 오직 2, 3, 5만을 소인수Prime Factor로 가지는 수를 의미합니다. 다시 말해 오직 2, 3, 5를 약수로 가지는 합성수를 의미합니다. 1은 못생긴수라고 가정합니다. 따라서 못생긴 수들은 {1, 2, 3, 4 ,5, 6, 8, 9, 10, 12, 15, ... } 순으로 이어지게 됩니다. 이떄, n번째 못생긴 수를 찾는 프로그램을 작성하세요. 예를 들어 11번째 못생긴 수는 15입니다.

2. 입력

• 첫째 줄에 n이 입력됩니다. (1 ≤ n ≤1,000)

3. 출력

• n번째 못생긴 수를 출력합니다.

4. 풀이

• 반복되는 규칙을 찾아서 구해주었다.
• 2, 3, 5만을 약수로 가지면 2부터 30까지 22개가 반복된다.
• (2번째 못생긴수)와 (24번째 못생긴 수)의 1의 자리 수가 같고 정확히 십의 자리는 30차이 난다.
• (i번째 못생긴수 + 30) = (i+22번째 못생긴 수)
• 그래서 22로 나눈 몫과 나머지를 구해서 계산해주었다.
• n = 1 + (22 * cnt + d)
• d = (n-1) % 22
• cnt = (n-1) // 22
• answer = cnt * 30 + d

5. 처음 풀이와 달라진 점

• 나머지 계산하는 게 조금씩 꼬였다.
• arr[d-1]도 고려해보았는데 음수가 나올 수도 있어서 배제하였다.
• 처음에 0을 추가하고 마지막 30을 제외하는 걸로 결정했다.
• 어차피 0 + 30 = 30 적절했다.

물론 책 해설은 이렇게 안 되어있었는데 이것도 되지 않을까 싶다...
해설은 O(N)이었다.
온라인 저지 없어서 확인 해볼 방법이 없다.

6. 코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int arr[22] = { 0, 2, 3, 4, 5, 6, 8, 9, 10,
		12, 14, 15, 16, 18, 20,
		21, 22, 24, 25, 26, 27, 28
		};

int main(){
	int n;
	cin >> n;
	if (n == 1) {
		cout << 1 << endl;
        return 0;
	}

	int d = (n - 1) % 22;
	int cnt = (n - 1) / 22;

	int answer = cnt * 30 + arr[d];

	cout << answer << endl;
}