문제

https://www.acmicpc.net/problem/3687

성냥개비는 숫자를 나타내기에 아주 이상적인 도구이다. 보통 십진수를 성냥개비로 표현하는 방법은 다음과 같다.

성냥개비의 개수가 주어졌을 때, 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 큰 수를 찾는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 테스트 케이스는 최대 100개 이다. 각 테스트 케이스는 한 줄로 이루어져 있고, 성냥개비의 개수 n이 주어진다. (2 ≤ n ≤ 100)

출력

각 테스트 케이스에 대해서 입력으로 주어진 성냥개비를 모두 사용해서 만들 수 있는 가장 작은 수와 가장 큰 수를 출력한다. 두 숫자는 모두 양수이어야 하고, 숫자는 0으로 시작할 수 없다.

아이디어

👎 시간 초과
1. 작은 수 구하기
1.1 작은 수는 자릿수를 최대한 줄여야하기 때문에 s 리스트에 있으면 한 자리수로 출력한다.
1.2 s 리스트에 없는 경우, 2자리 이상이므로 맨 앞 자리는 1로 채우고 나머지는 0으로 채운뒤 마지막은 가능한 숫자 중에서 가장 작은 값으로 채운다.
2. 큰 수 구하기
2.1 큰 수는 자릿수를 최대한 늘리는게 좋기 때문에 2,3인 경우를 제외하고 2자리 이상으로 만들어준다.
2.2 성냥을 제일 적게 사용하여 자릿수를 늘리는 방법은 3개가 필요한 7을 앞에 두고 나머지를 1로 채우는 것이다.
2.3 짝수인 경우, 1을 만드는데 성냥 2개가 필요하므로 모두 1로 채워 자릿수를 늘린다.
2.4 홀수인 경우, 맨 앞자리를 7로 채우고 나머지를 1로 채운다.

내 코드(Python) #Error

:: 시간 초과

def solutions(number):
    s = [2, 5, 5, 4, 5, 6, 3, 7, 6, 6]
    for i in range(len(number)):
        # 작은 수 구하기
        if number[i] in s:
            answer_min = s.index(number[i])+1
        else:
            tmp = '1'
            num = number[i] - 2
            while num != 0:
                if num - 6 > 7:
                    tmp += '0'
                    num -= 6
                elif num - 6 in s:
                    tmp += '0'
                    tmp += str(s.index(num-6)+1)
                    num = 0
            answer_min= int(tmp)
        # 큰 수 구하기
        if number[i] <= 3:
            answer_max = s.index(number[i])+1
        else:
            tmp = ''
            if number[i] % 2 == 0:  # 짝수
                tmp += '1'*int(number[i] / 2)
            else:
                tmp = '7'
                tmp += '1'*int((number[i] - 3) / 2)
            answer_max = int(tmp)

        print(answer_min, end=' ')
        print(answer_max)

num = int(input())
number = [int(input()) for _ in range(num)]
solutions(number)

Clone 코드

✅ 큰 수를 구하는 방법은 위와 같지만 한 줄로 간단하게 표현할 수 있다.

✅ 작은 수를 구하는 방법은 조금 복잡하다.
1. 우선 성냥이 2개부터 10개일 때를 직접 구해보면 ans와 같이 나오는 것을 알 수 있다.
2. 10보다 작은 경우는 그대로 answer_min으로 출력한다.
3. 그렇지 않은 경우에는 자릿수를 제일 적게 사용하기 위해 가장 많은 7개의 성냥을 사용하는 8로 수를 채운다.
4. 7로 나누어 떨어지지 않는 경우를 예외로 처리한다.

👍 숫자가 7로 나누어 떨어진다면 가장 작은 수는 8로만 이루어진 수 이다.
7로 나눈 나머지가 각각,

• 1인 경우 = 앞의 8을 없애고 10을 붙여준다. (8을 만드는데 사용한 7개의 성냥 + 1 = 총 8개의 성냥으로 만들 수 있는 가장 작은 수는 ans[8]=10이다.)
• 2인 경우 = 성냥을 2개를 사용하는 숫자인 1을 제일 앞에 붙여준다.
• 3인 경우 = 앞의 두 숫자를 없애고 200을 붙여준다. (8을 하나만 제거하면 성냥이 7 + 3 = 10개 이므로 22가 되지만, 8을 두 개 제거하면 7 + 7 + 3 = 17 이므로 17 = 5 + 6 + 6이므로 200을 붙이는 것이 더 작다.)
• 4인 경우 = 앞의 8을 없애고 20을 붙여준다. ( 7 + 4 = 11이므로 11 = 5 + 6이므로 20을 붙인다.)
• 5인 경우 = 5를 가지고 만들 수 있는 가장 작은 숫자인 2를 앞에 추가한다.
• 6인 경우 = 6을 가지고 만들 수 있는 가장 작은 숫자는 0이지만 맨 앞에는 0이 올 수 없고 0이 맨 뒤로 가는 것보다 6개를 사용하여 만들 수 있는 6을 맨 앞에 붙이는 것이 더 작다.

def solutions(number):
    for i in range(len(number)):
        # 큰 수 구하기
        answer_max = '7' * (number[i] % 2) + '1' * (number[i] // 2 - (number[i] % 2))

        # 작은 수 구하기
        ans = [0, 0, 1, 7, 4, 2, 6, 8, 10, 18, 22]
        n = number[i]
        if n <= 10:
            answer_min = ans[n]
        else:
            answer_min = ''
            while n > 0:
                n -= 7
                if n >= 0:
                    answer_min += '8'
                else:
                    n += 7
                    break
            small = {2:'1', 5:'2', 6:'6'}
            if n in small:
                answer_min = small[n] + answer_min
            else:
                if n == 1:
                    answer_min = '10'+answer_min[1:]
                elif n == 3:
                    answer_min = '200'+answer_min[2:]
                elif n == 4:
                    answer_min = '20' + answer_min[1:]

        print(answer_min, end=' ')
        print(answer_max)

num = int(input())
number = [int(input()) for _ in range(num)]
solutions(number)

clone코드 출처