💚 16956 늑대와 양 최소의 울타리를 구하는 것이 아니므로 사실 BFS를 쓸 필요가 없다. 양과 늑대가 붙어있는 경우를 확인하고, 없으면 모든 빈칸에 울타리를 설치하면 절대로 늑대가 양에게 갈 수 없다. 💚5014 스타트링크 처음에 이 문제를 보았을 때는 그냥 BFS 식으로 탐색하는 것이 아니라 건방지게 단순 연산으로 풀 수 있을 것 같았다. 예를 들어 a, b를 각각 위, 아래로 이동가능한 거리라고 가정하자. 2라는 거리를 이동해야할 때, 위로는 2층씩, 아래에는 3층씩 이동가능하다면 $2a + 3b = 2$라는 이차방정식이 세워진다. 여기서 단순히 $a, b$를 구하는 것이 아니라 양의 정수를 구해야하므로 BFS 식으로 탐색을 해야하는 것이 맞았다. 시간복잡도는 최악의 경우 모든 층을 방문하는 것..

이 문제는 greedy하게 풀면 모든 조합을 만들 필요가 없다고 한다..나는 모든 조합을 다 시도해봤더니 시간 초과가 발생한다. We want to show that a binary string T of length $m$ is paranoid if and only if $m = 1$ or($m > 1$ and $S[m] \neq S[m - 1]$) 🌱 In the case of $S[m - 1] = S[m]$ 우리는 마지막 두 char를 지울 수 없다. 왜냐하면 동일한 char라서 남아있기 때문이다. 따라서 S는 paranoid가 아니다. 🌱 In the case of $S[m - 1] \neq S[m]$ 만약 $m = 2$이라면, 우리는 하나의 연산만으로 우리의 목표에 도달할 수 있다. 그렇지 않은 ..

나는 이거 그나마 패턴 만들어서 꾸역꾸역 string을 만들었는데, 이보다 더 간단한 패턴이 있다고 한다. Define the minimum possible creepiness of the string as ans. We want to show that ans is equal to $max(1, |a - b|)$. 최소한의 creepiness를 가지는 ans라는 string을 정의해보자. 우리는 ans가 $max(1, |a - b|)$와 동일하다는 것을 보여주어야 한다. $S[1..1]$의 creepiness는 1과 동일하고, $S[1..n]$는 $|a - b|$와 동일하다. 따라서 $max(1, |a - b|) t; while(t--) { int a, b; cin >> a >> b; for(int i ..

https://www.acmicpc.net/problem/7453 7453번: 합이 0인 네 정수 첫째 줄에 배열의 크기 n (1 ≤ n ≤ 4000)이 주어진다. 다음 n개 줄에는 A, B, C, D에 포함되는 정수가 공백으로 구분되어져서 주어진다. 배열에 들어있는 정수의 절댓값은 최대 228이다. www.acmicpc.net 처음에 풀 때는 정신없이 풀었는데 왜 굳이 이렇게 풀었는지 한 번 정리해볼 필요가 있어보였다. 효율성을 생각하지 않는다면 A,B,C,D 배열 요소마다 조합을 만들어서 배열의 합이 0인지를 확인한다. 이렇게 된다면 $O(N^4)$이라는 시간복잡도를 가지게 된다. (비효율 그자체..) 이런 상황을 방지하기 위해 A,B 배열을 합치고 C,D 배열을 합쳐서 4개의 배열을 2개의 배열로 ..

https://leetcode.com/problems/time-based-key-value-store/ Time Based Key-Value Store - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 아..역시나 이번에도 시간 초과가 발생한다... 내가 이렇게나 비효율적인 사람이었나 싶다. 그나마 효율적인 탐색을 하겠다고 Binary Search, (B+Tree로 구현된 STL인)Set 등 다양하게 시도하였으나 모두 FAIL 이보다 더 효율적인 방법이 도저히 ..

https://leetcode.com/problems/magical-string/ Magical String - LeetCode Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview. leetcode.com 이 문제는 앞서 푼 문제의 다음 챌린지로 추천된 문제여서 풀게된 문제이다. 역시나 주어진 규칙을 곧이곧대로 받아들이는 것이 아니라, 규칙 내의 패턴을 활용해야 한다. 규칙 The string s is magical because concatenating the number of contiguous occr..