19291 [C] 1929: 소수 구하기 사실 이 문제가 Dynamic Programming로 푸는 것은 아니다. DP는 점화식을 이용하여 i번째까지 구한 것을 저장하고 이것을 i+1번째를 구할 때 이용하는 것이다. 사실 이걸 그대로 사용하고 있지는 않다. 다만 DP에 쓰이는 방법 일부를 사용하고 있다. i번째 수가 소수인지를 각각 구하는 것이 아니라 1부터 탐색을 할때 소수이면 그 수의 배수들을 따로 저장하여 소수인지 확인하면 된다. 즉 Bottom-up 방식으로 생각해서 구현하면 된다. #include int dp[1000001]; int main(void) { int m,n; scanf("%d %d",&m,&n); for(int i=2;i=m && i 2023. 8. 10. 이전 1 다음