문제를 잘 보면 나눠줄 수 있는 "최대" 길이이므로 만족하는 숫자들의 범위 중 최댓값을 출력해주는 것이다. 따라서 이분탐색의 upper_bound를 활용해주면 된다. Upper_bound의 대략적인 skeleton code는 다음과 같다. // Upper_bound (이분탐색에서의 상계를 구하는 방법) int start = 0; int end = vector_container.size(); while (start M >> N; vector data_store; for(int i = 0; i > temp; data_store.push_back(temp); } sort(data_..

전형적인 이분탐색의 lower_bound 형태이다. 전체적인 스켈레톤은 다음과 같다. 자세한 설명은 viyoung.tistory.com/77?category=284521 참고 // Lower_bound (이분탐색에서의 하계를 구하는 방법) int start = 0; int end = vector_container.size(); while (start < end){ mid = (start + end) / 2; if(card[mid] < compare_value){ start = mid + 1; } else{ end = mid; } } 사실 이 문제는 오버 플로우 때문에 개고생했다.. 처음에는 end값을 리터럴로 잡으려고 하다가 계속 틀려서 input값을 기준으로 최댓값을 보정하니까 맞았다. (생각보다 숫자..

문제 자체는 그렇게 어렵지 않다. 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..