2017-10-12 게시 됨2021-03-22 업데이트 됨Algorithm / BOJ6분안에 읽기 (약 870 단어)

<12100> 2048 (Easy)

문제 : https://www.acmicpc.net/problem/12100

째로탈출2처럼 코드가 깁니다… 째로탈출2와 마찬가지로 2차원 배열을 조작하는 부분에서 코드가 많이 길어지게 되는데 더 간결하게 만들 수 있도록 연습을 해야할 것 같습니다.
구현은 combine_map함수를 통해서 방향에 맞게 같은 숫자를 합쳐주고 move_map함수를 통해 빈공간을 제거하는것을 반복하도록 구현했습니다. Easy의 경우 5회 반복이기 때문에 대부분 시간초과 경우는 없을 것 입니다.
(테스트 케이스가 문제에 1개 밖에 없다보니 힘들었습니다… 테스트 케이스가 부족하신 분들은 문제 게시판에 가시면 더 찾아보실 수 있습니다.)

#include <iostream>
#include <algorithm>

#define MAP_MAX_SIZE 20
using namespace std;

int map[MAP_MAX_SIZE][MAP_MAX_SIZE];
int N;
int max_dp[6];

void init_map() {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> map[i][j];
        }
    }
}

void copy_map(int(*map)[MAP_MAX_SIZE], int(*tmp_map)[MAP_MAX_SIZE]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            tmp_map[i][j] = map[i][j];
        }
    }
}

void recovery_map(int(*map)[MAP_MAX_SIZE], int(*tmp_map)[MAP_MAX_SIZE]) {
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            map[i][j] = tmp_map[i][j];
        }
    }
}

void combine_map(int dir) {
    // 상
    if (dir == 0) {
        for (int c = 0; c < N; c++) {
            for (int r = 0; r < N - 1; r++) {
                int data1 = map[r][c];

                if (data1 == 0) {
                    continue;
                }

                for (int k = r + 1; k < N; k++) {
                    int data2 = map[k][c];

                    if (data2 == 0) {
                        continue;
                    }
                    else {
                        if (data1 == data2) {
                            map[r][c] *= 2;
                            map[k][c] = 0;
                            r = k;
                        }
                        break;
                    }
                }
            }
        }
    }
    // 하
    else if (dir == 1) {
        for (int c = 0; c < N; c++) {
            for (int r = N-1; r > 0; r--) {
                int data1 = map[r][c];

                if (data1 == 0) {
                    continue;
                }

                for (int k = r - 1; k >= 0; k--) {
                    int data2 = map[k][c];

                    if (data2 == 0) {
                        continue;
                    }
                    else {
                        if (data1 == data2) {
                            map[r][c] *= 2;
                            map[k][c] = 0;
                            r = k;
                        }
                        break;
                    }
                }
            }
        }
    }
    // 좌
    else if (dir == 2) {
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N - 1; c++) {
                int data1 = map[r][c];

                if (data1 == 0) {
                    continue;
                }

                for (int k = c + 1; k < N; k++) {
                    int data2 = map[r][k];

                    if (data2 == 0) {
                        continue;
                    }
                    else {
                        if (data1 == data2) {
                            map[r][c] *= 2;
                            map[r][k] = 0;
                            c = k;
                        }
                        break;
                    }
                }
            }
        }
    }
    // 우
    else if (dir == 3) {
        for (int r = 0; r < N; r++) {
            for (int c = N-1; c > 0; c--) {
                int data1 = map[r][c];

                if (data1 == 0) {
                    continue;
                }

                for (int k = c - 1; k >= 0; k--) {
                    int data2 = map[r][k];

                    if (data2 == 0) {
                        continue;
                    }
                    else {
                        if (data1 == data2) {
                            map[r][c] *= 2;
                            map[r][k] = 0;
                            c = k;
                        }
                        break;
                    }
                }
            }
        }
    }
}

