글 읽기 - 3128번 질문입니다.

wuppu13579 4년 전 0

현 지점에서 가장 가까운 알파벳과의 거리를 통해

최소 거리를 찾는 방식으로 접근했습니다.

이 알고리즘으로 접근했을 때, 어느 부분이 틀렸는지 모르겠습니다ㅠㅠ

이 방식 말고 단순한 DFS 로 풀어봤지만 똑같이 틀렸다고 나왔습니다.

#include <bits/stdc++.h>

using namespace std;

const int MAX = 26;
int matrix[MAX];
string str;

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

    getline(cin, str);

    int size = 0;
    for (int i = 0; i < str.size(); i++) {
        if (str[i] == ' ') continue;
        int num = str[i] - 'A';
        matrix[num]++;
        size++;
    }

    int cnt = size;
    int current = 0;
    int ret = str.size() == size ? 0 : 1;
    vector<char> v;
    while (cnt--) {
        int left_idx = current, right_idx = current;
        int left_length = 0, right_length = 0;

        while (!matrix[left_idx]) {
            left_idx--;
            left_length++;
            if (left_idx == -1) 
                left_idx = 25;
        }

        while (!matrix[right_idx]) {
            right_idx++;
            right_length++;
            if (right_idx == MAX)
                right_idx = 0;
        }

        if (left_length < right_length) {
            matrix[left_idx]--;
            current = left_idx;
            ret += left_length;
        }
        else {
            matrix[right_idx]--;
            current = right_idx;
            ret += right_length;
        }
        v.push_back(current + 'A');
        ret++;
    }
    cout << ret << "\n";
    for (int i = 0; i < v.size(); i++)
        cout << v[i];
    return 0;
}

ho94949 4년 전 0

ABFY 일때 이상한것 같네요.

A->B->Y->F보다 A->Y->B->F가 더 빠릅니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

3128번 질문입니다.

wuppu13579 4년 전 0

ho94949 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말