사용자 도구

사이트 도구


ps:problems:boj:7490

0 만들기

ps
링크acmicpc.net/…
출처BOJ
문제 번호7490
문제명0 만들기
레벨골드 5
분류

브루트 포스

시간복잡도O(t*n*3^n)
인풋사이즈t<=9, n<=9
사용한 언어Python
제출기록30860KB / 164ms
최고기록60ms
해결날짜2022/02/04

풀이

  • 그냥 모든 조합을 다 시도해서 0이 되는 것들을 찾으면 된다.
  • 백트래킹으로 어느정도의 가지치기를 해줄수도 있겠지만, 그런것 없이 3^(n-1)가지의 모든 경우를 다 시도해봐도 n이 작아서 돌리는데에 별 무리가 없다.
  • 만들어진 각각의 식에 대해서, 결과값을 계산하는 것은 공백 연산자의 존재때문에 조금 구현이 귀찮다. 보통때에는 금기시하고 있지만, 이번에는 그냥 eval()을 사용해서 계산해버렸다.
  • O(3^n)가지의 식에 대해서 계산시간이 O(n)이 걸리므로 총 시간 복잡도는 O(n*3^n)

코드

"""Solution code for "BOJ 7490. 0 만들기".

- Problem link: https://www.acmicpc.net/problem/7490
- Solution link: http://www.teferi.net/ps/problems/boj/7490

Tags: [Brute Force]
"""

import itertools

OPER = (' ', '+', '-')


def main():
    t = int(input())
    for _ in range(t):
        N = int(input())

        s = [None] * (N + N - 1)
        s[::2] = [str(x) for x in range(1, N + 1)]
        for t in itertools.product(OPER, repeat=(N - 1)):
            s[1::2] = t
            expression = ''.join(s)
            # pylint: disable=eval-used
            if eval(expression.replace(' ', '')) == 0:
                print(expression)
        print()


if __name__ == '__main__':
    main()

토론

댓글을 입력하세요:
O I L X W
 
ps/problems/boj/7490.txt · 마지막으로 수정됨: 2022/02/06 16:01 저자 teferi