int move_map(int dir) {
    int max_value = 0;

    // 상
    if (dir == 0) {
        for (int c = 0; c < N; c++) {
            for (int r = 0; r < N; r++) {
                max_value = max(max_value, map[r][c]);

                if (map[r][c] == 0 && r != N - 1) {
                    for (int k = r+1; k < N; k++) {
                        if (map[k][c] != 0) {
                            map[r][c] = map[k][c];
                            map[k][c] = 0;
                            max_value = max(max_value, map[r][c]);
                            break;
                        }
                    }
                }
            }
        }
    }
    // 하
    else if (dir == 1) {
        for (int c = 0; c < N; c++) {
            for (int r = N-1; r >= 0; r--) {
                max_value = max(max_value, map[r][c]);

                if (map[r][c] == 0 && r != 0) {
                    for (int k = r - 1; k >= 0; k--) {
                        if (map[k][c] != 0) {
                            map[r][c] = map[k][c];
                            map[k][c] = 0;
                            max_value = max(max_value, map[r][c]);
                            break;
                        }
                    }
                }
            }
        }
    }
    //좌
    else if (dir == 2) {
        for (int r = 0; r < N; r++) {
            for (int c = 0; c < N; c++) {
                max_value = max(max_value, map[r][c]);

                if (map[r][c] == 0 && c != N-1) {
                    for (int k = c + 1; k < N; k++) {
                        if (map[r][k] != 0) {
                            map[r][c] = map[r][k];
                            map[r][k] = 0;
                            max_value = max(max_value, map[r][c]);
                            break;
                        }
                    }
                }
            }
        }
    }
    //우
    else if (dir == 3) {
        for (int r = 0; r < N; r++) {
            for (int c = N-1; c >= 0; c--) {
                max_value = max(max_value, map[r][c]);

                if (map[r][c] == 0 && c != 0) {
                    for (int k = c - 1; k >= 0; k--) {
                        if (map[r][k] != 0) {
                            map[r][c] = map[r][k];
                            map[r][k] = 0;
                            max_value = max(max_value, map[r][c]);
                            break;
                        }
                    }
                }
            }
        }
    }

    return max_value;
}

void dfs(int cnt, int max_value) {
    max_dp[cnt] = max(max_dp[cnt], max_value);

    if (cnt >= 5) {
        return;
    }

    // 상, 하, 좌, 우
    for (int dir = 0; dir < 4; dir++) {
        int tmp_map[MAP_MAX_SIZE][MAP_MAX_SIZE];
        copy_map(map, tmp_map);

        combine_map(dir);                  // 기울인 방향으로 합치기
        int value = move_map(dir);      // 빈칸 땡기기 & 현재 최대값 반환
        dfs(cnt + 1, value);

        recovery_map(map, tmp_map);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin >> N;

    init_map();
    dfs(0, 0);

    cout << max_dp[5] << '\n';

    return 0;
}

2017-10-11 게시 됨2021-03-22 업데이트 됨Algorithm / BOJ5분안에 읽기 (약 824 단어)

<13460> 째로탈출 2

문제 : https://www.acmicpc.net/problem/13460

처음 풀이 방향을 잘못 잡고, 풀이시 여러 예외 사향을 잘못 생각하는 바람에 시간이 오래 걸렸습니다.
코드가 조금 긴 편입니다… 저는 dfs를 활용해서 풀었습니다. 주의해야 할 사항이 몇가지 있었는데,
1. 이미 기울였던 방향과 그 반대방향으로 다시 기울여서는 안된다. (이미 기울였던 방향으로 다시 기울이게 된다면 결과는 같을 것 입니다. 또한 방금 기울였던 방향의 반대로 기울인다면 이전과 같은 상태로 돌아가게 됩니다.)
2. 기울인 후 파란공과 빨간공의 위치가 겹친다면 기울이기 전의 (1) 기울인 방향, (2) 파란공 위치, (3) 빨간공 위치 를 고려하여 다시 위치를 변경해주어야 한다.

위의 2가지 주의사항을 고려해서 푼다면 큰 문제 없이 풀 수 있을것 입니다.

#include <iostream>
#include <algorithm>

#define MAP_MAX_SIZE 10
#define ANS_MAX 11
using namespace std;

char map[MAP_MAX_SIZE][MAP_MAX_SIZE];
int N, M;
int ans = ANS_MAX;
int rx, ry, bx, by, hx, hy;
bool is_r_hall_in, is_b_hall_in;

void init_map() {
    char c;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            cin >> c;
            map[i][j] = c;

            if (c == 'R') {
                rx = i;
                ry = j;
            }
            else if (c == 'B') {
                bx = i;
                by = j;
            }
            else if (c == 'O') {
                hx = i;
                hy = j;
            }
        }
    }
}

