못생긴 수

문제

못생긴 수란 2,3,5만을 소인수로 가지는 수
1은 못생긴 수라 가정
-> {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15, ...}

입력

N 입력 (1<=N<=1000)

출력

N번째 못생긴 수 출력

풀이

DP문제는 아직 풀어도 풀어도 익숙해지지 않는 것 같다ㅠㅠ

이것이 코딩테스트다 p.570쪽 참고 -> C++버전으로 구현
처음에는 2,3,5 각각의 수에 계속해서 2,3,5를 곱하는 방식으로 풀었는데, 알고보니 각각의 index(i2,i3,i5)를 증가시키면서 이전에 배열에 포함된 못생긴 수에 2,3,5를 구해서 작은값 순서대로 넣는 방식으로 구현

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int N;
	cin >> N;


	int ugly[1001];
	ugly[0] = 1;

	int i2 = 1, i3 = 1, i5 = 1;
	int two = 2, three = 3, five = 5;

	for(int i=1;i<N;i++){
    	//2,3,5의 합성수 중 최솟값 구하기
		int minTemp = min(two, three);
		minTemp = min(minTemp, five);

		ugly[i] = minTemp;

		if (minTemp == two) {
			two=ugly[i2++]*2;
		}
		if (minTemp == three) {
			three = ugly[i3++] * 3;
		}
		if (minTemp == five) {
			five = ugly[i5++] * 5;
		}

	}
	cout << ugly[N-1];
	
	return 0;
}