코딩고치

1. 문제 주소 15988번: 1, 2, 3 더하기 3 각 테스트 케이스마다, n을 1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다. www.acmicpc.net 2. 문제 정수 n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력하는 문제이다. n을 나타내는 방법은 n-1을 나타내는 방법에서 1을 더하고 n-2를 나타내는 방법에서 2를 더하고 n-3을 나타내는 방법에서 3을 더하면 된다. 따라서 n을 나타내는 방법의 수는 n-1, n-2, n-3을 나타내는 방법을 모두 더해주면 된다. 3. 소스 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 #include using namespace std; long long di..

1. 문제 주소 https://www.acmicpc.net/problem/2225 2225번: 합분해 첫째 줄에 답을 1,000,000,000으로 나눈 나머지를 출력한다. www.acmicpc.net 2. 문제 0부터 N까지의 정수를 K개 더하여 N이 나오는 경우의 수를 구하는 문제이다. [K][N]인 경우에 다음과 같은 식이 된다. $$x_{1}+x_{2}+x_{3}+...+x_{K}=N$$ 이것을 다시 써보면 $$x_{1}+x_{2}+x_{3}+...+x_{K-1}+X = N$$ 로 나타낼 수 있으며 이 식은 [K-1][N-X] (X > n >> k; dp[0][0] = 1LL; for (int i = 1; i

1. 문제 주소 1699번: 제곱수의 합 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 www.acmicpc.net 2. 문제 자연수 N을 제곱수들의 합으로 나타낼 때 최소 항의 개수를 구하는 문제이다. 가장 마지막에 더해지는 숫자가 무엇인지 확인하면 쉽게 풀 수 있다. 예를 들어 i를 제곱수의 합으..

1. 문제 주소 1912번: 연속합 첫째 줄에 정수 n(1 ≤ n ≤ 100,000)이 주어지고 둘째 줄에는 n개의 정수로 이루어진 수열이 주어진다. 수는 -1,000보다 크거나 같고, 1,000보다 작거나 같은 정수이다. www.acmicpc.net 2. 문제 연속된 숫자들의 합 중에서 가장 큰 합을 구하는 문제이다. 숫자를 더해나가다가 음수를 만났을 때 이전의 연속합에 더할지 아니면 버리고 새로 시작할지를 생각하면 쉽게 풀 수 있는 문제이다. 3. 소스코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 #include #include #include using namespace std; int main() { int n; cin >> n; vector..