2022 2회차 쇼미더코드 후기

대회 결과

1회차에 이어 7월 2일에 원티드에서 주관하는 쇼미더코드 2회차에 참여했다.

결과는 3솔브/65분을 기록했다. 아마 이번에도 저번 대회에 이어 금손 뱃지를 획득할 것 같다.

2022년 2회차 쇼미더코드 공지

이번 회차는 1회차와 다르게 올솔을 한 사람 중 추첨을 통해 키보드와 마우스를 증정한다.

 

2회차 성적

난이도는 1회차와 비슷했던 것 같다. 나는 C번이 봤었던 유형이라 쉬웠지만, 처음 보는 사람들이라면 꽤나 헤맸을 것이다.

 

---

A. SHOW ME THE DUNGEON (AC/+17min)

$N \leq 20$ 이기 때문에 $O(NlogN2^N)$ 브루트포스로 풀었다. 각 $2^N$개 경우의 수에 대해 정렬을 한 뒤 $t_i$가 큰 것부터 먼저 탐색을 하면 체력을 가장 적게 소모하게 된다.

참고로 $0$ ~ $2^N-1$로 잡고 비트마스킹으로 풀면 구현이 더 간단하다. 백트래킹으로 풀어도 무관하다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n, k; cin >> n >> k;
    int a[n];
    int p[n];
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> p[i];
    int ans = 0;
    
    int w[1<<n];
    for (int i = 0; i < (1<<n); i++) {
        vector<int> v;
        int sumk = 0;
        w[i]=0;
        
        for (int j = 0; j < n; j++) {
            if (((i>>j)&1)) {
                v.push_back(a[j]);
                w[i]+=p[j];
            }
        }
        sort(v.begin(), v.end());
        
        
        for (int j = 0; j < v.size(); j++) {
            sumk += (v.size()-j)*v[j];
        }
        if (sumk > k) w[i]=0;
    }
    
    for (int i = 0; i < (1<<n); i++) {
        if (ans < w[i]) ans = w[i];
    }
    cout << ans;
}

---

B. Drop 7 (AC/+65min)

꽤나 구현이 많은 문제이다. 2048 문제와 비슷한 구현방식으로 구현하면 된다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int arr[7][7];

void down() {
    for (int j = 0; j < 7; j++) {
        for (int k = 0; k < 7; k++) {
            for (int i = 1; i < 7; i++) {
                if (arr[i][j]==0 && arr[i-1][j] != 0) {
                    arr[i][j] = arr[i-1][j];
                    arr[i-1][j] = 0;
                }
            }
        }
    }
}
void erased() {
    int temp[7][7]; int erase[7][7];
    for (int i = 0; i < 7; i++) {
        for (int j = 0; j < 7; j++) {
            temp[i][j]=arr[i][j];
            erase[i][j]=false;
        }
    }
    
    for (int i = 0; i < 7; i++) {
        int cnt = 0;
        for (int j = 0; j < 7; j++) {
            if (arr[i][j] != 0) cnt++;
            else {
                int k = j-1;
                int g = cnt;
                while (cnt != 0) {
                    if (arr[i][k] == g) erase[i][k]=true;
                    k--; cnt--;
                }
            }  
        }
        int k = 6;
        int g = cnt;
        while (cnt != 0) {
            if (arr[i][k] == g) erase[i][k]=true;
            k--; cnt--;
        }
    }
    for (int j = 0; j < 7; j++) {
        int cnt = 0;
        for (int i = 0; i < 7; i++) {
            if (arr[i][j] != 0) cnt++;
            else {
                int k = j-1;
                int g = cnt;
                while (cnt != 0) {
                    if (arr[k][j] == g) erase[k][j]=true;
                    k--; cnt--;
                }
            }
        }
        int k = 6;
        int g = cnt;
        while (cnt != 0) {
            if (arr[k][j] == g) erase[k][j]=true;
            k--; cnt--;
        }
    }
    
    // 지우기
    for (int i = 0; i < 7; i++) {
        for (int j = 0; j < 7; j++) {
            if (erase[i][j]) arr[i][j]=0;
        }
    }
    // 내려보내기
    down();
    
    for (int i = 0; i < 7; i++) {
        for (int j = 0; j < 7; j++) {
            if (arr[i][j] != temp[i][j]) {
                erased(); return;
            }
        }
    }
}
 
int main() {
    ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int constarr[7][7];
    int ans = 50;
    for (int i = 0; i < 7; i++) {
        for (int j = 0; j < 7; j++) {
            cin >> arr[i][j];
            constarr[i][j] = arr[i][j];
        }
    }
    int k; cin >> k;
    for (int p = 0; p < 7; p++) {
        for (int i = 0; i < 7; i++) {
            for (int j = 0; j < 7; j++) {
                arr[i][j] = constarr[i][j];
            }
        }
        arr[0][p] = k;
        down();
        erased();
        int cnt = 0;
        for (int i = 0; i < 7; i++) {
            for (int j = 0; j < 7; j++) {
                if (arr[i][j] != 0) cnt++;
            }
        }
        if (cnt < ans) ans = cnt;
    }
    
    cout << ans;
}

---

C. 수들의 합 8 (AC/+32min)

먼저 누적합을 사용해 배열 $A, B$를 업데이트한다. 그 다음 $A[i]-B[i]$가 key, 그 개수가 value가 되는 map을 만들어 보관한다.

만약 key가 0이고 value가 v라면 정답에 ${}_v C_2 + v$를 더하고,

key가 0이 아니라면 ${}_v C_2$를 더한다. 시간복잡도는 map에 보관하는 코드가 지배적이므로 $O(NlogN)$이다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ios_base :: sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n; cin >> n;
    ll a[n]; ll b[n];
    for (int i = 0; i < n; i++) cin >> a[i];
    for (int i = 0; i < n; i++) cin >> b[i];
    for (int i = 1; i < n; i++) {
        a[i] = a[i]+a[i-1];
        b[i] = b[i]+b[i-1];
    }
    map<ll, ll> m;
    for (int i = 0; i < n; i++) {
        ll diff = a[i]-b[i];
        if (m.find(diff) != m.end()) {
            (m.find(diff))->second++;
        } else {
            m.insert({diff, 1});
        }
    }
    ll ans = 0;
    for (auto iter = m.begin(); iter != m.end(); iter++) {
        ll diff = iter->first;
        ll c = iter->second;
        if (diff == 0) ans += c;
        ans = ans + (c*(c-1)/2);
    }
    cout << ans;
}