eff3ct's st0rage Dev Blog

월반멘토링 1주차 set 풀이

25 Jul 2022

개발공부 하기도 귀찮고 PS 공부하기도 귀찮아서 쓰는 풀이

완전탐색 / 그리디 / 분할정복

1. 로프 (Silver IV)

tag : greedy, sorting, math

로프 하나만 있으면 해당 로프가 버티는 최대 중량값이 답이다. 두개 이상이 되면 (버틸 수 있는 최대 중량의 min값 * 로프 개수)가 해당 로프들이 버틸 수 있는 최대 중량임을 쉽게 알 수 있다. 알고싶은 것은 N개의 로프가 주어질 때, 로프를 잘 써서 버틸 수 있는 최대 중량값이다.

그리디하게 접근하자. 먼저 로프가 버틸 수 있는 최대 중량 값을 기준으로 내림차순 정렬한다. 앞에서부터 로프를 하나씩 추가해가며 로프들이 버틸 수 있는 max값을 찾아주면 쉽게 답을 찾을 수 있다.

코드 보기 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ppii = pair<int, pii>;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N; cin >> N;
    vector<int> rope(N);
    for(int& e : rope) cin >> e;

    sort(rope.rbegin(), rope.rend());

    int ans = rope[0];
    for(int i = 1; i < N; ++i) 
        ans = max(ans, (i + 1) * rope[i]);
    
    cout << ans << '\n';

    return 0;
}

2. 색종이 만들기 (Silver II)

tag : divide and conquer

문제에서 시키는 그대로 하면 된다. 구역을 4개로 나눠가면서 해당 구역이 같은 색깔로 가득 차 있는지 확인하고 같은 색깔이면 답을 업데이트, 아니면 재귀 호출을 하면 된다.

\(f(i, j, N) =\) “(i, j)부터 N길이의 정사각형 안에 있는 흰색종이와 파란색종이를 찾는 함수”

라고 하면, 아래처럼 관계식을 찾을 수 있다.

\[\small f(i, j, N) = f(i + \frac{N}{2}, j, \frac{N}{2}) + f(i, j + \frac{N}{2}) + f(i + \frac{N}{2}, j + \frac{N}{2}, \frac{N}{2}) + f(i, j, \frac{N}{2})\]

base case와 구현을 적당히 잘 하면 쉽게 맞출 수 있다.

코드는 1년전의 내가 짜놓은… 파이썬 코드 ㅎㅎ… 요상하게 짜놓긴 했는데 다행히도 알아보는데는 지장 없네요.

코드 보기 
result = [0, 0]

def checkPaper(array, startx, starty, size):
    global result
    if size == 1:
        if array[startx][starty] == 0:
            result[0] += 1
        else:
            result[1] += 1
        return -1
    else:
        cnt = 0
        for i in range(size):
            for j in range(size):
                if array[startx + i][starty + j] == 0:
                    cnt -= 1
                else:
                    cnt += 1
        if cnt == -(size*size):
            result[0] += 1
            return -1
        elif cnt == (size*size):
            result[1] += 1
            return -1
        return 0