int get_deposit_dir(int dir) {
    if (dir == 0) {
        return 1;
    }
    else if (dir == 1) {
        return 0;
    }
    else if (dir == 2) {
        return 3;
    }
    else if (dir == 3) {
        return 2;
    }
}

int get_priority(int dir) { // 0 = 빨간공, 1 = 파란공
    int priority = -1;

    // 상
    if (dir == 0) {
        priority = bx < rx;
    }
    // 하
    else if (dir == 1) {
        priority = bx > rx;
    }
    // 좌
    else if (dir == 2) {
        priority = by < ry;
    }
    // 우
    else if (dir == 3) {
        priority = by > ry;
    }

    return priority;
}

int move_x(int x, int y, int dir) {
    int nx = x;
    char type;

    if (dir == 0) {
        for (int i = x - 1; i > 0; i--) {
            type = map[i][y];
            if (type == '#') {
                break;
            }
            else if (type == 'O') {
                nx = i;
                break;
            }
            else {
                nx = i;
            }
        }
    }
    else {
        for (int i = x + 1; i < N - 1; i++) {
            type = map[i][y];
            if (type == '#') {
                break;
            }
            else if (type == 'O') {
                nx = i;
                break;
            }
            else {
                nx = i;
            }
        }
    }

    return nx;
}

int move_y(int x, int y, int dir) {
    int ny = y;
    char type;

    if (dir == 2) {
        for (int i = y - 1; i > 0; i--) {
            type = map[x][i];
            if (type == '#') {
                break;
            }
            else if (type == 'O') {
                ny = i;
                break;
            }
            else {
                ny = i;
            }
        }
    }
    else {
        for (int i = y + 1; i < M - 1; i++) {
            type = map[x][i];
            if (type == '#') {
                break;
            }
            else if (type == 'O') {
                ny = i;
                break;
            }
            else {
                ny = i;
            }
        }
    }

    return ny;
}

void move(int dir) {
    if (dir == 0 || dir == 1) { // 상, 하
        rx = move_x(rx, ry, dir);
        bx = move_x(bx, by, dir);
    }
    else { // 좌, 우
        ry = move_y(rx, ry, dir);
        by = move_y(bx, by, dir);
    }
}

void check_hall_in() {
    if (bx == hx && by == hy) {
        is_b_hall_in = true;
    }

    if (rx == hx && ry == hy) {
        is_r_hall_in = true;
    }
}

void priority_move(int priority, int dir) {
    if (dir == 0) {
        if (priority == 0) {
            bx = bx + 1;
        }
        else {
            rx = rx + 1;
        }
    }
    else if (dir == 1) {
        if (priority == 0) {
            bx = bx - 1;
        }
        else {
            rx = rx - 1;
        }
    }
    else if (dir == 2) {
        if (priority == 0) {
            by = by + 1;
        }
        else {
            ry = ry + 1;
        }
    }
    else if (dir == 3) {
        if (priority == 0) {
            by = by - 1;
        }
        else {
            ry = ry - 1;
        }
    }
}

