Doby's Lab

https://www.acmicpc.net/problem/13699 13699번: 점화식 다음의 점화식에 의해 정의된 수열 t(n)을 생각하자: t(0)=1 t(n)=t(0)*t(n-1)+t(1)*t(n-2)+...+t(n-1)*t(0) 이 정의에 따르면, t(1)=t(0)*t(0)=1 t(2)=t(0)*t(1)+t(1)*t(0)=2 t(3)=t(0)*t(2)+t(1)*t(1)+t(2)*t(0)=5 ... 주어진 입력 0 ≤ n www.acmicpc.net Solved By: DP Top-Down DP 방법을 사용했습니다. 재귀 호출로 선언하여 t(n) 값이 존재한다면 그대로 리턴하고, 존재하지 않는다면 t(n)을 구하여 리턴하는 방식으로 Memoization 기법이 상당히 드러나는 문제였습니다. #in..

https://www.acmicpc.net/problem/9625 9625번: BABBA 상근이는 길을 걷다가 신기한 기계를 발견했다. 기계는 매우 매우 큰 화면과 버튼 하나로 이루어져 있다. 기계를 발견했을 때, 화면에는 A만 표시되어져 있었다. 버튼을 누르니 글자가 B로 변했 www.acmicpc.net Solved By: DP A는 직전의 문자열에서 B들이 변환된 것이라 볼 수 있습니다. B는 "BA"로 전환되기 때문에 직전 문자열에서 B의 개수와 A에서 변환되는 B의 개수를 모두 합하여 각각 A, B의 개수를 알 수 있습니다. #include #define MAX 46 using namespace std; int A[MAX], B[MAX]; int main(){ int k; cin >> k; A[..

https://www.acmicpc.net/problem/1585 1585번: 경찰 첫째 줄에 차가 총 몇 대 있는지 주어진다. 이 값을 N이라고 하고, 50보다 작거나 같은 자연수이다. 둘째 줄에는 차가 동호도로에 들어가는 시간이 주어진다. 총 N개의 수가 공백 한 칸을 사이에 www.acmicpc.net Solved By: MCMF 네트워크 모델링에 있어서 다음 경우들을 생각하면 됩니다. 1) 출발 시간과 도착 시간이 매칭이 안 되는 경우 >> 도착 시간이 출발 시간보다 빠르다면 이건 말이 되지 않는 경우입니다. >> edge를 만들어줄 필요가 없습니다. 2) 벌금을 내지 않는 경우 >> edge를 만들어주고, 벌금은 내지 않으므로 cost값은 0입니다. 3) 벌금을 내는 경우 >> edge를 만들어..

https://www.acmicpc.net/problem/14950 14950번: 정복자 서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재 www.acmicpc.net Solved By: Kruskal Algorithm 정복할 때마다 도로 비용을 t만큼 올린다 한들 모든 도로가 t만큼 올라가는 것이기 때문에 우선 어떤 노드에서 다른 모든 노드를 갈 수 있으며 가중치가 최소인 합을 구해야 합니다. >> 즉, MST를 구해야 합니다. Kruskal Algorithm 사용 최소합을 구한 상태에서 t값을 신경 써줘야 하는데 MST의 edge의 개수는 n - 1개입니다. 첫..

https://www.acmicpc.net/problem/12745 12745번: Traffic (Small) 사람들이 가장 많이 이용하는 구간을 출력하고, 몇 명의 사람들이 그 구간을 거쳤는지 출력한다. a b c 꼴로 출력하면 되는데, 이는 사람들이 가장 많이 이용하는 구간이 a번 역과 b번 역을 연결하 www.acmicpc.net Solved By: LCA (using Sparse Table) 시간 복잡도 상으로는 시간 초과가 나와야할 거 같은 코드가 맞았습니다. section배열을 선언하여 a, b사이를 얼마나 지나갔는지 저장하였습니다. 트리의 구조이기도 하고, 모든 사람들이 최단 거리로 이동했기 때문에 LCA를 사용했습니다. 쿼리에서 lcaNode를 구하여 a에서 lcaNode까지 한 칸씩 이동..

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..