[알고리즘] 만들 수 없는 숫자 Python

나동빈 님의 "이것이 취업을 위한 코딩 테스트다 with 파이썬" 책에 수록된

만들 수 없는 숫자 문제입니다 (p.314)

 

이 문제는 그리디 유형으로 분류하셨습니다

그리디 알고리즘은 현재 상태에서 가장 좋은 것(최적)을 선택하는 알고리즘입니다

 

## 문제풀이 과정

[접근방법]

어떤 수까지를 만들 수 있다면, 거기에 하나 더 큰 수 (target)를 만들려고 하는 수로 놓습니다 

예를들어 4까지 만들 수 있고 5를 만들 수 있는 지 확인하려고 합니다 (target = 5)

1,2,3,4를 만들 수 있으니 이번에 나온 수가 5와 같거나 작으면 5를 만들 수 있습니다

왜냐하면 5와 같으면 5를 만들 수 있고 5보다 작은 경우는 앞서에 만들 수 있었던 숫자 조합(1,2,3,4)에 이번 수를 더하면 만들 수 있기 때문입니다

 

이렇게 풀기 위해서 우선 수를 정렬하고

위의 접근 방법으로 문제를 해결합니다

 

from typing import List


def get_unreachable_integer(numbers: List[int]):
    numbers.sort()

    # 처음에 1을 만들 수 있는 상태인지 체크
    target = 1

    for number in numbers:
        # 만들려는 숫자보다 현재 숫자가 더 크면 못 만듭니다
        if target < number:
            break
        target += number

    return target

 

 

## 문제를 풀고나서...

이리저리 한참을 고민해서 풀어보고 못 풀어서 답을 확인하고 풀이가 쉬워서 놀랐습니다

제 생각에는 정확히 그리디 알고리즘 문제는 아닌 거 같고

그리디 알고리즘의 근본적인 사고법(?)과 알고리즘 문제 많이 풀어본 능력이 있으면 풀 수 있다고 생각했습니다