[Codeforces] Codeforces Round #411 (Div. 2) 이야기

오늘은 A,B,C,D번 문제를 모두 풀어본 날이다. 원래 풀어봐야 C까지 풀었지만, 

오늘은 D번까지 문제를 풀 수 있어서 매우 기분이 좋았다.

하지만 내가 풀었다는 것은 다른 사람들도 풀 수 있었다는 의미였고, A번을 틀리는 바람에 점수는 1280(+38)로 마무리 하였다.

A번 문제는 풀때부터 틀릴 것 같았다. 트릭을 썼기 때문이다.

A. Fake NP :: http://codeforces.com/contest/805/problem/A

문제 자체는 쉽다.

input a, b가 주어지는데 그 사이의 값들을 소수로 나누었을 때 가장 많이 나누어지는 소수를 구하는 문제이다.

#include <iostream>
#include <cstdio>
 
using namespace std;
 
int main()
{
    int a, b;
    cin >> a >> b;
 
    a == b ? cout << a : cout << 2;
    return 0;
}
 
 
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

나는 문제를 좀 어렵게 생각해서 에라토스테네스 체로 문제를 풀려 했지만, 그것이 아닌 이 문제는

두 입력이 같으면 그 값이고, 그게 아니면 2가 정답인 것이다. 당연한 문제였지만, 혼자 생각을 많이 하다가 틀린 것 같다.

시간 복잡도는 O(1) 이다.

B. 3-palindrome :: http://codeforces.com/contest/805/problem/B

이 문제는 다음과 같다.

전체 길이에 대해 팰린드롬을 보는 것이 아닌 처음부터 끝까지 3글자에 대한 부분 문자열에 대해 팰린드롬을 검사한다.

이때 a,b,c 3가지 글자로만 구성되며 최대한 c는 적게 쓰도록 해야한다.

이 문제도 잘 생각해보면 결국 aabbaabbaabb...로 반복된다.

따라서 아래 코드처럼 그냥 a로 다 입력해두고 bb로만 바꿔주면 된다.

시간 복잡도는 O(n)이다.

#include <iostream>
#include <cstdio>
#include <string>
 
using namespace std;
 
string str;
int main()
{
    int n;
    scanf("%d", &n);
 
    for (int i = 0; i < n; i++)
        str += 'a';
    
    for (int i = 0; i < n; i++)
        if (i + 2 < n && str[i] == str[i + 2])
            str[i + 2] = 'b';
 
    cout << str;
 
    return 0;
}
 
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

C. Find Amir :: http://codeforces.com/contest/805/problem/C

이 문제또한 생각을 하고 알고리즘 보다는 규칙을 찾는 문제였다.

1~n까지 학교가 있을 때 모든 학교를 방문해야 한다. 이때 거리는 (i + j)  % (n + 1)로 정의된다.

결국 1->n, 2->n-1, 3->n-2, ... 로 가는 길들이 0이므로 최단 거리가 되고 n->2, n-1->3 이것들을 연결해주면 

결국 나머지가 1이기에 길의 거리가 1임을 알 수 있다.

따라서 짝수인 경우는 n/2-1이 답이고, 홀수인 경우는 n/2가 답이 된다. 

시간 복잡도는 O(n)이다.

#include <iostream>
#include <cstdio>
 
using namespace std;
 
int main()
{
    int n;
    scanf("%d", &n);
 
    if (n % 2 == 0)
        cout << n / 2 - 1;
    else
        cout << n / 2;
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

D. Minimum number of steps :: http://codeforces.com/contest/805/problem/D

마지막 시간에 풀었던 문제이다.

이 문제는 DP와 규칙의 조합인 문제였다.

ab라는 단어가 있다면 bba로 바꿔야 한다.

이때 ab가 없어질 때 까지 반복하는데 예를들어 aab면 aab->abba -> bbaba -> bbbbaa라서 총 3번의 동작을 한다.

이때 aab의 과정을 잘 보면 aa가 결국 끝자리로 가는 것을 볼 수 있다.

만약 aabbaa라면 aabbaa의 aab가 다 동작을 하면 b~bbaabaa가 될 것이고 또 aab에 대한 과정을 구한다면

bb~baaaa가 될 것이다. 따라서 나는 이 해결 방식에 초점을 두기 위해 나는 ab, aab, aaab, aaaab, ... a~ab에 대한 DP값을 구해보았다.

규칙이 존재하였고, dp[i] = dp[i-1]*2+1임을 알 수 있었다.

이제 문제에 접근을 해보자.

b가 나올 때 까지 a의 개수를 계속 카운트 해준다.

b가 나오면 현재 a의 개수의 dp값을 ans에 더해준다. 그리고 cnt는 누적되며 끝까지 반복한다.

이때 ans에는 dp의 누적 합이 저장 될 것이며 답이 될 것이다.

시간 복잡도는 O(n)이다.

#include <iostream>
#include <cstdio>
#include <string>
 
using namespace std;
 
long long dpA[1000003];
long long mod = 1000000007;
 
int main()
{
    dpA[1] = 1;
    dpA[2] = 3;
    dpA[3] = 7;
    dpA[4] = 15;
 
    for (int i = 5; i <= 1000001; i++)
        dpA[i] = (dpA[i - 1] * 2 % mod) + 1;
    
    string str;
    char tmp[1000003];
    scanf("%s", tmp);
    str = tmp;
 
    int len = str.size();
    int cnt = 0;
    long long ans = 0;
 
    for (int i = 0; i < len; i++)
    {
        if (str[i] == 'a')
            cnt++;
        else if (str[i] == 'b')
            ans = ((ans % mod) + (dpA[cnt] % mod)) % mod;        
    }
    cout << ans;
 
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>

 

얼마전부터 느낀 내용이지만, 상위권의 알고리즘 문제풀이가 아닌 이상 지금 내 수준에서는 알고리즘을 많이 아는 것 보다

그 문제를 얼마나 더 창의적으로 풀 수 있냐가 중요한 것 같다는 것을 많이 느낀다.