[solved.ac 실버3] 9440_숫자 더하기 (파이썬, 그리디, 정렬)

밑의 사진을 클릭하면 문제 링크로 이동합니다

제한사항

문제

강민이가 초등학교 3학년일 때, 담임선생님이 이런 문제를 냈었다.

숫자 1, 2, 7, 8, 9 를 사용해서 만든 두 숫자를 더했을 때, 나올 수 있는 가장 작은 수는 무엇일까요?

강민이는 이 문제의 답이 207(78 + 129)이라고 생각했다. 그런데 선생님은 책 4페이지에 있는 비슷한 문제를 모두 풀어오라는 숙제를 내셨다. 

작년부터 프로그래밍을 시작한 강민이는 이런 숙제보다 코딩을 더 재밌어했다. 그래서 강민이는 이 숙제를 코딩으로 해결하기로 했다!

어린 강민이를 위해 코딩을 도와주자.

입력

한 줄에 하나씩 연습문제가 주어진다.

각 줄에서 첫 번째로 나오는 정수 N (2 ≤ N ≤ 14) 은 연습문제에서 사용될 숫자의 개수이다.

두 번째부터 사용될 N개의 숫자가 주어진다. 0이 아닌 수가 최소 2개 이상 존재한다

마지막 줄에 0을 입력하면 프로그램이 종료된다.

출력

각 연습문제마다 정답을 출력한다.

예제

 

---

나의 풀이

주어진 숫자들을 모두 사용해야 한다. 이때 만들어지는 두 수의 자릿수를 비슷하게 만들어야 한다.

예를 들어 8개의 숫자가 주어지면 4자리 수, 4자리수로 만들어야 하고, 7개의 숫자가 주어지면 4자리 수, 3자리 수로 만들어야 한다. 그래야 최솟값을 구할 수 있다.

각 숫자를 작은 숫자에서 큰 숫자 순서로 배치하면 작은 수를 만들 수 있는데 이때 주어지는 숫자 중에는 0도 있기 때문에 숫자의 맨 앞에 0이 오지 않도록 해야 한다.

이러한 조건은 문제에 직접적으로 나타나있지는 않지만 0이 아닌 수가 최소 2개 이상 존재한다는 조건에서 유추할 수 있다.

• 주어진 수들을 오름차순으로 정렬한다.
• 0이 아닌 가장 작은 숫자를 각각 num1과 num2에 할당한다.
• 주어진 수에서 위에서 할당한 두 숫자를 제외하고 남은 숫자들을 차례로 분배한다.

이때 num1에 가장 작은 0이 아닌 수가 주어졌다면 이후에 분배할 때도 num1부터 분배해주어야 한다.

주어진 수가 짝수 개라면 같은 길이의 숫자가 나오기 때문에 상관 없지만 홀수 개가 주어진다면 둘 중 하나의 길이가 더 길 것이다. 그래서 더 길게 될 num1에 가장 작은 수를 맨 앞에 배치하고, 이후 숫자들을 분배한다.

while True:
    n = input()
    if n == '0': break
    li = sorted(n.split()[1:])
    num1, num2 = str(), str()
    for i in range(len(li)):
        if li[i] != '0':
            num1, num2 = li[i], li[i + 1]
            li = li[:i] + li[i + 2:]
            break
    for i in range(0, len(li), 2):
        num1 += li[i]
        if i < len(li) - 1:
            num2 += li[i + 1]

    print(int(num1) + int(num2))

n이 0이면 프로그램(반복문)을 종료했다.

주어진 수를 정렬한 후에 숫자들의 개수를 나타내는 첫 번째 숫자를 제거한 리스트를 li에 담는다.

그리고 0이 아닌 최초의 수를 찾아 num1에 할당하고 그 다음 수를 num2에 할당한 후에 li에서 두 수를 제거하고, 탐색을 종료한다.

이제 남은 숫자들을 차례로 분배하면 num1과 num2에는 더했을 때 가장 작게 될 두 수가 남게 된다.

이 두 수를 정수로 변환해 더한 값을 출력하면 된다.

 

채점 결과