[이것이 코딩 테스트다] 못생긴 수 - 다이나믹 프로그래밍
문제못생긴 수란 오직 2, 3, 5 만을 소인수로 가지는 수를 의미합니다.1은 못생긴 수라고 가정합니다.이때 n 번째 못생긴 수를 찾는 프로그램을 작성하십시오. 입력 조건첫 째 줄에 n이 입력됩니다.(1 출력 조건n 번째 못생긴 수를 출력합니다.해결 과정첫번째 아이디어이다.1, 2, 3, 4, ..., n 순으로 탐색한다. 다시 말하면 1부터 n까지 선형탐색을 한다. 현재 위치의 수를 소인수분해해서 못생긴 수인지 파악하는 방법이다.하지만 소인수분해를 계산해야하는 시간적 번거로움이 생긴다.2, 3, 5로 나머지가 0이 아닐 때까지 나누는 함수를 만드는 것은 금방이다. 하지만 991번째 못생긴 수 부터 1000번째 못생긴 수를 보면, 소인수분해 계산에서 시간초과에 걸릴 수 있다고 생각했다.* [ ..., 5..
2024. 9. 7.
