[SW Expert Academy] 코드 배틀!! 처음으로 해보는 1등! 허걱스

4751. 다솔이의 다이아몬드 장식

SW Expert Academy는 문제에 저작권이 걸려있기 때문에 링크로 대신하겠습니다!

문제를 푸는 방법은 생각보다 간단합니다!

글자가 있는 위치를 기준으로 #을 찍어주는 함수를 만들면 됩니다!

이렇게 말이죠!

코드

#pragma once
#include<cstdio>
#include<cstring>
 
char str[51];
char res[5][502];
 
 
void draw(int r, int c) {
    res[r - 2][c] = res[r - 1][c - 1] = res[r - 1][c + 1] = res[r][c - 2] = res[r][c + 2] = res[r + 1][c - 1] = res[r + 1][c + 1] = res[r + 2][c] = '#';
}
 
int len() {
    int i = 0;
    while (str[i]) i++;
    return i;
}
 
int main() {
    int t;
    scanf("%d\n", &t);
 
    for (int tc = 1; tc <= t; tc++) {
        scanf("%s\n", str);
        memset(res, '.', sizeof(res));
 
        int l = len();
 
        for (int i = 0, st = 2; i < l; i++, st += 4) {
            res[2][st] = str[i];
            draw(2, st);
        }
        for (int i = 0; i < 5; i++) res[i][4 * l + 1] = 0;
        for (int i = 0; i < 5; i++) {
            printf("%s\n",res[i]);
        }
    }
 
    return 0;
}

4740. 밍이의 블록게임

와우.. 시뮬레이션의 정석과도 같은 문제네요!

문제의 조건들을 그대로 구현을 해주면 됩니다!

여기서 유의해야할 점은, U를 할 때 어짜피 같은 열에서는 행이 모두 붙어있기 때문에, 맨 위의 행만 블록이 있는지 없는지 검사해주면 된다는 점 입니다!

저같은 경우는 L, U, 그리고 항상 아래로 당겨져야하는 DOWN의 경우에는 스택을 사용해서 옆이나 아래로 밀어줬네요!

위 그림과 같은 상황에서 L명령을 했다고 합시다! (파란색을 아무것도 없는 배경이라고 생각하겠습니다!)

그럼 맨 위부터 시작해서 블록을 스택에 넣어줍니다. 맨 위 행에는 초록색 블록 하나밖에 없기 때문에 스택의 모양은 위와 같습니다.

그럼 이제 맨 왼쪽에 포인터가 도달하게 되고, 여기부터 스택에 쌓여있는 블록들을 pop해줍니다!

그럼 위와 같은 모양이 될 것입니다!

이러한 과정을 2번째 에도 해주면 스택은 오른쪽과 같이 되고,

pop을 해주면 요렇게 될 것입니다!

3 번째도 마찬가지! 보시면 왼쪽으로 쭈우우욱 아름답게 밀려있는 것을 볼 수 있습니다!

D명령이 약간 까다로울 수도 있습니다!

D 명령은 저장 공간 2개와 큐를 사용했습니다.

우선, store 저장 공간입니다. 나중에 사라질 블록들 (영역의 크기가 최대이겠죠)의 좌표 위치를 저장합니다.

다음은 temp라는 저장 공간입니다. 한 영역의 블록들의 좌표를 저장하고 있습니다.

그리고 queue 입니다! 한 영역의 블록은 결국 인접한 같은 색깔의 블록의 개수이기 때문에 bfs를 이용하면 구하기 편해집니다!

과정을 설명해드리겠습니다!

 

위와 같은 그림에서 D를 누르면 어떻게 해결되는지 확인해봅시다!

자 우선, 1번 블록부터 확인합니다.

그리고 왼쪽 아래쪽, 위쪽, 아래쪽을 확인하면서 자신과 같은 블록을 큐에 넣어줍시다.

오른쪽의 2번 블록의 경우에는 조건에 맞으니 넣어줍니다!

위에있는 6번 블록의 경우에는 색이 다르기 때문에 안들어가겠군요!

1번 블록을 다 검사했으면 큐에서 가장 앞에있는 2번 블록을 꺼내서 또다시 왼쪽 아래쪽 위쪽 아래쪽을 검사합니다.