void dfs(int pre_dir, int cnt) {
    if (cnt > 10) {
        is_b_hall_in = false;
        is_r_hall_in = false;
        return;
    }

    if (is_b_hall_in) {
        is_b_hall_in = false;
        is_r_hall_in = false;
        return;
    }
    else {
        if (is_r_hall_in) {
            is_b_hall_in = false;
            is_r_hall_in = false;
            ans = min(ans, cnt);
            return;
        }
    }

    int brx = rx;
    int bry = ry;
    int bbx = bx;
    int bby = by;

    // 상, 하, 좌, 우
    for (int dir = 0; dir < 4; dir++) {
        if (dir == pre_dir || dir == get_deposit_dir(pre_dir)) {
            continue;
        }

        int priority = get_priority(dir);

        // 이동 & 홀 인 체크
        move(dir);
        check_hall_in();

        // 공이 겹칠 경우, 우선순위에 따라 이동
        if (rx == bx && ry == by) {
            priority_move(priority, dir);
        }

        if (brx != rx || bry != ry || bbx != bx || bby != by) {
            dfs(dir, cnt + 1);
        }

        rx = brx;
        ry = bry;
        bx = bbx;
        by = bby;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin >> N >> M;

    init_map();
    dfs(-1, 0);

    if (ans == ANS_MAX) {
        cout << -1 << '\n';
    }
    else {
        cout << ans << '\n';
    }

    return 0;
}

2017-10-02 게시 됨2021-03-22 업데이트 됨Algorithm / BOJ1분안에 읽기 (약 201 단어)

<11054> 가장 긴 바이토닉 부분 수열

문제 : https://www.acmicpc.net/problem/11054

먼저 증가하는 수열의 최대 길이와 감소하는 수열의 최대 길이를 구해주었습니다.
그 후 각 자리의 최대 길이를 서로 더해준 후 max 값을 비교하여 해결했습니다.

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int main() {
    int max_value = 0;
    int n;
    cin >> n;
    vector<int> a(n);

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

    vector<int> plus(n); // 증가하는 수열의 최대 길이
    vector<int> minus(n); // 감소하는 수열의 최대 길이

    for (int i = 0; i < n; i++) {
        plus[i] = 1;
        for (int j = 0; j < i; j++) {
            if (a[j] < a[i] && plus[i] < plus[j] + 1) {
                plus[i] = plus[j] + 1;
            }
        }
    }

    for (int i = n-1; i >= 0; i--) {
        minus[i] = 1;
        for (int j = n-1; j > i; j--) {
            if (a[j] < a[i] && minus[i] < minus[j] + 1) {
                minus[i] = minus[j] + 1;
            }
        }
    }

    for (int i = 0; i < n; i++) {
        max_value = max(max_value, plus[i] + minus[i] - 1);
    }

    cout << max_value << '\n';

    return 0;
}

2017-10-02 게시 됨2021-03-22 업데이트 됨Algorithm / BOJ2분안에 읽기 (약 356 단어)

<2632> 피자판매

문제 : https://www.acmicpc.net/problem/2632

피자가 붙어있어야 한다는 조건 때문에 정렬을 할수가 없었습니다. 먼저 A와 B 각각의 피자판에서 만들어 질 수 있는 모든 합의 경우를 map을 사용해 저장한 후 목표하는 크기의 피자를 만들 수 있는 경우를 출력하는식으로 문제를 해결했습니다.

#include <iostream>
#include <vector>
#include <map>

#define MAX_SIZE 1000
using namespace std;

int target;
int m, n;
int a[MAX_SIZE], b[MAX_SIZE];
map<int, int> a_sum, b_sum;

void get_all_sum(int* arr, map<int, int>& sum_map, int size) {
    for (int i = 1; i < size; i++) { // 1개~suze-1개로 만들 수 있는 경우 모두 구하기
        for (int j = 0; j < size; j++) { // 시작하는 피자 순서
            int sum = 0;
            for (int k = 1; k <= i; k++) { // j번째 피자부터 i개 만큼 더하기
                if (j+k-1 < size) {
                    sum += arr[j+k-1];
                } else {
                    sum += arr[j+k-1-size];
                }
            }
            sum_map[sum] = sum_map[sum] + 1;
        }
    }

    int sum = 0;
    for (int i = 0; i < size; i++) { // 피자의 모든 조각(size) 합
        sum += arr[i];
    }
    sum_map[sum] = 1;

    return ;
}

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

    cin >> target >> m >> n;

    for (int i = 0; i < m; i++) {
        cin >> a[i];
    }
    for (int j = 0; j < n; j++) {
        cin >> b[j];
    }

    get_all_sum(a, a_sum, m);
    get_all_sum(b, b_sum, n);

    int cnt = a_sum[target] + b_sum[target]; // a와 b 각각의 피자만 사용해서 만드는 경우
    for (int i = 1; i < target; i++) { // a와 b피자 같이 사용해서 만드는 경우
        if (a_sum[i] && b_sum[target-i]) {
            cnt += (a_sum[i] * b_sum[target-i]);
        }
    }

    cout << cnt << '\n';

    return 0;
}

