문제 개요
문자열 형태의 숫자 n이 주어졌을 때, 그 합이 n과 같아지는 데시바이너리(deci-binary) 수의 최소 개수를 구하는 문제입니다. 여기서 데시바이너리 수란 각 자릿수가 0 또는 1로만 이루어진 십진수를 의미합니다.
예를 들어 입력이 n = "132"라면 출력은 3이 됩니다. 132는 세 개의 데시바이너리 수인 10 + 11 + 111의 합으로 표현할 수 있기 때문입니다.
해결 접근 방식
이 문제는 의외로 간단하게 해결할 수 있습니다. 핵심 아이디어는 n의 각 자릿수 중 가장 큰 숫자가 곧 필요한 데시바이너리 수의 최소 개수라는 점입니다. 특정 자릿수 d를 만들려면 해당 자리에 1이 정확히 d번 더해져야 하므로, 가장 큰 자릿수가 전체 개수의 하한선이 되기 때문입니다.
알고리즘 단계
- result를 1로 초기화합니다.
- n의 각 문자 i에 대해 반복합니다.
- i가 {0, 1}에 속하지 않는다면, result와 i 중 더 큰 값을 result에 저장합니다.
- 반복이 끝나면 result를 반환합니다.
구현 예제
다음 파이썬 코드를 통해 동작 방식을 더 잘 이해해 보겠습니다.
def solve(n):
result = 1
for i in n:
if i not in {0,1}:
result = max(result, int(i))
return result
n = "132"
print(solve(n))
입력
132
출력
3
동작 원리 상세 설명
입력값 "132"를 기준으로 코드의 실행 흐름을 살펴보면 다음과 같습니다.
- 첫 번째 자릿수 '1'은 처리 후에도 max(1, 1) = 1이므로 결과에 영향을 주지 않습니다.
- 두 번째 자릿수 '3'은 0 또는 1이 아니므로 result는 max(1, 3) = 3으로 갱신됩니다.
- 세 번째 자릿수 '2' 역시 0 또는 1이 아니지만 max(3, 2) = 3이므로 결과는 그대로 유지됩니다.
- 최종적으로 3이 반환되며, 이는 132 = 10 + 11 + 111이라는 세 개의 데시바이너리 수 분할과 일치합니다.
이처럼 한 번의 순회만으로 답을 구할 수 있으므로 시간 복잡도는 O(len(n))으로 매우 효율적입니다.