[Python] 3687 성냥개비

[Gold II] 성냥개비 - 3687 

[문제 링크](https://www.acmicpc.net/problem/3687)

---

💻 문제 정의

0 ~ 9의 숫자들은 성냥개비로 표현할 수 있다. 성냥개비의 개수가 주어졌을 때, 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 큰 수를 출력하는 문제이다.

💡 접근 및 설계

다이나믹 프로그래밍을 이용하여 문제 접근

성냥개비의 개수에 따라 만들 수 있는 숫자는 정해져 있다. 2개일 때는 1, 3개일 때는 7, 4개일 때는 4, 5개일 때는 2, 3, 5, 6개일 때는 0, 6, 9, 7개일 때는 8. 즉 성냥개비가 8개인 경우에는 성냥개비 2개로 만들 수 있는 수 + 성냥개비 6개로 만들 수 있는 수 / 성냥개비 3개로 만들 수 있는 수 + 성냥개비 5개로 만들 수 있는 수 / 성냥개비 4개로 만들 수 있는 수 2개 로 나타낼 수 있다.

즉, 2 ~ 7개로 만들 수 있는 숫자의 값을 미리 정해놓으면 이후 성냥개비의 개수가 추가됨에 따라 최솟값 또는 최댓값을 쉽게 구할 수 있게 된다.

✏️ 알고리즘 풀이

def makeMin(num):
    INF = 1_000_000_000_000_000

    minNum = [INF] * 101
    minNum[2] = 1
    minNum[3] = 7
    minNum[4] = 4
    minNum[5] = 2 # [2, 3, 5]
    minNum[6] = 6 # [0, 6, 9]
    minNum[7] = 8

    arr = [INF, INF, 1, 7, 5, 2, 0, 8] # 각 개수마다 만들수 있는 가장 작은 수
    for i in range(8, 101):
        for j in range(2, 8): # 0개, 1개는 존재하지 않으므로, 2~8개로 만들 수 있는 수를 붙였을 때, 현재 수보다 큰지 판별
            minNum[i] = min(minNum[i], int(str(minNum[i-j]) + str(arr[j])))

    return minNum[num]

최솟값을 반환하는 makeMin함수이다. 2 ~ 7개의 성냥개비로 만들 수 있는 숫자의 최솟값을 미리 정의한다. 예외로 6개로 만들 수 있는 수 [0, 6, 9] 중에서 숫자 0은 0으로 시작하기 때문에 존재할 수 없다고 판단. 따라서 6으로 정의한다.

이후 arr리스트에는 각 개수마다 만들 수 있는 숫자의 최솟값을 정의한다.

이후 DP 알고리즘에 의해 성냥개비 8 ~ 100개로 만들 수 있는 숫자들의 값을 구한다. 성냥개비 i개로 만들 수 있는 숫자는 성냥개비 i-j개로 만든 숫자 + 성냥개비 j개로 만들 수 있는 숫자의 최솟값이 된다.

def makeMax(num):
    maxNum = [0] * 101
    maxNum[2] = 1
    maxNum[3] = 7

    arr = [0, 0, 1, 7] # 1, 7 만으로 가장 큰 수를 만들 수 있음
    for i in range(4, 101):
        for j in range(2, 4):
            maxNum[i] = max(maxNum[i], int(str(maxNum[i-j]) + str(arr[j])))

    return maxNum[num]

최댓값을 반환하는 makeMax함수이다. 최댓값은 최솟값과는 다르게, 7과 1을 만드는 성냥개비의 개수가 현저히 적어 7과 1 만으로 숫자를 만드는 것이 가장 좋다. (성냥개비가 6개 주어졌다고 가정했을 때, 9를 만드는 것 보다 77, 77보다 111을 만드는 것이 더 크다.)

따라서 1과 7만으로 큰 수를 충분히 만들 수 있게된다. 로직은 makeMin함수와 동일하다.

def makeMax(num):
    if num % 2 == 1:
        return int("7" + "1" * ((n - 3) // 2))
    else:
        return int("1" * (n // 2))

조금 더 직관적이게 생각해보면, 성냥개비가 짝수 개이면 1로만 숫자를 구성할 수 있을거고, 성냥개비가 홀수 개이면 맨 앞자리만 7이고 나머지는 1로 채운 수가 가장 큰 수가 될 것이다.

🗒️ 최종 제출 코드

# 3687 성냥개비

def makeMin(num):
    INF = 1_000_000_000_000_000

    minNum = [INF] * 101
    minNum[2] = 1
    minNum[3] = 7
    minNum[4] = 4
    minNum[5] = 2 # [2, 3, 5]
    minNum[6] = 6 # [0, 6, 9]
    minNum[7] = 8

    arr = [INF, INF, 1, 7, 5, 2, 0, 8] # 각 개수마다 만들수 있는 가장 작은 수
    for i in range(8, 101):
        for j in range(2, 8): # 0개, 1개는 존재하지 않으므로, 2~8개로 만들 수 있는 수를 붙였을 때, 현재 수보다 큰지 판별
            minNum[i] = min(minNum[i], int(str(minNum[i-j]) + str(arr[j])))

    return minNum[num]

def makeMax(num):
    maxNum = [0] * 101
    maxNum[2] = 1
    maxNum[3] = 7

    arr = [0, 0, 1, 7] # 1, 7 만으로 가장 큰 수를 만들 수 있음
    for i in range(4, 101):
        for j in range(2, 4):
            maxNum[i] = max(maxNum[i], int(str(maxNum[i-j]) + str(arr[j])))

    return maxNum[num]

T = int(input())
for _ in range(T):
    num = int(input())
    print(makeMin(num), makeMax(num))

---

💭 오늘의 회고

DP는 역시 너무나 어렵다. 생각하는 것 조차 쉽지 않을 뿐더러, 방법을 떠올려도 코드로 옮겨 작성하는 것 또한 쉽지 않다.

DP문제는 항상 느끼는거지만, 다른 문제들에 비해 문제에 제시된 조건이 굉장히 중요한 포인트인 것 같다. 이번 문제의 핵심은 성냥개비의 범위 (2 ≤ n ≤ 100) 라고 생각한다. 해당 조건이 있기 때문에 maxNum, minNum 리스트를 정의할 수 있게되고, 결과적으로 TopDown, BottopUp 방식의 Dynamic Programming이 완성될 수 있다고 생각한다.

결론 : 문제를 다시 한 번 잘 읽도록 하자