1번 블록은 이미 방문했었기 때문에 검사하지 않습니다.

7번 블록과 3번 블록은 색이 다르기 때문에 큐에 넣지 않습니다.

그럼 이제 큐가 비게되고, 빨간색 블록 영역에 대한 검사가 끝났습니다!

현재 store에 저장된 것이 없기 때문에 현재 가장 큰 영역의 블록 사이즈를 2로 맞추고, temp에 있는 블록들을 store로 옮겨줍니다.

위와 같은 방법으로 bfs를 이용하면, temp에는 3,4,5번 블록이 들어있을 것 입니다. store에 저장된 영역의 크기는 2입니다. 현재 저희가 찾은 보라색 영역은 3이기 때문에 store에 temp를 그대로 덮어씌웁시다!

주황색 영역을 검사하면 최대 사이즈는 4가 됩니다! 역시 store를 temp로 뒤집어 씌워줍니다.

엇! 이번에도 영역의 크기가 4가 나왔습니다. 그러면 최대 사이즈와 같기 때문에 store의 뒤에 temp에 있는 블록들을 이어 붙여줍니다.

그럼 store에는 6,7,8,9,10,13,14,15 8개의 블록이 존재합니다.

해당 블록들이 바로 삭제되어야할 대상이고 삭제해줍니다!

결과는 위와 같을 것입니다! 참고로 현재는 괜찮지만, 문제에서는 블록들을 아래로 옮겨야 할 경우도 있기 때문에 마지막에는 이러한 행동을 하는 함수를 넣어놓읍시다!

코드

시뮬레이션인만큼 주석을 열심히 달았습니다!

#pragma once
#include<cstdio>
#include<cstring>
 
int n, m, q;
char map[30][31];
char insert[31];
 
void DOWN() {
    char st[30];
    for (int i = 0; i < m; i++) {
        int f;
        int p = 0;
        for (f = 0; f < n; f++) {
            if (map[f][i] != '#') {
                st[p++] = map[f][i];
                map[f][i] = '#';
            }
        }
 
        while (p) {
            map[--f][i] = st[--p];
        }
    }
}
 
void U() {
    bool check = true;
    // 행에 빈공간이 없는지 체크
    for (int i = 0; i < m; i++) {
        check = map[0][i] == '#';
        if (check == false) break;
    }
 
    // 빈공간이 없으면 아무 일도 하지 않음
    if (check == false) return;
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            map[i][j] = map[i + 1][j];
        }
    }
    for (int i = 0; i < m; i++) {
        map[n - 1][i] = insert[i];
    }
    //아래로 밀어줌
    DOWN();
}
 
void R() {
    char st[30];                        //스택을 이용해서 오른쪽으로 밀어줌
    for (int i = 0; i < n; i++) {
        int f;
        int p = 0;
        for (f = 0; f < m; f++) {
            if (map[i][f] != '#') {
                st[p++] = map[i][f];
                map[i][f] = '#';
            }
        }
 
        while (p) {
            map[i][--f] = st[--p];
        }
    }
}
void L() {
    char st[30];
    for (int i = 0; i < n; i++) {
        int f;
        int p = 0;
        for (f = m-1; f >= 0; f--) {
            if (map[i][f] != '#') {
                st[p++] = map[i][f];
                map[i][f] = '#';
            }
        }
 
        while (p) {
            map[i][++f] = st[--p];
        }
    }
}
 
int dr[4] = { -1,0,1,0 };
int dc[4] = { 0,1,0,-1 };
 
