후기

  • virtual participation으로 풀었는데 2200점이라니ㅠㅠㅠㅠㅠㅠ 지난주에 시험칠걸 그랬나ㅠㅠㅠ
  • 앞 3문제의 난이도는 그닥 어렵지 않았지만 4번문제를 푸냐 못푸느냐가 관건인것 같다.
  • 제대로 푼 게 아니라 어쩌다가 4번을 풀어버렸다. 뭐 이런저런 걸 떠나서 나름 만족스러운 시험이었다!
  • 그리고 잔실수 줄이는 연습이 필요할 듯하다.

사진

A. Maximum Square

문제 링크

  • 이 문제는 4분컷 해버렸다.
  • 보자마자 방법이 떠올라서 바로 구현에 들어갔다.
  • n개 짜리가 n개 이상 있다면 n짜리 정사각형을 만들 수 있다.

코드

#include <cstdio>
int t, n, arr[1001];
int main(){
    scanf("%d", &t);
    while(t--){
        scanf("%d", &n);
        for(int i = 0; i < n; i++)scanf("%d", &arr[i]);
        for(int i = n; i >= 1; i--){
            int sum = 0;
            for(int j = 0; j < n; j++){
                if(arr[j] >= i)sum++;
            }
            if(sum >= i){
                printf("%d\n", i);
                break;
            }
        }
    }
}

B1. Character Swap (Easy Version)

  • 이 문제는 단순히 문자열을 돌면서 각 위치 값이 다른 위치를 세서 다른 개수가 2개이면서 s1[i]와 s2[j]를 바꿨을 때 두 문자열이 같아지면 YES를 출력하면 된다.
  • 문자열 길이를 10001이 아니라 1001로 해서 2번이나 틀려버렸다…ㅠㅠ

문제 링크

코드

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int t, n;
char s1[10001], s2[10001];
int main(){
    scanf("%d", &t);
    while(t--){
        int x[2], cnt = 0, valid = 1;
        scanf("%d %s %s", &n, s1, s2);
        for(int i = 0; i < n; i++){
            if(s1[i] == s2[i])continue;
            else {
                if(cnt == 2){
                    valid = 0;
                    break;
                }
                x[cnt++] = i;
            }
        }
        if(valid){
            if(cnt == 1)valid = 0;
            else if(cnt == 2) {
                if(s1[x[0]] == s1[x[1]] && s2[x[0]] == s2[x[1]]);
                else valid = 0;
            }
        }
        if(valid)printf("YES\n");
        else printf("NO\n");
    }
}

B2. Character Swap (Hard Version)

  • 이 문제는 B1이랑 똑같으나 바꿀 수 있는 횟수가 2n번이다.
  • s1[i]와 s2[i]가 다를 때 s2[i]와 같은애가 s1[i + 1] ~ s1[n - 1] 중에 있으면 s1[i], s2[i]를 swap하고 s2[i]랑 찾은 값으로 swap해서 총 2회 swap으로 해결할 수 있다.
  • 만일 s2[i + 1] ~ s2[n - 1] 중에 있으면 s1[i]와 그냥 swap해줘서 1번의 swap으로 s1[i]와 s2[i]를 같게 해줄 수 있다.
  • 두 경우 모두 없다면 No를 출력하게 한다.
  • 그러므로 이 때 최대 교환 횟수는 2n이 된다.

코드

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
using namespace std;
int t;

int main(){
    cin >> t;
    while(t--){
        int valid = 1, n;
        char s1[52], s2[52];
        cin >> n >> s1 >> s2 ;
        vector<int> mx, my;
        for(int i = 0; i < n; i++){
            if(s1[i] == s2[i])continue;
            else {
                int find = 0;
                for(int j = i + 1; j < n; j++){
                    if(s2[i] == s2[j]){
                        mx.push_back(i), my.push_back(j);
                        swap(s1[i], s2[j]);
                        find = 1;
                        break;
                    }
                }
                if(find)continue;
                for(int j = i + 1; j < n; j++){
                    if(s2[i] == s1[j]){
                        mx.push_back(i), my.push_back(i);
                        swap(s1[i], s2[i]);
                        mx.push_back(j), my.push_back(i);
                        swap(s1[j], s2[i]);
                        find = 1;
                        break;
                    }
                }
                if(!find){
                    valid = 0;
                    break;
                }
            }
        }
        if(!valid){
            cout << "NO\n";
            continue;
        }
        cout << "YES\n";
        cout << mx.size() << '\n';
        for(int i = 0; i < mx.size(); i++){
            cout << mx[i] + 1 << ' ' << my[i] + 1 << '\n';
        }
    }
}

C. Tile Painting

  • 처음으로 1500점짜리 문제를 풀어봤다. (실제로 셤을 봤어야 했다….ㅎㅎ)
  • 몇가지 경우를 돌려보니 소수가 1개라면 무조건 소수 만큼 색을 뽑을 수 있고
  • 소수가 2개 이상이면 1개의 색 밖에 안된다.
  • 근데 예외가 있는데 제일 작은 소수로 나머지 소수가 다 나눠진다면 그 때도 소수가 1개인 경우로 볼 수 있다.
  • 소수가 없다면 n개의 색을 출력한다.
  • 혹시나 해서 제출했는데 맞아버렸다…ㅎㅎㅎ(다음에도 1500점 문제를 풀수있을까..?ㅠㅠ)

코드

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
using namespace std;
long long n, m, val, cnt;
//sqrt(n)보다 작은 약수를 구하고 이를 이용해서 또 다른 약수를 찾아
int main(){
    scanf("%lld", &n);
    m = sqrt(n);
    for(long long i = 2; i <= m; i++){
        if(n % i == 0){
            if(val == 0)val = i, cnt++;
            if(i % val != 0)cnt++;
            long long next = n / i;
            if(next % val != 0)cnt++;
        }
    }
    if(cnt == 1)printf("%lld", val);
    else if(cnt >= 2)printf("1");
    else printf("%lld", n);
}

느낀점

  • Div.2는 진짜 잘해야 본전이 될것같은 느낌이 강하다… 화요일에 1500점 뚫을 수 있을까..?ㅋㅋ