4번 - 큰 수와 작은 수의 합 - 실전 유형 코딩 테스트 모의고사

03 [1차 모의고사] 2016년도 문제 해설

4번 - 큰 수와 작은 수의 합

큰 수와 작은 수의 합 문제는 두 가지 솔루션으로 풀이할 수 있습니다.

그리디 솔루션

이 문제는 주어지는 숫자의 개수가 적기 때문에 다양한 풀이를 적용할 수 있지만, 결과로 출력해야 할 숫자가 크기 때문에 64비트 정수형을 사용하지 않으면 계산 과정에서 문제가 생길 수 있습니다. 항상 출력 결과가 어떤 범위를 가지게 될 지 고민하시기 바랍니다.

실제 문제지에서는 출력 범위에 대한 언급이 전혀 없었습니다. 즉, 20자리 99999999999999999999와 같은 숫자가 정답이 되는 입력이 들어와도 이상하지는 않다는 이야기죠. 이럴 경우에는 큰 수에 대한 처리까지 작성해야 만점을 받을 수 있습니다.
다만, 시험 방식의 차이를 고려하여 문제의 난이도 조절을 위해 본 모의고사에서는 64비트 정수형 범위 이내로 제한했습니다.

아마 가장 쉽게 떠올릴 수 있는 솔루션은 그리디하게 생각하는 것입니다. 아래와 같은 순서로 접근하면 됩니다.

모든 숫자를 정확히 한 번씩 사용 해야한다.

어떻게 조합하더라도 자릿수는 같다는 걸 알 수 있습니다.

숫자를 배치할 때 앞 자리가 9에 가까운 숫자를 앞으로 꺼내면 유리해보입니다.
마찬가지로 작은 숫자는 앞자리가 1에 가까운 숫자를 앞으로 꺼내면 유리해보입니다.

숫자를 정렬하여 접근하는 방법을 떠올려 볼 수 있습니다.

하지만 이것으로 끝이 아닙니다. 바로 숫자의 가장 앞자리가 같은 예외 경우를 고려해야 합니다. 예를 들어서 32, 3, 34라는 세 숫자를 이어붙이는 케이스를 고민해봅시다. 단순히 대소관계로 정렬하면 3, 32, 34가 됩니다. 이 경우 뒤에서부터 이어붙이는 전략을 택하면 34323이 되는데, 이는 34332라는 반례가 존재합니다. 즉, 3과 32는 앞자리가 서로 같지만 3은 뒤에 다른 3x류의 숫자를 놓아 33...로 이어져 갈 수 있는 반면에 32은 항상 32.... 로 시작하는 패턴을 만들게 됩니다. 하지만 34는 항상 3보다 먼저 쓰는게 유리하다는 걸 알 수 있죠.

그래서 이 문제의 키는 한 자리 숫자에 대한 새로운 대소 관계를 아래와 같이 정의하면 됩니다.

31 < 32 < 3 < 33 < 34 < 35 ...
41 < 42 < 43 < 4 < 44 < 45 ...

이제 이를 구현하는 일이 남았습니다. 물론 수 많은 if문으로 처리할 수 있습니다. 한번 고민해보세요. Java 답안 코드에서는 문자열로 가상의 두 자리 숫자를 만들어 정렬하는 방법을 소개합니다.

예를 들어, 실제로는 4일지라도 정렬을 위한 비교 과정에서는 44처럼 비교하는 겁니다. 첨부된 코드를 참고해보세요.

동적계획법 솔루션

이 문제는 사용해야 할 숫자의 개수가 적고 각 숫자는 사용 한다/안한다 두 경우만이 가능하므로, 어떤 시점에서 숫자들을 사용한 현황을 0과 1로 표현되는 비트로 표현할 수 있습니다. 어떤 숫자 X가 마지막으로(가장 오른쪽에) 사용되었을 때 이 숫자를 포함해 총 k개의 숫자를 사용해서 만들 수 있는 가장 큰 숫자는 무엇일까요?

