[이취코] DP 실전 - 못생긴 수 / Python
2,3,5만을 약수로 가지는 합성수를 못생긴 수라고 한다1은 못생긴 수라고 가정한다n번째 못생긴 수를 구하자 처음 아이디어 접근 일단 1,2,3,4,5가 못생긴 수인건 맞으니dp = [1,1,1,1,1] 로 세팅한다 n이 5보다 작은 경우에는 n을 return하도록 한다 그 이상은 dp를 구한다 못생긴 수를 세는 cnt와 현재 수를 나타내는 cur 변수를 둔다while문을 돌며 cnt가 n에 도달하면 멈춘다 while문 내에서 현재 살펴보는 수를 1씩 증가시킨다현재 수가 2or3or5로 나누어떨어지고, dp[i//(2or3or5)-1]값이 1이라면그 수는 2,3,5만을 인수로 가진다는 뜻못생긴 수 cnt를 증가시키고, dp에도 못생긴 수라는 뜻으로 1을 삽입 그 외에는 0을 삽입한다 마지막에 현재 숫자를..
