알고리즘 노트: Carry 피하기 2

문제 설명

문제 유형: 완전탐색
n개의 숫자 중 서로 다른 3개의 숫자를 선택하여, carry가 발생하지 않으면서 나올 수 있는 숫자 합의 최댓값을 계산하는 프로그램을 작성합니다.

Carry란?

각 자리수를 더했을 때 10을 넘어가는 경우 carry가 발생합니다. 예를 들어:

  • 3 + 6 = 9 (carry 발생하지 않음)
  • 5 + 7 = 12 (carry 발생)

입력 형식

  1. 첫 번째 줄에 n이 주어집니다.
  2. 두 번째 줄부터 n개의 줄에 숫자가 주어집니다.
    • 3 ≤ n ≤ 20
    • 1 ≤ 숫자의 범위 ≤ 10,000

출력 형식

carry가 발생하지 않으면서 3개의 숫자의 합의 최댓값을 출력합니다.
모든 숫자쌍에서 carry가 발생할 경우 -1을 출력합니다.

예제

입력

6
522
6
84
7311
19
9999

출력

7839

설명

522, 6, 7311을 선택하면, 각 자리수의 합에서 carry가 발생하지 않으므로 합은 7839입니다.

내 풀이

코드

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

#define MAX_N 20

int n;
int arr[MAX_N];

/* Carry 발생 여부를 확인하는 함수 */
bool IsCarry(int i, int j, int k) {
    int cnt = 0;
    string a = to_string(arr[i]), b = to_string(arr[j]), c = to_string(arr[k]);

    if(a.length() <= b.length()) cnt = a.length();
    else cnt = b.length();
    int l = 1;
    while(cnt) {
        int i = a[a.length() - l] - '0', j = b[b.length() - l] - '0';
        if(i + j >= 10) return false;
        cnt--;
        l++;
    }

    string d = to_string(arr[i] + arr[j]);

    if(d.length() <= c.length()) cnt = d.length();
    else cnt = c.length();
    l = 1;
    while(cnt) {
        int i = d[d.length() - l] - '0', j = c[c.length() - l] - '0';
        if(i + j >= 10) return false;
        cnt--;
        l++;
    }
    return true;
}

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

    int max_sum = -1;

    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            for(int k = j + 1; k < n; k++) {
                if(IsCarry(i, j, k))
                    max_sum = max(max_sum, arr[i] + arr[j] + arr[k]);
            }
        }
    }

    cout << max_sum;
    return 0;
}

풀이 설명

  1. 숫자를 string으로 변환하여 각 자리수를 비교.
  2. 세 숫자의 각 자리수를 더했을 때 10을 넘으면 carry로 판별.
  3. 모든 가능한 조합을 탐색해 carry가 발생하지 않는 합의 최댓값을 계산.

문제점

  • 복잡도: 문자열 변환 및 자리수 비교가 비효율적.
  • 가독성: 코드가 직관적이지 않음.

모범답안

코드

#include <iostream>
#include <algorithm>
#include <string>
using namespace std;

#define MAX_N 20

int n;
int arr[MAX_N];

/* Carry 발생 여부를 확인하는 함수 */
bool IsCarry(int i, int j, int k) {
    if(arr[i] % 10 + arr[j] % 10 + arr[k] % 10 >= 10) return true;
    if(arr[i] % 100 / 10 + arr[j] % 100 / 10 + arr[k] % 100 / 10 >= 10) return true;
    if(arr[i] % 1000 / 100 + arr[j] % 1000 / 100 + arr[k] % 1000 / 100 >= 10) return true;
    if(arr[i] % 10000 / 1000 + arr[j] % 10000 / 1000 + arr[k] % 10000 / 1000 >= 10) return true;
    return false;
}

int main() {
    cin >> n;
    for(int i = 0; i < n; i++) cin >> arr[i];
    int ans = -1;
    for(int i = 0; i < n; i++) {
        for(int j = i + 1; j < n; j++) {
            for(int k = j + 1; k < n; k++) {
                if(IsCarry(i, j, k) == false)
                    ans = max(ans, arr[i] + arr[j] + arr[k]);
            }
        }
    }
    cout << ans;
    return 0;
}

풀이 설명

  1. 각 자리수를 직접 계산하여 carry 발생 여부를 효율적으로 확인.
  2. 가능한 모든 조합을 탐색하여 최대 합을 계산.

개선된 점

  • 효율성: 문자열 변환 없이 직접 자리수를 비교.
  • 가독성: 코드가 더 간단하고 직관적.

요약

항목 내 풀이 모범답안
효율성 문자열 변환으로 인해 비효율적 직접 자리수 계산으로 효율적
가독성 복잡하고 직관적이지 않음 간단하고 직관적임

완전 탐색의 문제를 끝까지 포기하지 않고 문제를 풀려고 노력하였다.

그러나, 앞으로도 여러 완전탐색 문제를 풀면서, (모범답안)문자열 변환 없이 숫자를 직접 계산하는 방식처럼 더 직관적이고 빠른 해결책을 찾는 연습이 필요하다.