[Codeforces] 1694A. Creep
2022. 6. 17. 13:49ㆍTIL💡/Algorithms
나는 이거 그나마 패턴 만들어서 꾸역꾸역 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|) <= ans$이다.
- $max(1, |a - b|)$의 creepiness와 동일하게 만드는 방식
- while $0 < a, b$ holds, add 01 to the end of the string. After that, add the remaining character to the end of the string. Now we know ans <= $max(1, |a-b|)$.
- Complexity: $O(a + b)$
#include <iostream>
#include <map>
#include <cmath>
using namespace std;
int main() {
int t;
cin >> t;
while(t--) {
int a, b;
cin >> a >> b;
for(int i = 0;i < min(a, b);i++) {
cout << "01";
}
for(int i = 0;i < abs(a - b);i++) {
cout << (a < b ? 1 : 0);
}
cout << '\n';
}
return 0;
}
이 개수의 차이를 카운트할 때 어차피 문자열의 처음부터 세기 때문에 누적된다.
따라서 굳이 가운데 사이사이에 숫자를 넣어줄 필요가 없다.
앞에 최대한 score를 0으로 만들면 이후에는 score가 증가되어 $max(|a - b|)$가 된다.
'TIL💡 > Algorithms' 카테고리의 다른 글
[중급 알고리즘] Brute Froce 확장 2 (0) | 2022.06.18 |
---|---|
[Codeforces] 1694B. Paranoid String (0) | 2022.06.17 |
[백준] 7453: 합이 0인 네 정수 (0) | 2022.06.15 |
[LeetCode] 981. Time Based Key-Value Store with lower_bound (0) | 2022.06.14 |
[Codeforces] 481. Magical String (0) | 2022.06.14 |