void D() {
    int queue[900][2];
    int f, r;
    
    int store[900][2];                                                    // 삭제되어야할 블록들 저장
    int temp[900][2];                                                    // 한 영역의 블록 저장
    int len = 0, tempLen;                                                // len : store의 크기, tempLen : temp의 크기
    int maxSize = 0;
    bool visit[30][30] = { false };                                        // 처리했는지 체크
 
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (visit[i][j]) continue;                                    // 이미 처리된 블록이면 처리할 필요가 없다.
            if (map[i][j] == '#') continue;                                // 빈공간이면 처리할 필요가 없다.
 
            char col = map[i][j];                                        // 블록의 색 저장
            f = r = 0;                
            int size = 0;
            queue[r][0] = i;
            queue[r++][1] = j;
            visit[i][j] = true;
            tempLen = 0;
            while (f != r) {
                int nr = queue[f][0];
                int nc = queue[f++][1];
                size++;
 
                temp[tempLen][0] = nr;
                temp[tempLen++][1] = nc;
 
                for (int d = 0; d < 4; d++) {
                    int nnr = nr + dr[d];
                    int nnc = nc + dc[d];
 
                    if (nnr >= 0 && nnr < n && nnc >= 0 && nnc < m)        // 블록이 맵 사이즈 안에 있어야 한다.
                    {
                        if (visit[nnr][nnc]) continue;        
                        if (map[nnr][nnc] != col) continue;                // 색이 같은 블록만 처리한다.
 
                        visit[nnr][nnc] = true;
                        queue[r][0] = nnr;                                // 색이 같은 블럭이면 같은 영역으로 간주해 큐에 넣는다.
                        queue[r++][1] = nnc;
                    }
                }
            }
            if (size > maxSize) {                                        // 현재 영역의 사이즈가 최대 영역보다 큰 경우 사이즈를 갱신하고,
                maxSize = size;                                            // 이전의 값들은 모두 버린다.
                len = 0;
                for (int i = 0; i < tempLen; i++) {
                    store[len][0] = temp[i][0];
                    store[len++][1] = temp[i][1];
                }
            }
            else if (size == maxSize) {                                    // 현재 영역의 사이즈가 최대 영역과 같을 경우
                for (int i = 0; i < tempLen; i++) {                        // 삭제할 영역을 보관하는 store 뒤에 블록들을 이어붙인다.
                    store[len][0] = temp[i][0];
                    store[len++][1] = temp[i][1];
                }
            }
        }
    }
 
    for (int i = 0; i < len; i++) {                                
        map[store[i][0]][store[i][1]] = '#';                            //블록을 삭제한다.
    }
    DOWN();
}
 
 
int main() {
    int t;
    scanf("%d\n", &t);
 
    for (int tc = 1; tc <= t; tc++) {
        scanf("%d %d %d\n", &n, &m, &q);
 
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                scanf("%c\n", &map[i][j]);
            }
        }
 
        for (int i = 0; i < q; i++) {
            char Q;
            scanf("%c\n", &Q);
 
            switch (Q) {
            case 'D':
                D(); break;
            case'L':
                L(); break;
            case 'R':
                R(); break;
            case 'U':
                scanf(" %s\n", &insert);
                U(); break;
            }
        }
 
        printf("#%d\n", tc);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                printf("%c", map[i][j]);
            }
            printf("\n");
        }
        printf("\n");
    }
    return 0;
}
 

4747. 사막에서 만난 지니

계속 어떻게풀까 고민만 하다가 '일단 짜보고 생각해보자!' 하고 짜봤더니 풀려서 당황스런 문제였습니다...

자! 우선 문제에서 가장 중요한 점은 어디일까요?

바로 '3명 에게 동일한 가치가 되도록 물건을 나누어 준다'는 것 입니다!

물건들의 가치가 입력으로 주어지기 때문에 한 명에게 얼마의 가치를 줘야하는지 바로 정할 수 있죠!

바로, 모든 물건 가치의 합 / 3 입니다!

또한, 문제에서 딱 3명 에게 나누어 줄 수 있는 경우만 준다고 했으므로,

2 명에게 물건을 나누어 준다면 나머지 한명은 나머지 물건을 가지게 됩니다. 핫핫..

그럼 1번 사람에게 줄 물건들을 정하고, 남은 물건들로 2번 사람에게 줄 물건들을 정할 조건이 완성된다면 문제를 풀 수 있게 되는 것이죠!

그렇다면, 어떻게 물건을 선택하는 것이 최선일까요?!

생각보다 간단합니다! 작은 가치의 물건들이 쪼개기 쉽기 때문에, 이왕이면 적은 물건들로 요구 조건을 채우는 것이죠!

그리고, 적은 물건들이 되기 위해선 '가치가 큰 물건 먼저' 채워 나가면 됩니다!

그리고 물건들의 가치 합이 목표로 하는 가치가 되면 2번 사람에게 줄 물건을 정하고, 만약 나머지 물건들로 2번 사람에게 줄 물건을 정할 수가 없다면 1번 사람에게 줄 물건을 다시 정하는 식으로 하면 됩니다!