2017-10-01 게시 됨2021-03-22 업데이트 됨Algorithm / BOJ1분안에 읽기 (약 204 단어)

<5014> 스타트링크

문제 : https://www.acmicpc.net/problem/5014

BFS를 사용해 쉽게 해결할 수 있습니다. 다만 if 문에서 visit 배열로 층의 방문 여부를 체크하기전에 배열의 index가 유효한 범위에 속해있는지 확인을 먼저해주어야 합니다.

#include <iostream>
#include <queue>
#include <vector>

#define MAX_SIZE 1000001
using namespace std;

bool visit[MAX_SIZE];
int cnt[MAX_SIZE];

int main() {
    int f, s, g, u, d; // 전체 층, 현재 층, 목표 층, 업 층, 다운 층
    cin >> f >> s >> g >> u >> d;

    queue<int> q; // 층수
    visit[s] = true;
    cnt[s] = 0;
    q.push(s);

    while(!q.empty()) {
        int now_floor = q.front();
        int now_cnt = cnt[now_floor];
        q.pop();

        int next1 = now_floor + u;
        int next2 = now_floor - d;

        if (next1 < MAX_SIZE && visit[next1] == false) {
            q.push(next1);
            visit[next1] = true;
            cnt[next1] = now_cnt + 1;
        }

        if (next2 > 0 && visit[next2] == false)  {
            q.push(next2);
            visit[next2] = true;
            cnt[next2] = now_cnt + 1;
        }
    }

    if (visit[g] == true) {
        cout << cnt[g] << '\n';
    } else {
        cout << "use the stairs" << '\n';
    }

    return 0;
}

2017-09-29 게시 됨2021-03-22 업데이트 됨Algorithm / BOJ1분안에 읽기 (약 165 단어)

<14501> 퇴사

문제 : https://www.acmicpc.net/problem/14501

N의 범위가 최대 15로, 작은 경우에 속해서 완전 탐색을 했습니다. 상담을 하는 경우와 하지 않는 경우를 나누어 해결합니다.
상담이 필요한 기간에 당일 부터 포함되는 것만 주의하여 범위를 계산하면 될 것 같습니다

#include <iostream>
#include <algorithm>

#define MAX_SIZE 16

using namespace std;

int day[MAX_SIZE];
int pay[MAX_SIZE];
int n;

int sum = 0;

void go(int d, int s) {
    if (d == n + 1) {
        sum = max(sum, s);
        return;
    }

    if (d + day[d] <= n + 1) {
        go(d + day[d], s + pay[d]);
    }
    if (d + 1 <= n + 1) {
        go(d + 1, s);
    }
}

int main(void) {
    cin >> n;

    for (int i = 1; i <= n; i++) {
        cin >> day[i] >> pay[i];
    }

    go(1, 0);

    cout << sum << '\n';

    return 0;
}