[BOJ][Python] 백준 3687 번: 성냥개비

1일 1PS 82일차!

📚 문제

---

[골드 2] - 성냥개비

💡 풀이 과정

---

2개 = 1
3개 = 7
4개 = 4
5개 = 2, 3, 5
6개 = 6, 9, 0
7개 = 8

• 성냥개비의 개수로 만들어낼 수 있는 숫자다.

1. 최대

• 자리수가 가장 많은 것이 좋기에 1 혹은 7만 사용된다.
• 7개의 성냥개비는 3개, 2개, 2개로 나누어 711
• 6개의 성냥개비는 2개 * 3 으로 111
• 위와 같이 최대값이 나누어진다.

1. 최소

• 각 자리 수 중에서 가장 작은 숫자를 사용한다.
• [1, 7, 4, 2, 0 ( 6), 8]

• 여기서 0 에 주의한다. 1자리 수일 경우에 6을 사용해야한다.

• 2 ~ 7 까지는 한 자리 수를 선택한다.
• 8 의 경우는 (2, 6) 으로 나눠 10 이 가장 최소이다.
• 모든 경우에서 가장 첫 번째 자리수에는 1이 들어가는 것이 가장 좋다.
• 다만 14의 경우 88 로 두 자리수가 가장 최소이다.
• 즉 7의 배수를 기준으로 자리 수가 정해진다.
• 7의 배수 내에서는 1(2개), 0(6개), 2(5개), 4(4개), 7(3개), 8(7개) 를 우선순위로 배치한다.
• [2, 6, 5, 4, 3, 7] 을 우선순위로 해당 개수를 사용할 수 있을 지 확인한다.
• n 이 40 일때 7 7 7 7 7 5 개로 “288888” 혹은 7 7 7 7 6 6 개를 사용해 “80088” 을 만들어낼 수도 있다.
• 결국 가장 앞자리만 특수하게 결정하고 뒷부분은 최소에 따라 결정하면 된다.
• 반례 : 10 answer 22, result 40
  • 가장 첫번째에서 1, 2, 4 를 한 번 확인해 flag 를 유지하면 된다.

📌포인트

---

• mapping
  • 우선 순위 설정 후 dict 를 통한 매핑이 가능하다.
• 0 처리
  • 0 을 처리하는 방법이 중요하다.
  • flag 를 통해 0 을 6으로 바꿔야하는 지 여부를 확인할 수 있다.
• first_nonzero = next((index for index, x in enumerate(min_list) if x != 0), None)
  • next(iterator[, default])
  • 이터레이터에서 다음 값을 반환하는 파이썬 내장 함수이다. 이 함수는 이터레이터에서 다음 값을 가져와 반환하고, 이터레이터의 끝에 도달하면 기본값을 반환할 수 있다.

💻 코드

---

import sys

T = int(sys.stdin.readline())

# 성냥개비 개수
priority = [2, 6, 5, 4, 3, 7]
priorityToNumber = {
    2: [1],
    6: [0],
    5: [2],
    4: [4],
    3: [7],
    7: [8]
}

first_try = [2, 5, 4]
firstToNumber = {
    2: 1, 5: 2, 4: 4
}

for _ in range(T):
    N = int(sys.stdin.readline())

    n = N
    # 최솟값의 자릿수
    min_digit = (n + 6) // 7
    min_list = []
    p_idx = 0

    # 0 처리를 위한 flag
    flag = False
    for f in first_try:
        if (min_digit - 1) * 2 <= n - f <= (min_digit - 1) * 7:
            min_digit -= 1
            min_list.append(firstToNumber[f])
            n -= f
            flag = True
            break

    # 우선순위를 순서대로 성냥 개비 사용 횟수를 나눈다.
    while min_digit:
        if (min_digit - 1) * 2 <= n - priority[p_idx] <= (min_digit - 1) * 7:
            min_digit -= 1
            min_list.append(priorityToNumber[priority[p_idx]][0])
            n -= priority[p_idx]
        else:
            p_idx += 1

    # 15 의 경우 [2, 6, 7] 이 생성된다. list 도 우선순위대로 정렬되어있다.
    # 6도 모두 0 으로 바꿔 정렬 후 연산.
    # 이를 min_list.append 시에 dict 을 참고해서 바로 바뀌도록 변경했다.
    # [1, 0, 8] 이 생성된다.

    # 이를 순서대로 정렬하고 0이 아닌 가장 첫번째 숫자가 6보다 크다면 첫번째 0을 6으로 바꾼다.
    # 만약 0이 아닌 첫 번째 숫자가 6보다 작다면 해당 숫자와 첫번째 0의 위치를 바꾼다.
    min_list.sort(key=lambda x: x)
    # if 0 in min_list:
    #     # 0 이 아닌 첫 번째 수.. 끝까지 동작할 경우 None 을 반환한다.
    #     first_nonzero = next((index for index, x in enumerate(min_list) if x != 0), None)
    #
    #     if first_nonzero:
    #         if min_list[first_nonzero] < 6:
    #             min_list[0], min_list[first_nonzero] = min_list[first_nonzero], min_list[0]
    #         else:
    #             min_list[0] = 6
    #     else:
    #         min_list[0] = 6

    #  6보다 작은 수가 확실히 존재한다.
    if flag:
        if 0 in min_list:
            first_nonzero = next((index for index, x in enumerate(min_list) if x != 0), None)

            if first_nonzero:
                min_list[0], min_list[first_nonzero] = min_list[first_nonzero], min_list[0]

    # 6보다 작은 수가 없다!
    else:
        if 0 in min_list:
            min_list[0] = 6

    min_num = "".join(map(str, min_list))
    # n 이 홀수인 경우 7을 추가, n - 3 에서 // 2 만큼 1 추가
    # 짝수인 경우 n // 2 만큼 1 추가
    n = N
    max_num = "7" * (n % 2) + "1" * ((n - (3 * (n % 2))) // 2)

    print(min_num + " " + max_num)