leo020630의 블로그

A. Donut Shops (00:05, +) 한 가게는 도넛 하나를 \(a\)원에 판매하고, 다른 가게는 도넛 \(b\)개를 \(c\)원에 판다. 이 때 첫 가게가 유리한 시점은 무조건 도넛을 1개 구매하는 시점이다. 이때 첫 가게가 더 싸지 않다면 언제나 두 번째 가게를 이용하는 것이 효율적이다. 다른 경우도 마찬가지로, 도넛을 b개 구매하는 시점이 두 번째 가게가 가장 효율적인 순간이다. B. 01 Game (00:09, +) 연산 한번당 0과 1이 각각 하나씩 사라지므로 min(0의 개수, 1의 개수)의 홀짝성을 따지면 답을 구할 수 있다.대회 중에는 머리가 빠르게 돌아가지 않아 stack을 통해 구현했다. C. Pluses and Minuses (00:20, +) 주어진 수도 코드를 해석해야 한..

A. Digits Sum (00:01, +) \((N+1)/10\)을 출력하면 된다. B. Reverse String (00:26, +) 문자열의 크기가 상당히 작으므로 만들 수 있는 전체 문자열에 대해 모두 확인해보아도 \(O(N^2)\)으로 시간 내에 문제를 해결할 수 있다. C. Penalty (00:13, +) 어느 한 팀에게 골을 몰아주는 것이 항상 최적이다. D. Backspace (00:35, +) 뒤에서부터 홀짝성을 판별하며 그리디하게 선택해주면 된다.

A. AquaMoon and Strange Sort (00:06, +) 방향을 유지하며 이동하려면 짝수 칸만큼 이동해야 한다. 따라서 본인이 있던 칸과의 홀짝성은 변하지 않고, 정렬 후에도 홀짝성이 변하지 않으면 가능하다.

A. Potion-making (00:02, +) \(\frac{100}{\gcd(100,n)\) 이 답이다. B. Permutation Sort (00:19, +4) 양쪽 끝 수를 보며 최적의 경우를 생각해주면 된다. D. Armchairs (01:05, +1) \(DP[i][j]\)를 \(i\)번째까지의 의자 모두를 앞에서 \(j\)번째까지로 옮기는 최소 비용으로 정의하자. 이는 \(i\)번째 칸이 1이고 \(j\)번째 칸이 0인 경우에만 갱신 가능한데, \(dp[i][j-1]\)과 \(dp[i-1][j-1]+|i-j|\)중 작은 것을 선택해주면 된다.

A. Fair Playoff (00:02, +) 1위 실력과 2위 실력을 가진 사람이 서로 다른 그룹에 속해있는지 판별해주면 된다. B. Array Reodering (00:07, +) 짝수->홀수대로 정렬하되, 내림차순으로 정렬하는 것이 최적이다. C. Unstable String (00:20, +) 현재 위치에서 만들 수 있는 가장 긴 Stable String의 길이들을 저장하며 가면 된다. D. Playoff Tournament (00:42, +) 각 업데이트에서 바뀌는 결과가 최대 \( O(logN) \) 개이므로, Segment Tree등의 자료구조를 이용해서 업데이트하면 \(O(NlogN)\)에 문제를 해결할 수 있다.

A. Exciting Bets (00:05, +) \(a

A. Odd Set (00:02, +) 두 정수를 더해서 홀수를 만드는 방법은 홀수+짝수밖에 존재하지 않는다. 따라서, 각 그룹마다 홀수의 개수와 짝수의 개수가 같다면 Yes이다. B. Plus and Multiply (00:14, +) 1에서 a를 곱하거나 b를 더해 n을 만들 수 있는지 묻는 문제이다. n을 만들 때에 a를 k번 곱했다고 가정하자. 그렇다면 \( n=a^k+xb \) 꼴로 표현됨을 알 수 있다. 따라서 모든 \( a^k 10^{16} \) 이므로 \(O(40T)\) 정도에 문제를 해결할 수 있다.