Program Programming Programmer

문제: https://www.acmicpc.net/problem/1017 우선 에라토스테네스의 체 방법으로 2000 까지 소수를 구해놓고 앞의 1014번 문제에서 사용한적이 있던 network flow (Ford Fulkerson algorithm) 방법으로 bipartite matching 문제를 푸는 방법을 이용하여 푼 문제입니다.처음에 이분 매칭(bipartite matching) 의 조건을 구성하는 것이 생각하기 어려운 부분일 수 있는데 주어진 숫자를 짝수와 홀수로 나눠 이분 그래프를 만드는 것이 중요합니다. 짝수와 짝수 또는 홀수와 홀수로는 무조건 짝수값이 나오기 때문에 소수가 절대 될 수 없고 이 점 때문에 이분 그래프가 성립이 될 수 있는거죠.그리고 첫 번째 주어진 값과 연결될 수 있는 값을..

문제: https://www.acmicpc.net/problem/1016 시간 복잡도를 줄이기위해 에라토스테네스의 체 방법을 사용해야했고, 공간 복잡도를 줄이기 위해 bit mask 방법과 주어진 최소값부터 에라토스테네스의 체를 적용하는 방법을 사용해 풀었습니다. my solvingc++12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061#include #include #include #include using namespace std;typedef long long ll; const ll MAX_N = 1000003;unsigned char sieve[(..

문제: https://www.acmicpc.net/problem/1015 간단한 정렬 문제입니다. 직접 정렬을 구현하지 않고 std의 multimap 을 이용해 풀었습니다. my solvingc++123456789101112131415161718192021222324252627282930313233343536373839404142434445#include #include #include #include #include using namespace std; int main(){ int n; vector numbers; cin >> n; multimap sortedNumbers; for (int i = 0; i > num; numbers.push_back(num); sortedNumbers.insert(ma..

문제: 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