큰 수와 작은 수의 합 문제는 두 가지 솔루션으로 풀이할 수 있습니다.
이 문제는 주어지는 숫자의 개수가 적기 때문에 다양한 풀이를 적용할 수 있지만, 결과로 출력해야 할 숫자가 크기 때문에 64비트 정수형을 사용하지 않으면 계산 과정에서 문제가 생길 수 있습니다. 항상 출력 결과가 어떤 범위를 가지게 될 지 고민하시기 바랍니다.
99999999999999999999
와 같은 숫자가 정답이 되는 입력이 들어와도 이상하지는 않다는 이야기죠. 이럴 경우에는 큰 수에 대한 처리까지 작성해야 만점을 받을 수 있습니다.아마 가장 쉽게 떠올릴 수 있는 솔루션은 그리디하게 생각하는 것입니다. 아래와 같은 순서로 접근하면 됩니다.
하지만 이것으로 끝이 아닙니다. 바로 숫자의 가장 앞자리가 같은 예외 경우를 고려해야 합니다. 예를 들어서 32, 3, 34라는 세 숫자를 이어붙이는 케이스를 고민해봅시다. 단순히 대소관계로 정렬하면 3, 32, 34가 됩니다. 이 경우 뒤에서부터 이어붙이는 전략을 택하면 34323이 되는데, 이는 34332라는 반례가 존재합니다. 즉, 3과 32는 앞자리가 서로 같지만 3은 뒤에 다른 3x류의 숫자를 놓아 33...로 이어져 갈 수 있는 반면에 32은 항상 32.... 로 시작하는 패턴을 만들게 됩니다. 하지만 34는 항상 3보다 먼저 쓰는게 유리하다는 걸 알 수 있죠.
그래서 이 문제의 키는 한 자리 숫자에 대한 새로운 대소 관계를 아래와 같이 정의하면 됩니다.
이제 이를 구현하는 일이 남았습니다. 물론 수 많은 if
문으로 처리할 수 있습니다. 한번 고민해보세요. Java
답안 코드에서는 문자열로 가상의 두 자리 숫자를 만들어 정렬하는 방법을 소개합니다.
이 문제는 사용해야 할 숫자의 개수가 적고 각 숫자는 사용 한다/안한다 두 경우만이 가능하므로, 어떤 시점에서 숫자들을 사용한 현황을 0과 1로 표현되는 비트로 표현할 수 있습니다. 어떤 숫자 X가 마지막으로(가장 오른쪽에) 사용되었을 때 이 숫자를 포함해 총 k개의 숫자를 사용해서 만들 수 있는 가장 큰 숫자는 무엇일까요?
즉, 사용하고자 하는 어떤 k개의 숫자에 대하여 이 숫자를 모두 사용하여 만들 수 있는 가장 큰 숫자는
위의 k가지 경우 중 하나라는 걸 알 수 있습니다. 즉, 전체 k개의 숫자로 만들 수 있는 숫자를 조회하기 위하여 k-1개의 숫자를 통해 만들 수 있던 결과에 사용하지 않는다고 가정한 숫자를 뒤에 이어붙이며 만들 수 있습니다. 그리고 이런 방식으로 숫자의 사용현황으로 하나의 상태를 표현할 수 있습니다.
앞서 언급한 아래와 같은 값을 함수 long long dp(S)
로 정의해 봅시다.
위와 같은 형태로 동적 계획법이 가능한 형태의 함수 dp(S)
를 설계할 수 있으며, 이에 대해 동적계획법을 구현하면 됩니다. 상세한 구현은 아래 C++ 코드를 참고하시기 바랍니다.
아래에 두 언어로 각기 다른 방법을 이용해 작성한 코드를 첨부합니다. 두 가지 언어와 방법을 보고 공부해보세요.
Bit DP를 활용한 풀이입니다.
문자열 정렬을 이용한 그리디한 풀이입니다.