[백준] 9440번 숫자 더하기 파이썬 풀이

 

[문제]

9440번: 숫자 더하기

---

[코드]

import sys
input = sys.stdin.readline

while True:
    num = list(map(int, input().split()))
    if num[0] == 0:
        break

    n = num[0]
    number = sorted(num[1:])
    
    num1, num2 = str(), str()
    for i in range(n):
        if number[i] != 0:
            num1, num2 = str(number[i]), str(number[i+1])
            number.pop(i)
            number.pop(i)
            break
    for i in range(0, len(number), 2 ):
        num1 += str(number[i])
        if i < len(number) - 1:
            num2 += str(number[i+1])


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

---

[해설]

'그리디'문제이다 

지금 당장 최적의 선택을 선택해서 문제를 해결 하는 전형적인 문제이다

 

이 문제의 핵심은 아래와 같다

주어진 수를 활용해서 두개의 수를 구성하고 이 두개의 수가 최소값이 되게 만들어야한다

 

즉, 주어진 수를 활용한 두수의 합이 최솟값이 되는 수를 찾는 것이 이 문제의 핵심이다

 

우선 문제에서 요구하는것이 0을 입력했을 때 프로그램이 종료되는 것이기 때문에 while 문을 활용한다

그리고 input값으로 num이라는 변수를 이용해 활용할 수를 받는다 

여기서 만약 num의 첫번째 수가 0이라면 프로그램을 종료하게 한다

import sys
input = sys.stdin.readline

while True:
    num = list(map(int, input().split()))
    if num[0] == 0:
        break

그리고 0이 아니라면 전체 수의 크기를 n으로 받고

num의 첫번째 값을 제외한 나머지를 number라는 리스트로 다시 인덱싱 한다 (처음 받는 리스트의 첫번째는 사용할 수의 크기이기 때문이다)

 

이제 우리는 이 number이라는 리스트를 활용해서 수를 구성할 것이다

우선 핵심은 숫자 0이 우리가 만들 두수의 맨앞으로 갈 수 없다는 것이다

따라서 우리는 초기 숫자, 쉽게 말해서 만들 수 의 맨앞자리를 0을 제외하고 선택해 주어야한다

 

n = num[0]
    number = sorted(num[1:])

    num1, num2 = str(), str()

 

우서 number는 무작위 순서이므로 정렬을 해준다

그리고 우리가 만들 두 수를 num1, num2로 지정하고 형은 str()으로 지정한다 [int로 하게되면 그냥 수를 더해버려 자릿수를 지정할 수 없다]

    for i in range(n):
        if number[i] != 0:
            num1, num2 = str(number[i]), str(number[i+1])
            number.pop(i)
            number.pop(i)
            break

첫번째 for문은 초기 수를 지정하는 for문이다. 즉, 정렬된 number 리스트의 0이 아닌 가장 작은 수를 num1의 가장 앞자리로 지정하고 그 다음수를 num2의 가장 앞자리로 지정한다 그리고 number에서 이 수들을 제거하고 for문을 종료한다

 

 

이제 남은 수들을 num1과 num2에 순서대로 넣어주면 된다 

ex) 1 2 7 8 9 경우 앞에 1,2는 앞의 for문으로 num1 = '1', num2= '2'에 추가되었고 number에서 사라져 현재 number = [7, 8, 9]이다 .

    for i in range(0, len(number), 2 ):
        num1 += str(number[i])
        if i < len(number) - 1:
            num2 += str(number[i+1])

이제 두번째 for 문을 활용해서 숫자를 추가한다 

0부터 number의 len 까지 2개씩 커지는i의  for 문을 구성해서 num1에 추가한다 

그리고 i가 len(number)-1 보다 작을 때 num2에는 i+1의 수를 추가해준다 만약 i == len(number)-1 된다면 마지막 숫자에 도착한 것이기 때문에 num2에 숫자를 추가해줄 필요가 없다.

 

이제 str 형으로 저장된 num1과 num2를 형변환 하여 더해준 값을 출력하기만 하면 문제해결!!

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

 

 

문제 핵심요약

• 그리디문제 해결방법
• 작은수에서 - 큰수로 추가해주는 흐름 생각하기
• 가장 작은 수가 0일때 해결방법 생각하기