Doby's Lab

https://www.acmicpc.net/problem/17222 17222번: 위스키 거래 주은이와 명진이는 사적으로 위스키를 거래하는 사이이다. 주은이는 돈도 많고 위스키를 무척 좋아해서 위스키를 가능한 한 많이 사고 싶어하고, 명진이는 위스키가 넘쳐나서 위스키를 가능한 www.acmicpc.net Solved By: Max Flow 명진이를 Source, 주은이를 Sink로 네트워크를 모델링합니다. 명진이는 무한대로 보낼 수 있고, 주은이는 무한대로 받을 수 있습니다. 하지만, 친구들은 한 번에 받을 수 있는 용량(Capacity)이 제한되어있습니다. 명진이가 명진이 친구들에게로 가는 edge에서 용량은 명진이 친구들이 한 번에 받을 수 있는 양으로 용량을 할당하고, 주은이 친구들이 주은이에게로 ..

https://www.acmicpc.net/problem/14630 14630번: 변신로봇 승균이는 변신로봇에 심취해있었다. 한 분야가 극에 달한 사람은 그것을 통해 세상을 이해한다는 말이 있는데, 승균이가 바로 그러했다. 승균이는 시시때때로 감정이 변하는 사람들을 보면서 www.acmicpc.net Solved By: Dijkstra 오래간만에 풀어본 다익스트라 문제였습니다. 변신 상태를 각각 하나의 노드로 취급했을 때, 각 엣지들의 가중치는 각 노드에 입력받은 값들을(문자열로) 각 자리의 차를 제곱한 값들을 더해주었습니다. 가중치들을 각 노드의 엣지로 이어주는 방법은 Brute-Force를 택했습니다. (거의 3달 전에 작성했던 코드(틀림)과 비교해봤더니 신기하더군요. 그런데 3달 전이면 저 이병 때..

https://www.acmicpc.net/problem/1476 1476번: 날짜 계산 준규가 사는 나라는 우리가 사용하는 연도와 다른 방식을 이용한다. 준규가 사는 나라에서는 수 3개를 이용해서 연도를 나타낸다. 각각의 수는 지구, 태양, 그리고 달을 나타낸다. 지구를 나타 www.acmicpc.net Solved By: Brute-Force 중국인의 나머지 정리를 쓰지 않아도 완전 탐색으로 풀 수 있는 문제였다. #include using namespace std; int main(){ int e, s, m; cin >> e >> s >> m; // brute-force int y = 1; while(1){ if((y - e) % 15 == 0 && (y - s) % 28 == 0 && (y - m..

https://www.acmicpc.net/problem/24009 24009번: Huge Numbers The first line of the input gives the number of test cases, T. T lines follow. Each line contains three integers A, N and P, as described above. www.acmicpc.net Solved By: Exponentiation By Squaring, Number Theory 거듭제곱은 시간 단축을 위해 분할 정복을 이용했습니다. A, N, P가 주어지면 A의(N!) 제곱을 구하고, 이를 P로 나누라는 소리인데 우선, A의(N!)제곱은 N이 3이라 할 때, (((A^1)^2)^3)과 같이 정리할 ..

ll POW(ll a, ll b) { if (b == 0) {//지수가 0이면 모든 수가 1이 된다. return 1; } ll value = POW(a, b / 2); // 여기서 분할적으로 나뉘어짐 value = value * value; if (b % 2 == 0) {// b가 짝수일 때 return value; } else {// b가 홀수일 때 return value * a; } }

https://www.acmicpc.net/problem/15203 15203번: Police Station A network of hyperspace highways is built in the galaxy. Each of the highways is a one-directional corridor which connects two planets. Galactic government wants to find a planet on which a police station will be built. In order for the police to protect www.acmicpc.net Solved By: Tarjan Algorithm 각 SCC를 구성하여 SCC의 indegree를 조사합니다. inde..

https://www.acmicpc.net/problem/13059 13059번: Tourists Each input will consist of a single test case. Note that your program may be run multiple times on different inputs. The first line of input will consist of an integer n (2 ≤ n ≤ 200,000) indicating the number of attractions. Each of the following n− www.acmicpc.net Solved By: LCA, Number Theory 트리가 주어지면 각 노드의 배수 노드들 사이에 노드 개수를 세는 문제입니다. 트리이..

https://www.acmicpc.net/problem/9742 9742번: 순열 입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있다. 첫 번째 문자열은 서로 다른 숫자와 알파벳으로 이루어져 있으며, 길이는 최대 10이다. 또한, 사전 www.acmicpc.net Solved By: BackTracking 찾아야 하는 순서가 백트래킹으로 구해지는 순서 안에 있다면 결과 string에 해당 문자열을 할당해주고, 아니라면 빈 문자열을 반환하도록 아무것도 할당하지 않았습니다. #include #include using namespace std; string s; int n; int cnt; string res; bool visited[10]; void backTrac..