만약에 이 X를 제외한 (k-1)개의 숫자를 사용하여 만들 수 있는 가장 큰 숫자를 알고있고 그 값을 Y라고 한다면,
이 경우에는 YX와 같이 이어붙이는 것이 이 질문에 대한 답이라고 할 수 있습니다.

즉, 사용하고자 하는 어떤 k개의 숫자에 대하여 이 숫자를 모두 사용하여 만들 수 있는 가장 큰 숫자는

1번째 숫자가 가장 마지막에 사용된 경우 만들 수 있는 가장 큰 숫자
2번 째 숫자가 가장 ...
..
k번째 숫자가 가장 ...

위의 k가지 경우 중 하나라는 걸 알 수 있습니다. 즉, 전체 k개의 숫자로 만들 수 있는 숫자를 조회하기 위하여 k-1개의 숫자를 통해 만들 수 있던 결과에 사용하지 않는다고 가정한 숫자를 뒤에 이어붙이며 만들 수 있습니다. 그리고 이런 방식으로 숫자의 사용현황으로 하나의 상태를 표현할 수 있습니다.

앞서 언급한 아래와 같은 값을 함수 long long dp(S)로 정의해 봅시다.

long long dp(S) := S에 포함 된 모든 숫자를 사용해 총 k개의 숫자를 사용해서 만들 수 있는 가장 큰 숫자
S는 k개의 숫자에 대한 사용 여부를 정수로 표현한 값입니다. 아래의 수식을 참고하세요.
이 처럼 가변적인 길이의 상태를 하나의 정수로 표현하여 상태공간을 설계하는 동적 계획법을 Bit DP라고 합니다.

위와 같은 형태로 동적 계획법이 가능한 형태의 함수 dp(S)를 설계할 수 있으며, 이에 대해 동적계획법을 구현하면 됩니다. 상세한 구현은 아래 C++ 코드를 참고하시기 바랍니다.

최소값에 대해서는 위의 함수를 최소 기준으로 수정하면 구현할 수 있으므로 생략합니다.

답안 코드

아래에 두 언어로 각기 다른 방법을 이용해 작성한 코드를 첨부합니다. 두 가지 언어와 방법을 보고 공부해보세요.

C++ 답안코드

Bit DP를 활용한 풀이입니다.

#include<string>
#include<algorithm>
#include<iostream>
#include<vector>
#include<memory.h>

using namespace std;


int n = 0;

long long numbers[10];


long long max_memo[ 2048 ]; //max_dp 함수를 위한 Memoization 배열 
long long min_memo[ 2048 ]; //min_dp 함수를 위한 Memoization 배열 

/** max_dp(state)
 *   - 각 단어들 중 비트가 1로 표시된 인덱스에 해당하는 숫자들을 모두 사용했을 때
 *     조합해서 만들 수 있는 가장 큰 숫자
 */
long long max_dp(int state)
{
    //이미 계산한 적 있는 값이라면 생략한다
    if(max_memo[state] != -1)
        return max_memo[state];
    
    
    long long & answer = max_memo[state];
    for(int i = 0 ; i < n ; i ++)
    {
        int bits = ( 1 << i );
        if( (state & bits) == 0 )   continue;
        //state에 속한 숫자 들 중 
        //i번째 숫자를 마지막으로 사용했었다면
        //만들 수 있던 최대의 값은 얼마일까?
        
        
        //i번째 숫자를 사용하기 이전의 상태 
        int before_state = state - bits;
        
        //그 때 만들 수 있던 최대의 10진수와
        long long head = max_dp(before_state);
        
        //i번째 숫자
        long long tail = numbers[i];
        
        
        //head를 1~2자리 10진법으로 시프트하여 두 숫자를 이어붙인다.
        if(tail >= 10){
            head *= 100;
        }else{
            head *= 10;
        }
        long long concat = head + tail;
        
        //i번 숫자를 마지막으로 사용한 게 최적해라면 갱신한다
        if(answer == -1 || concat > answer)
            answer = concat;
    }
    
    //최적해를 Memoization하고 반환한다
    return answer;
}


/** min_dp(state)
 *   - 각 단어들 중 비트가 1로 표시된 인덱스에 해당하는 숫자들을 모두 사용했을 때
 *     조합해서 만들 수 있는 가장 작은 숫자
 */
