[BOJ] - 16922

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

완전탐색

• 가능한 모든 경우의 수를 탐색하는 유형이다
• 재귀 형태로 문제를 푸는경우가 많으며, 각 단계마다 가능한 경우는 다음 재귀를 실행시키고 불가능한경우는 넘어간다
• 재귀의 끝 (탈출조건)에 도달했을 때, 1을 리턴해 경우의 수를 카운트한다
• 경우의 수를 세는 문제는 완전탐색 유형이다
• 완전탐색을 구현하는 방법은 다섯가지가 있다
  • Brute Force
  • 비트마스크
  • 순열
  • 백트래킹
  • BFS

노트

1) set 연산

a = set()

a.add(1) # 한개 원소 추가

a.update([1,2,3]) # 여러개 원소 추가

a.remove(2) # 값 제거

# b : set

a & b # 교집합
a - b # 차집합
a | b # 합집합
a ^ b # 합집합 - 교집합

# 부분집합 여부 확인
>>> a = {1, 2, 3, 4, 5}
>>> b = {1, 2, 3}
>>> a.issubset(b)
False
>>> b.issubset(a)
True

풀이

1) 가능한 경우들을 set 에 저장

2) set 을 가져와서 다음 단계를 진행

3) set 바꿔치기

문제점

코드

import sys

sys.stdin = open('16922.txt')

n = int(input())
ans_set = set()
add_set = [1, 5, 10, 50]

for i in range(n):
    if i == 0:
        ans_set.update(add_set)
    else:
        sub_set = set()
        for e in ans_set:
            sub_set.update([e + a for a in add_set])

        ans_set = sub_set

print(len(ans_set))