[대회][BOJ][INU 코드페스티벌 2021] B번 23842 : 성냥개비

문제를 정리해보자.

 

성냥개비를 이용해서 '올바른 수식'을 만들어야 한다.

올바른 수식이 되는 조건은 아래와 같다.

 

1. @@+@@=@@ 형태를 만족해야 한다.

(모든 수는 항상 두 자릿수로 표현해야 한다. 예를 들면, 27은 27이다. 5는 05이다.)

 

2. N개의 성냥개비가 주어진다. 모두 사용해야 한다.

(+와 =에도 각각 2개의 성냥개비가 필요하다.)

 

 

풀이를 생각해보자.

 

모든 경우의 수를 따져보면 된다. (0+0=0부터 99+99=99까지 완전 탐색한다.)  

그리고 경우마다,

 

1. 수식이 성립하는가?

2. 수식이 N개의 성냥개비를 사용하는가?

 

를 따진다.

1, 2를 모두 만족하면 올바른 수식이다.

 

 

구현해보자.

 

숫자마다 사용되는 성냥개비 개수는 아래와 같다.

 

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

 

0은 6개

1은 2개

2는 5개

3은 5개

4는 4개

5는 5개

6은 5개

7은 3개

8은 7개

9는 6개

 

 

def sol(num):
    for num1 in range(100):
        for num2 in range(100):
            for num3 in range(100):
                if num1 + num2 == num3:  # 수식이 성립하는가?

                    # 수식이 N개의 성냥개비를 사용하는가?
                    i = 0
                    tmp = 0
                    result = ''
                    for n in [num1, num2, num3]:

                        str_n = str(n)

                        if len(str_n) == 1:
                            tmp += num_count[0] + num_count[n]
                            result += '0' + str_n

                        else:
                            tmp += num_count[int(str_n[0])] + num_count[int(str_n[1])]
                            result += str_n

                        if i == 0:
                            result += '+'

                        elif i == 1:
                            result += '='

                        i += 1

                    if tmp == num:
                        return result

    return "impossible"


n_i = int(input()) - 4  # +, = 사용하고 남은 성냥개비 개수
num_count = [6, 2, 5, 5, 4, 5, 6, 3, 7, 6]

print(sol(n_i))

 

 

시간복잡도는 O(100^3)이다.

 

 

느낀 점

 

대회에서 이 문제를 풀 때, 조합 외장함수를 이용했다.

9개의 숫자 중 2개를 선택하고 (중복해서 같은 숫자 선택 가능) 한 그룹으로 묶었다.

그리고 만들어진 그룹들에서 3개를 선택했다. (중복해서 같은 그룹 선택 가능)

 

하지만 이렇게 하니까 시간초과가 났다. 불필요한 연산이 많았기 때문이다.

'중복해서 x를 선택 가능' 이 부분이 시간 초과의 원인이다.

중복해서 선택하기 위해서 같은 숫자, 그룹들을 리스트에 넣어 놓았고, 중복되는 경우의 수를 만들었다. 

 

3중 for문을 이용해서 1부터 99까지 돌리면 되는데, 왜 이 생각을 못 했을까.. 반성하게 된다.