[백준 BOJ] 27674번 A+B (C++/cpp)

문제 설명

https://www.acmicpc.net/problem/27674

27674번: A+B

 

접근 방법 - 정렬을 활용한 그리디 알고리즘 문제

백준의 27674번 문제는 정렬을 활용하여 해결해야 하는 수학적 그리디 알고리즘 문제이다.

해당 문제는, 각 테스트 케이스에서 주어지는 문자열 숫자를 2개의 숫자로 쪼개어 덧셈을 수행할 때의 최댓값을 구하여 출력해야 하는 문제이다.

그리디 알고리즘 문제이기 때문에, 가장 쉽고 편리한 방법으로 연산을 수행하여 정답을 구해내야 한다.

필자의 경우에는, 숫자들을 내림차순 정렬하고 가장 큰 숫자와 가장 작은 숫자로 쪼개어내서 그 둘을 합하게 하였다.

원리는 아래와 같다.

 (ex) "123456"이 입력으로 주어질 때,
1. 내림차순 정렬 결과 :: "654321"
2. 2개의 숫자로 쪼개기 결과 :: "65432" / "1"
3. 합 구하기 :: 65432 + 1 = 65433 -> 정답

좀 더 자세한 내용은 아래에 기재되어 있으니, 혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면 아래의 설명과 코드를 참고해 보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

 

1) 테스트 케이스의 수(n)를 입력받는다.

그리고 위 원리를 코드로 수행하기 위해선, 이다음으로는 숫자를 문자열 형태로 입력받아야 한다.

그렇기 때문에, 입력값 간 충돌이 발생하지 않도록 cin.ignore()를 수행해 준다.

 

2) n의 크기만큼, 반복문을 실행하여 아래의 연산을 취한다.

- 숫자(num)를 문자열 형태로 입력받는다.

- num의 숫자 문자들을 내림차순으로 정렬한다. (아래처럼 compare 함수를 따로 구현하여 내림차순 정렬을 수행한다.)

-  정렬된 결괏값을 2개의 숫자로 쪼개어준 뒤, 이를 숫자형으로 변환한다.

(이때, 입력값의 최대 자릿수를 생각하며 long long int로 2개의 숫자를 받아내도록 한다.)

• 첫 번째 숫자(n1)는 가장 큰 숫자로, 인덱스 0부터 시작하며 길이는 num.length()-1이 되게끔 설정해 준다. (위 예시에선 "65432" 부분)
• 두 번째 숫자(n2)는 가장 작은 숫자로, 인덱스 num.length()-1부터 시작하며 길이는 1이 되게끔 설정해 준다. (위 예시에선 "1" 부분)

- result에 n1와 n2를 더한 값을 저장하고, 이를 출력한다.

 

3) 모든 테스트 케이스에 대한 정답을 출력하였다면, 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#include <string>
#include <algorithm>
#define endl '\n'
using namespace std;

//백준 27674번 코드
bool compare(char a, char b) {
    return a > b;
}

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

    int n;
    cin >> n;
    cin.ignore();

    for (int i = 0; i < n; i++) {
        string num;
        cin >> num;
        sort(num.begin(), num.end(), compare);

        long long int n1 = stoll(num.substr(0, num.length() - 1));
        long long int n2 = stoll(num.substr(num.length() - 1, 1));
        long long int result = n1 + n2;
        cout << result << endl;
    }
}

 

제출 결과

(2023.10.03 백준 27674번 문제 제출 결과)