number theory

https://www.acmicpc.net/problem/27519 1 ~ n 까지의 정수를 소수의 합으로 표현하는 방법의 개수를 구하는 문제이다.예를 들어 8을 표현하면1) 2 + 2 + 2 + 22) 2 + 3 + 33) 3 + 5이렇게 3가지가 존재한다.여기서 중요한 점은 3 + 5와 5 + 3을 같은 방법으로 고려한다는 점이다.이는 i == 8인 경우에 dp[i] = dp[i - 3] + dp[i - 5]가 아니라는 것을 의미한다. 이를 위해서 우선 2만으로 만들 수 있는 숫자를 카운트한다.dp[0] = 1로 선언해주고dp[i] = dp[i - 2] 로 선언해주면 i == 2인 경우 dp[2] = 1을, i == 4인 경우 dp[4] == dp[2] == 1을 저장하는데,이는 곧 4를 만들기 위해..