[정올] 2712 : 두 수의 최소합

http://jungol.co.kr/bbs/board.php?bo_table=pbank&wr_id=1975&sca=99&page=17 

JUNGOL

 

사용 언어: C

 

#include <stdio.h>
#define SWAP(x, y) {int t = (x); (x) = (y); (y) = t;} 
int N;
int arr[15];

int main(void) {

    int num1 = 0, num2 = 0;

    scanf("%d", &N);
    // 입력받음
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }

// 정렬 (내림차순)
    for (int i = 0; i < N - 1; i++) {
        for (int j = i + 1; j < N; j++) {
            if (arr[i] < arr[j]) {
                SWAP(arr[i], arr[j]);
            }
        }
    }

	// 맨 끝이 0이면 0이 아닌 최소값과 교체
    if (arr[N-1] == 0) {
        int j = N-2;
        for (; j >=0; j--) {
            if (arr[j] != 0) break;
        }
        SWAP(arr[N-1], arr[j]);
    }
    // 맨 끝에서 두 번째가 0이면 0이 아닌 두 번째 최소값과 교체
    if (arr[N-2] == 0) {
        int j = N-2;
        for (; j >=0; j--) {
            if (arr[j] != 0) break;
        }
        SWAP(arr[N-2], arr[j]);
    }
    
    // 자릿수별로 계산해서 두 정수 구하기
    int d = 1;
    for (int i = 0; i < N; i++) {
        if (i % 2 == 0) {
            num1 += d * arr[i];
        }
        else {
            num2 += d * arr[i];
            d *= 10;
        }
    }
    
    printf("%d", num1 + num2);
    return 0;
}

 

가장 큰 자릿수에 가장 작은 수를 넣어주는 방식을 이용하는 게 기본 아이디어이다.

 

두 정수를 만들기 위해 배열에 저장한 정수들을 하나하나 추출해내면 되는데, 여기에서 주의할 점은 0이다.

0으로 시작하는 정수는 만들 수 없기 때문에, 정렬했을 때, 맨 뒤가 0인 경우 0보다 큰 정수 중 최소값을 찾아서 걔를 앞으로 놔줘야 한다. 

두 정수 모두 0으로 시작하면 안되기 때문에 맨 뒤에서 두 개의 0을 바꿔줘야 한다. 

 

0이 아닌 최소값을 찾기 위해 루프를 돌기보단, 애초에 입력받을 때 0의 개수를 받아두었다가.

 arr[zcnt] 이런 식으로 바로 접근하는 것이 효율적일 것 같다. 

 

개선한 코드:

#include <stdio.h>
#define SWAP(x, y) {int t = (x); (x) = (y); (y) = t;} 
int N;
int arr[15];

int main(void) {

    int num1 = 0, num2 = 0;
    int zcnt = 0;

    // 입력받음
    scanf("%d", &N);
    for (int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
        if (arr[i] == 0) zcnt++;
    }

    // 정렬
    for (int i = 0; i < N - 1; i++) {
        for (int j = i + 1; j < N; j++) {
            if (arr[i] < arr[j]) {
                SWAP(arr[i], arr[j]);
            }
        }
    }

    if (arr[N-1] == 0) {
        arr[N - 1] == arr[N-1-zcnt];
    }
    if (arr[N-2] == 0) {
        arr[N - 2] == arr[N-2-zcnt];
    }
   
    int d = 1;
    for (int i = 0; i < N; i++) {
        if (i % 2 == 0) {
            num1 += d * arr[i];
        }
        else {
            num2 += d * arr[i];
            d *= 10;
        }
    }
    
    printf("%d", num1 + num2);
    return 0;
}