Program Programming Programmer

문제: https://www.acmicpc.net/problem/1014 알고리즘 책에서 봤던 network flow (Ford Fulkerson algorithm) 방법으로 bipartite matching 문제를 푸는 방법을 참고하여 풀어봤습니다.알고리즘 책에 예제로 있던 문제는 비숍을 놓는 문제로 놓여지는 비숍에 따른 두 개의 대각선으로 id를 정했다면 이 문제는 가로 줄의 홀수, 짝수 열로 id를 정해야되고 같은 홀수줄 또는 짝수줄은 절대 공통 원소를 가질 수 없으므로 이분 그래프가 됩니다. my solvingc++1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556..

문제: https://www.acmicpc.net/problem/1012 dfs (깊이 우선 탐색) 문제입니다. 처음에 UNIT 값을 50으로 주고 풀어 문제 난이도에 비해 상당히 절 헤매게 만든 문제입니다. getNextPosition 에서의 계산 방식 때문에 UNIT 값을 51 이상으로 주어야되었었네요. my solvingc++1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192#include #include #include #include u..

문제: https://www.acmicpc.net/problem/1013 100+ 1+ 이후에 01 이 오는 경우와 100+ 1+ 이 다시 반복되는 경우에 대한 판별 때문에 Deterministic finite automaton 라는 개념의 풀이 방법이 필요합니다.https://en.wikipedia.org/wiki/Deterministic_finite_automaton my solvingc++12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485868788899091929..

문제: https://www.acmicpc.net/problem/1011 마지막 단계에서는 속도가 1이어야 되기 때문에 속도가 올라갈 때 마다 속도를 줄일 구간을 생각해서 풀면 간단하게 풀 수 있는 문제네요. my solvingc++1234567891011121314151617181920212223242526272829303132333435363738394041424344#include #include #include #include using namespace std;typedef long long ll; int bruteForce(ll remaining, int speed){ int ret = 0; while (remaining > 0) { if (remaining > speed * 2) { ret ..

문제: 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/1009 a 의 b 승의 마지막 자리의 값을 구하는 문제입니다. 우선 b가 최대 1,000,000 이기 때문에 모든 값을 저장할 수 없으므로 마지막 자리의 값만 남겨두어 계산을 하고 실제로 0~9를 제곱하다보면 최대 4개의 패턴으로 묶이는 것을 확인할 수 있습니다. 이 점을 이용해 시간복잡도를 줄일 수 있습니다. my solvingc++1234567891011121314151617181920212223242526272829303132333435363738#include #include #include #include using namespace std; int main(){ int cases; cin >> cases; for (int i =..

문제: https://www.acmicpc.net/problem/1008 double 의 모든 자리를 출력하기 위해cout 의 precision,fixed 와 limits 라이브러리의 std::numeric_limits 을 사용했습니다. my solvingc++12345678910111213141516#include #include #include #include using namespace std; int main(){ double a, b; cin >> a >> b; cout.precision(numeric_limits::max_digits10); cout

문제: 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 좌표들을 구해둔다면즉 예에서는..

문제: https://www.acmicpc.net/problem/1006 처음에는 brute force 로 풀어봤으나 최대 N 의 값이 10000 이기 때문에 시간이 초과됩니다. 따라서 memoization 방법을 사용해야 되는데 그러기 위해서는 1번부터 N - 1 까지 순차적으로 우측 방향으로만 진행하며 경우의 수를 찾아야 됩니다. 이때 문제는 1번과 N + 1번에서 왼쪽으로 진행되는 방향은 고려되지 않는다는 점이 문제입니다. 해당 부분에 대해 한참 고민을 하다 사이트의 질문 검색을 통해 하드 코딩을 하는 방법으로 조언을 얻어 해결 했습니다. my solvingc++12345678910111213141516171819202122232425262728293031323334353637383940414243..

문제: https://www.acmicpc.net/problem/1005 처음에는 bruteForce 방법으로 풀었다가 시간 초과! 그래서 memoization 방법을 이용해 시간 복잡도를 줄여 풀었습니다. my solvingc++12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273747576777879808182838485#include #include #include #include #include #include using namespace std; multimap techTrees;vector buildin..