테스트 케이스로 예를 들겠습니다!

우선 아이템들을 위 그림과 같이 크기가 큰 순서대로 정렬해주시고 앞에서부터 선택하시면 됩니다!

우선 5를 넣겠죠! 목표가 5이기 때문에 1번째 사람에게 줄 물건을 바로 끝나 버립니다!

5는 이미 선택한 물건이기 때문에 2번째 사람은 거들떠보지도 않습니다.

그 다음인 4를 선택합니다.

3을 선택하려 했지만 목표보다 커지기 때문에 선택하지 않습니다.

4 + 2 도 6입니다!

4 + 1 은 5가 되고 이는 바로 목표치입니다! 2번째 사람도 목표를 달성했습니다!

자동적으로 3번째 사람이 나머지 물건을 가져가면 문제가 해결됩니다!

코드

#pragma once
#include<cstdio>
#include<cstring>
using namespace std;
 
int items[2000], temp[2000];
bool used[2000];
int st[2000][2];
int t1, t2;
 
int n, sum;
 
void mergeSort(int left, int m, int right) {
    int l = left, k = left, r = m + 1;
    while (l <= m && r <= right) {
        if (items[l] < items[r]) {
            temp[k++] = items[r++];
        }
        else {
            temp[k++] = items[l++];
        }
    }
 
    while (l <= m) temp[k++] = items[l++];
    while (r <= right) temp[k++] = items[r++];
    for (int i = left; i <= right; i++) {
        items[i] = temp[i];
    }
}
 
void merge(int l, int r) {
    if (l < r)
    {
        int m = (l + r) / 2;
        merge(l,m);
        merge(m + 1, r);
        mergeSort(l, m, r);
    }
}
 
 
bool find(int depth) {
    if (depth == 1) {
        int all = 0;
        for (int i = 0; i < n && all != sum; i++) {
            if (used[i]) continue;
 
            if (all + items[i] <= sum) {
                all += items[i];
                st[t2++][1] = i;
                used[i] = true;
            }
        }
 
        while (t2 != 0 && all != sum) {
            int save = st[--t2][1];
            int idx = save + 1;
            used[save] = false;
            all -= items[save];
 
            while (idx < n && items[save] == items[idx]) idx++;
 
            for (; idx < n; idx++) {
                if (used[idx]) continue;
 
                if (all + items[idx] <= sum) {
                    all += items[idx];
                    st[t2++][1] = idx;
                    used[idx] = true;
                }
                if (all == sum) break;
            }
        }
 
        return all == sum;
    }
 
 
    st[t1++][0] = -1;
    int all = 0;
    while (true) {
        int save = st[--t1][0];
        int idx = save+1;
        
        if (save == -1) {
            all = 0;
        }
        else {
            used[save] = false;
            all  -= items[save];
        }
 
        while (save != -1 && items[save] == items[idx]) idx++;
 
        while (idx < n && all != sum) {
            if (all + items[idx] <= sum) {
                all += items[idx];
                st[t1++][0] = idx;
                used[idx] = true;
            }
            idx++;
        }
 
        if(all == sum && find(1)) return true;
    }
 
    return false;
}
 
int main() {
    int t;
    scanf("%d\n", &t);
 
    for (int tc = 1; tc <= t; tc++) {
        scanf("%d\n", &n);
 
        memset(used, false, sizeof(used));
        sum = 0;
        t1 = t2 = 0;
 
        for (int i = 0; i < n; i++) {
            scanf("%d \n", &items[i]);
            sum += items[i];
        }
        sum /= 3;
        merge(0, n - 1);
        find(0);
 
        printf("#%d\n", tc);
 
        while (t1) {
            printf("%d ", items[st[--t1][0]]);
        }
        printf("\n");
        while (t2) {
            printf("%d ", items[st[--t2][1]]);
        }
        printf("\n");
 
        for (int i = 0; i < n; i++) {
            if (used[i] == false) printf("%d ", items[i]);
        }
        printf("\n");
 
    }
    return 0;
}

여담

으어어어

무려.. 코드배틀에서 1등을 했습니다!!!

너무 기뻐요 ㅠㅠㅠ