Program Programming Programmer

문제: https://www.acmicpc.net/problem/1038 완전탐색으로 문제를 풀 경우 시간 복잡도가 크기 때문에 다른 방법으로 접근을 해야 했습니다.만약 n이 19일 경우0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 21, 30, 31, 32, 40, 41, 42, 43위와 같은 순서대로 43이 정답이 되는데, 10 이후의 숫자들을 자세히 살펴보면앞자리가 4일 경우 올 수 있는 가짓수는 0, 1, 2, 3 사이의 숫자들 중 한 가지를 고르는 순서 없는 조합의 가짓수임을 알 수 있습니다.즉, 이항계수로 구할 수가 있습니다.따라서 다음과 같이 이항계수를 사용하여 시간 복잡도를 줄여 풀어볼 수 있습니다. 12345678910111213141516171819202122232..

문제: https://www.acmicpc.net/problem/1010 n 개 에서 k 개를 고르는 (순서 없는)조합의 가짓수를 구하는 이항계수를 구하는 문제입니다.특히 다리가 겹치면 안된다는 조건이 있기에 순서에 무관하게 조합의 개수를 구해야 됩니다. 이항 계수를 구하는 방법은 이전에 포스팅 한 방법을 사용해 구했습니다. my solvingc++12345678910111213141516171819202122232425262728293031323334353637#include #include #include #include using namespace std; const int MAX = 31; int cache[MAX][MAX]; int getBinomialCoefficient(int n, int k..

문제: https://www.acmicpc.net/problem/1007 만약 (x1, y1), (x2, y2), (x3, y3), (x4, y4) 이란 점들이 있고 이 중(x1, y1), (x3, y3)을 선택하여 벡터를 만들고 (x2, y2), (x4, y4) 를 선택해 벡터를 만들었다고 할 때,첫 번째 벡터는 (x1 - x3, y1 - y3) 으로 표현할 수 있고 두 번째 벡터는 (x2 - x4, y2 - y4) 으로 표현할 수 있습니다.그리고 두 벡터의 합은(x1 + x2 - (x3 + x4) , y1 + y2 - (y3 + y4)) 이라 할 수 있습니다. 여기서 만약 x1 + x2 + x3 + x4 를 미리 구해두고벡터가 되는 점의 한 쪽들을 선택하며 그 점들의 x 좌표들을 구해둔다면즉 예에서는..