long long min_dp(int state)
{
    if(min_memo[state] != -1)
        return min_memo[state];

    
    long long & answer = min_memo[state];
    for(int i = 0 ; i < n ; i ++)
    {
        int bits = ( 1 << i );
        if( (state & bits) == 0 )   continue;
        
        int before_state = state - bits;
        
        long long head = min_dp(before_state);
        long long tail = numbers[i];
        
        if(tail >= 10){
            head *= 100;
        }else{
            head *= 10;
        }
        
        long long concat = head + tail;
        if(answer == -1 || concat < answer)
            answer = concat;
    }
    
    return answer;
}

int main(){
    memset(max_memo, -1, sizeof(max_memo));
    memset(min_memo, -1, sizeof(min_memo));
    
    
    cin >> n;
    for(int i = 0 ; i < n ; i++){
        cin >> numbers[i];
        
        int bits = (1 << i);
        max_memo[bits] = min_memo[bits] = numbers[i];
    }
    
    int full_bits = (1 << n) -1;
    long long max_answer = max_dp(full_bits);
    long long min_answer = min_dp(full_bits);
    long long answer = min_answer + max_answer;
    cout << answer << endl;
    
    
    return 0;
}

cpp

Java 답안 코드

문자열 정렬을 이용한 그리디한 풀이입니다.

import java.io.*;
import java.util.*;


class Main {
    public static final Scanner scanner = new Scanner(System.in);

    public static void main(String[] args) {
			//사용할 숫자의 갯수를 입력받는다 
			int n = scanner.nextInt();
			
			//실제로는 숫자지만 문자열로서 다루면 훨씬 코드가 간결해지므로 이렇게 입력받는다.
			String[] numbers = new String[n];
			for(int i = 0 ; i < n ; i ++){
				numbers[i] = scanner.next();
			}
			
			//숫자들을 정렬한다.
			//정렬하는 기준은 단순 사전순이 아니라 따로 정의한다 
			Arrays.sort(numbers, new Comparator<String>() {
				@Override
				public int compare(String o1, String o2) {
					//일반적으로 작은 숫자가 앞으로 오도록 정렬하면 차례로 이어붙이면 가장 작은 숫자를 만들 수 있을 것 같다 
					
					//하지만
					//하나는 두 글자이고 하나는 한 글자일 때 앞 자리가 같은 경우가 정렬의 예외 케이스가 된다.
					//예를 들어서 큰 숫자를 만들 때 사용할 수 있는 숫자가 65, 6, 67 이 있다면
					// 67 < 6 < 65 순으로 사용하는게 가장 유리하다
					//이 경우를 예외처리 해주기 위하여 한 글자의 숫자를 두 숫자가 이어붙인 것 처럼 생각해서 정렬한다 
					
					//각 숫자가 한 글자라면 복사해서 두 글자 처럼 취급해서 정렬한다
					//예: 5 -> 55
					if( o1.length() == 1 )
						o1 = o1 + o1;
					
					if( o2.length() == 1)
						o2 = o2 + o2;
					
					//그 후 일반적인 문자열의 사전순 정렬을 따른다.
					//(자릿수가 같으므로 일반적인 숫자의 대소비교와 같다.)
					return o1.compareTo(o2);
				}
			});

			String max = ""; //정렬된 숫자들을 뒤에서부터 이어붙인다
			String min = ""; //정렬된 숫자들을 앞에서부터 이어붙인다 
			for(int i = 0 ; i < n ; i ++)
			{
				max += numbers[n-i-1];
				min += numbers[i];
			}

			//만들어진 정답 문자열들을 숫자로 변환하고
			long max_value = Long.parseLong(max);
			long min_value = Long.parseLong(min);
			
			//두 값을 더하여 정답을 만들고 출력한다
			long answer = max_value + min_value;
			System.out.println(answer);
		}
}

java

질문하기

추가 자료

추가 자료가 없습니다

여기서 새로운 학습 자료를 확인하세요!
선생님이 추가한 자료들을 바로 확인할 수 있어요.