def divPaper(array, startx, starty, size):
    condition = checkPaper(array, startx, starty, size)
    startxA = startx + size // 2
    startyA = starty + size // 2
    if condition != -1:
        divPaper(array, startx, starty, size // 2)
        divPaper(array, startxA, starty, size // 2)
        divPaper(array, startx, startyA, size // 2)
        divPaper(array, startxA, startyA, size // 2)


N = int(input())

arr = [list(map(int, input().split())) for _ in range(N)]

divPaper(arr, 0, 0, N)

print(result[0])
print(result[1])

3. 2022는 무엇이 특별할까? (Silver II)

tag : math, brute-forcing

완전탐색으로 풀리는 문제다. d진법 숫자가 한번 씩 모두 등장하는 수를 다 보려면 \(\scriptsize O(d!)\)이다. d개의 숫자를 나열하는 경우의 수랑 같기 때문이다. 따라서, 순열을 만드는 함수를 작성하면 되고 만든 수가 N보다 큰 지 확인하고 그 수들 중 min값을 저장해놓으면 된다.

코드가 지금보니까 좀 지저분하긴 함.

코드 보기 
#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

bool visit[10];
ll arr[10];
const ll INF = 12345678987654321;
ll ret = INF;

void solve(ll& N, ll& d, int cnt) {
    if(cnt == d) {
        ll val = 0;
        for(int i = 0; i < d - 1; ++i) {
            val += arr[i];
            val *= d;
        }
        val += arr[d - 1];

        if(val > N) ret = min(ret, val);
        return;
    }

    if(cnt == 0) {
        for(int i = 1; i < d; ++i) {
            if(visit[i]) continue;
            visit[i] = true;
            arr[cnt] = i;
            solve(N, d, cnt + 1);
            visit[i] = false;
        }
    }
    else {
        for(int i = 0; i < d; ++i) {
            if(visit[i]) continue;
            visit[i] = true;
            arr[cnt] = i;
            solve(N, d, cnt + 1);
            visit[i] = false;
        }
    }
    
}

int main() {
    ll N, d; cin >> N >> d;

    solve(N, d, 0);

    cout << (ret == INF ? -1 : ret);

    return 0;
}

4. 에너지 모으기 (Silver I)

tag : brute-forcing

태그에 백트래킹이 있는데 왜 있는지는 모르겠다. 그냥 완전탐색으로 쉽게 풀린다. Naive하게 시키는걸 구현해도 풀린다. N이 작아서 벡터에 현재 에너지 구슬을 뺀 나머지를 새로 다 넣고 전달해서 풀면 된다. 그런 뒤 찾아낸 값들 중에서 max를 리턴하도록 하면 답이 구해진다.

코드 보기 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ppii = pair<int, pii>;

int get_max(int N, vector<int> W) {
    if(N == 2) return 0;
    
    int ret = 0;
    for(int i = 1; i < N - 1; ++i) {
        int energy = W[i - 1] * W[i + 1];
        vector<int> next_W;
        for(int j = 0; j < N; ++j) {
            if(j == i) continue;
            next_W.push_back(W[j]);
        }
        ret = max(ret, energy + get_max(N - 1, next_W));
    }

    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N; cin >> N;
    vector<int> weight(N);
    for(int& e : weight) cin >> e;

    int ans = get_max(N, weight);
    cout << ans << '\n';

    return 0;
}

5. 부분수열의 합 (Silver I)

tag : brute-forcing

N이 20으로 작다는 점에 주목하자. S로 만들 수 있는 부분 수열을 모두 만들어보면 된다. 각 원소가 있다 없다로 생각하면 2가지 경우의 수만 생기므로, 탐색해야할 경우의 수는 \(\scriptsize O(2^{N})\)가지이다.

이때, N이 최대 20인데 \(\scriptsize 2^{20}\)은 백만 정도니까 충분히 시간내에 풀린다. 각 원소를 선택하고 안하고 하면서 모든 경우를 만들어주자. 그런 다음, 만들어질 수 있는 합에다가 체크하고 모든 체크가 다 끝나면 해당 배열에서 mex(Minimum EXcluded)값을 찾아주면 된다.

코드 보기 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ppii = pair<int, pii>;

bool vst[2'000'001];
int N;

void make_subarray_sum(int idx, int S, vector<int>& seq) {
    if(idx == N) {
        vst[S] = true;
        return;
    }
    make_subarray_sum(idx + 1, S + seq[idx], seq);
    make_subarray_sum(idx + 1, S, seq);
}

int get_mex() {
    for(int i = 0; i <= 2'000'000; ++i) {
        if(!vst[i]) return i;
    }
    return -1;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> N;
    vector<int> seq(N);
    for(int& e : seq) cin >> e;

    make_subarray_sum(0, 0, seq);
    int ans = get_mex();

    cout << ans << '\n';

    return 0;
}

6. 사과나무 (Silver I)

tag : greedy, math

뭔가 순서가 중요할 것 같지만 사실 그렇지 않다는 걸 캐치하면 풀 수 있는 문제다. 1만큼 성장하는 물뿌리개의 사용횟수와 2만큼 성장하는 물뿌리개의 사용횟수가 항상 동일해야한다. 홀수 높이만큼 성장하려면 1만큼 성장하는 물뿌리개가 필수이다. 따라서, 모든 높이를 훑어보고 홀수이면 1의 사용횟수를 증가시킨다. 2의 사용횟수는 높이를 2로 나눈 몫이다. 이렇게 하면 (2의 사용횟수) > (1의 사용횟수)가 되는데, 이때, 2 = 1 + 1이라는 점을 이용해 2를 하나 감소시키고 1을 두개 증가시키며 사용횟수가 같아질 수 있는 지 보면 된다.

코드 보기 
#include <iostream>

using namespace std;

void solve(int* height, int N) {
    int oneCnt = 0, twoCnt = 0;
    for(int i = 0; i < N; ++i) {
        if(height[i] % 2) oneCnt++;
        twoCnt += (int)height[i] / 2;
    }
    while(true) {
        if(twoCnt == oneCnt) {
            cout << "YES";
            break;
        }
        twoCnt -= 1;
        oneCnt += 2;
        if(twoCnt < oneCnt) {
            cout << "NO";
            break;
        } 
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int height[100001];
    int N, h;

    cin >> N;
    for(int i = 0; i < N; ++i) {
        cin >> height[i];
    }

    solve(height, N);

    return 0;
}

7. 도서관 (Gold V)

tag : greedy, sorting

그리디한 전략을 생각해내면 풀 수 있는데.. 쉽진 않다. 먼저, 양수 좌표에만 가져다 놔야 할 책이 있다고 쳐보자. 역순으로 생각하면 조금 쉬운데, 일단 가장 먼 거리에 있는 것은 마지막에 가져다 줘야지 다시 0으로 돌아오지 않을 수 있다는 걸 알 수 있다. 마지막에 있는걸 가져다 놓는 김에 그 전에 있는 책 M - 1개도 다 가져다 주면, 0으로 되돌아 오지 않고 최소 거리로 움직일 수 있다.

마지막 책들을 가져다 놓기 전에 그 책들 이전 위치에는 다 책이 놓여 있어야 한다. 마지막 이전에 M개의 책이 놓였다는 사실을 알 수 있고, 그전에도 M개가 놓였을 것이다. 그러다가, M개보다 적게 놓여야할 위치가 있음을 알게 되는데 고걸 잘 처리해주면 된다.

그럼 양수 음수 좌표가 둘다 있으면요? 가장 먼 곳에 있는 좌표가 음수일 지 양수일 지 모르니까 둘 중에 절댓값이 더 큰쪽이 마지막이 되면 된다. 책 가져다 놓는건 양수만 있을 때랑 동일한 전략을 적용하면 된다. 단지 방향만 반대라 두 방향 모두 다 구해주면 된다.

마지막 처리가 좀 어려울 수 있는데, 모든 거리를 다 구해 더한 다음 절댓값 MAX를 빼주면 된다. 무슨 소리인지 이해가 어려울 수 있는데 코드를 보는게 이해가 빠를 듯!

코드 보기 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ppii = pair<int, pii>;

int get_dist(vector<int>& x, int M) {
    int ret = 0;
    int idx = (int)x.size() - 1;
    while(idx >= 0) {
        ret += abs(x[idx]) * 2;
        idx -= M;
    }
    return ret;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, M; cin >> N >> M;

    vector<int> neg;
    vector<int> pos;
    for(int i = 0; i < N; ++i) {
        int x; cin >> x;
        if(x < 0) neg.push_back(x);
        else pos.push_back(x);
    }
    
    sort(neg.rbegin(), neg.rend());
    sort(pos.begin(), pos.end());

    int ans = 0;
    ans += get_dist(pos, M);
    ans += get_dist(neg, M);

    int sub = 0;
    if(pos.empty()) sub = abs(neg.back());
    else if(neg.empty()) sub = abs(pos.back());
    else sub = max(abs(pos.back()), abs(neg.back()));

    ans -= sub;
    cout << ans << '\n';

    return 0;
}

8. 샤워실 바닥 깔기 (Large) (Gold I)

tag : divide and conquer, implementation

나만 모르는 웰노운.. 인 문제다. L-테트로미노를 이용하면 임의의 한칸을 제외한 모든 칸을 채울 수 있다고 한다. 그게 웰노운이라는데 뭐 하여튼 자세한 풀이는 이분 블로그 글을 참고하자. 여담으로 요걸 풀면, UCPC 예선 기출인 흔한 타일 색칠 문제를 풀 수 있다.

코드 보기 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ppii = pair<int, pii>;

int m[129][129];
int n;

bool is_not_blank(int y, int x, int delta) {
    for(int r = 0; r < delta; ++r) {
        for(int c = 0; c < delta; ++c) {
            if(m[y + r][x + c] != 0) return false;
        }
    }
    return true;
}

void solve(int y, int x, int K) {
    int delta = pow(2, K - 1);
    n++;

    if(is_not_blank(y, x, delta)) m[y + delta - 1][x + delta - 1] = n;
    if(is_not_blank(y + delta, x, delta)) m[y + delta][x + delta - 1] = n;
    if(is_not_blank(y, x + delta, delta)) m[y + delta - 1][x + delta] = n;
    if(is_not_blank(y + delta, x + delta, delta)) m[y + delta][x + delta] = n;

    if(K == 1) return;

    solve(y, x, K - 1);
    solve(y, x + delta, K - 1);
    solve(y + delta, x, K - 1);
    solve(y + delta, x + delta, K - 1);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int K; cin >> K;
    int x, y; cin >> x >> y;
    m[y][x] = -1;

    solve(1, 1, K);

    for(int i = pow(2, K); i >= 1; --i) {
        for(int j = 1; j <= pow(2, K); ++j) {
            cout << m[i][j] << ' ';
        }
        cout << '\n';
    }

    return 0;
}

9. 중간 (Gold I)

tag : binary search, divide and conquer?

이분탐색이 분할정복인가..? 는 잘 모르겠는데 살짝 변형된 이분탐색으로 풀 수 있다. \(\scriptsize A[x]\)를 가져올 때, B에서는 \(\scriptsize B[N - x]\)를 가져오면 된다. 그리고 그 두 값을 비교해서 작은 값이 있는 쪽의 인덱스 범위를 키우면 된다. 그러면 앞에서부터 N번째 값을 찾아낼 수 있다.

요걸 이분탐색으로 구해주면 된다. l = 1, r = N으로 두고 위 논리를 적용시켜서 mid값으로 질의를 던져서 얻어낸 값으로 범위를 조절하자. 질의가 하필 40번인 이유는 \(\scriptsize O(log(2^{19}))\)번 각각 배열에 질의를 하고 마지막에 N번째 값이 무엇인지 찾으려고 2번 더 해야해서 그렇다.

아이디어 자체는 그리 어렵지 않은데.. 한번에 맞기 좀 어려운 문제다. 범위 조절하고 N번째 값이 무엇인지 좀 생각해야할게 많은데 잘 생각해서 풀면 되긴함.

코드 보기 
#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using pii = pair<int, int>;
using ppii = pair<int, pii>;

int main() {
    ios_base::sync_with_stdio(false);

    int N; cin >> N;
    int sa = 1, ea = N;
    int sb = 1, eb = N;

    int f, g, ma, mb;
    while(sa != ea && sb != eb) {
        ma = (sa + ea) / 2;
        mb = (sb + eb) / 2;
        cout << "? A " << ma << endl;
        cin >> f;
        cout << "? B " << mb << endl;
        cin >> g;

        if(f < g) {
            sa = ma + 1;
            eb = mb;
        }
        else {
            ea = ma;
            sb = mb + 1;
        }
    }

    cout << "? A " << sa << endl;
    cin >> f;
    cout << "? B " << sb << endl;
    cin >> g;

    cout << "! " << min(f, g) << endl;

    return 0;
}

Related posts