문제 자체는 그렇게 어렵지 않다. i번째에서 거리는 사실상 i-1번째의 상태에 의해서 결정되는 양상으로 진행된다. 추가적으로 조건을 잘 살펴보면 i분째 상태는 지침지수와 운동상태인지/쉬는 상태인지 여부에 따라 결정된다. 따라서 이러한 측면에서 3차원 DP가 필요하게 된다. dp[i][j][k] = i번째 분이 지났을 때 지침 지수가 j일때 달린 거리(단, k가 0이면 i번째 분일 때 쉰 상태, 1이면 달린 상태) 그리고 조건을 활용해서 점화식을 잘 세우면 다음과 같다. (단, d[i]는 i번째분에서 달릴 경우 갈 수 있는 거리) 1) 현재 움직히고 있는 상황인 경우(k가 1) dp[i][j][1] = dp[i - 1]j - 1][1] + d[i]가 기본적인 상황이다. 단, 만약 j가 1인 경우에는 dp[..

잘 생각해보면 10^6까지이므로 충분히 모두 다 조사해도 시간안에 무조건 들어온다. 다만, 중복되는 계산이 엄청나게 많을 것 처럼 보이므로 DP를 활용해서 중복되는 계산을 줄이는 것이 이 문제의 핵심이다. "dp[n] : 정수 N이 주어졌을 때 연산을 활용해서 1을 만들 수 있는 횟수의 최솟값" 이라 잡으면 점화식은 dp[n] = dp[n - 1] + dp[n - 2] + dp[n - 3]이다. 다만, dp[1] = 0, dp[2] = 2; dp[3] = 4는 Base case이므로 따로 넣어준다. #include #include #include #include using namespace std; int dp[1000001]; int recursion(int n){ if(n == 1 || n == 2 ..

dp[n] : 정수 n을 1, 2, 3의 합으로 나타내는 방법 점화식 dp[n] = dp[n - 1] + dp[n - 2] + dp[n -3] 단, dp[1] = 1, dp[2] = 2, dp[3] = 4는 Base input 값이므로 따로 설정해준다. 잘 생각해보면 시작은 1, 2, 3일수 밖에 없고 그 뒤는 dp의 다른 값으로 표현함으로써 점화식을 세울 수 있다. #include #include #include #include typedef long long ll; using namespace std; ll dp[1000001]; ll sum(int n){ if(n == 1 || n == 2 || n == 3) return dp[n]; if(dp[n - 1] == 0) sum(n - 1); retur..

재미있는 문제이다. 15는 3의 배수와 5의 배수 성질을 모두 가지고 있다. 즉 자릿수를 다 더한것이 3의 배수이고, 끝이 5아니면 0이다. 이러한 성질을 이용해서 DP로 풀어주면 쉽게 해결할 수 있다. 잘 생각해보면 N번째 자리는 무조건 1, 5로 시작할 수 밖에 없다. 마찬가지로 N-1번쨰 자리는 무조건 1, 5로 시작할 수 밖에 없다. 이를 활용하여 자릿수가 3이라는 것과 결부지어 생각해보자 "DP[n] : n번째 자리일 때 15배수의 갯수"로 잡았다고 하였을 때 맨 앞자리가 15로 시작하게 되면 뒤는 3의 배수이면서 자리가 n-2번쨰 자리를 만족하기만 하면 되므로 이는 DP[n-2]와 동치이다. 맨 앞자리가 51로 시작해도 마찬가지이다. 계속해서 수형도를 그려나가면서 가질 수 있는 경우의 수를 전..

공급받는 것을 집합으로 생각해서 풀어야하는 문제이므로 Union-Find를 생각해주면 된다. 추가적으로 금액이 최소인 상태로 간선들을 선택하므로 느낌이 MST와 비슷하다. 다만, 발전소를 반드시 모두 거쳐야하는 것은 아니므로 스패닝 트리는 아니다. 이 문제를 정확하게 접근해보면, 한 집합안에 발전소가 1개만 있으면 된다. 적당히 priority_queue와 Union-Find를 활용해서 풀어주면 된다. #include #include #include #include #include #include using namespace std; struct DisjointSet{ vector parent, rank; DisjointSet() : parent(1001){ for(int i = 0; i < 1001; ..

사실 아이디어는 잘 잡았는데, 구현 실력이 모자라서 시간 초과 및 메모리 초과가 나서 인터넷에서 풀이를 많이 참고하였다. 일단 처음에 들었던 생각은 다음과 같다. 문명이 몇개인지 알아야하고, 각 문명별로 컨트롤 해야하는 상황이므로 Union-Find 방법을 생각하였다. 결과적으로 그룹에 속하는지 속하지 않는지를 빠르게 판단할 수 있어야하고, 그 결합도 쉬워야하기 때문이다. (예를 들어 그룹끼리 합쳐질 때 만약 Union-Find를 사용하지 않는다면 일일히 방문하여 집합 정보에 대한 내용을 수정해주어야 하는데 이 경우에는 시간 초과가 날 수 밖에 없다.) 여기까지는 참 좋았는데, 2중 Union-Find를 진행하여 메모리 손실이 많이 발생하였다. 즉, pair parent[2001][2001]로 잡고 de..

처음에 문제를 보고 든 생각은 다음과 같다. 연결 되어 있냐/ 연결되어 있지 않냐를 판단하는 것이므로 Union-Find를 생각했다. 하지만, 중간에 간선을 지우는 상황이 발생하는데 먄약 Path-compression을 하게 되면 문제가 발생한다는 것을 파악하였다. 그래서 Union by rank만 진행해서 Union-Find를 진행하였다. 하지만 결과는 시간 초과였다. 그런데 잘 생각해보면, 애초에 시작할 때 지워질 간선을 무시하고 Union-Find를 진행하고 나중에 Merge시키면 되는 문제였다. 다른 블로그를 참고해보니 query 배열을 잡아서 하던데, 일단 코드에서는 stack를 2개 잡아서 진행하였다.(생각해보니 좀 비효율적인듯..) 코드는 다음과 같다. #include #include #in..

사실 이 문제를 보고 가장 먼저 든 생각은 최소 스패닝 트리의 해법과 비슷하게 풀면 된다는 것이다. 특히 Kruskal 알고리즘 해법과 되게 비슷한 느낌이 들었다. 정확하게 이 문제는 스패닝 트리를 구하는 것이 아니다. 왜냐하면, 출발과 목적 지점을 포함하기만 하면 되지 모든 노드들을 전부 방문할 필요는 없기 때문이다. 하지만 Kruskal 알고리즘 기법을 활용하겠다고 마음을 먹은 이유는 다음과 같다. 1. 결과적으로 길이 최대가 되게끔 계속해서 만들어야 한다. 2. 즉 이러한 알고리즘은 사실상 최소 값들을 priority_queue에 저장하고 탐욕적으로 집합을 만드는 Kruskal 알고리즘과 매우 유사하다. 3. 또한 연결되었다는 것은 하나의 집합으로 볼 수 있다는 의미이고 상호 배타적 집합에서 배운 ..