SWE(4837)_부분집합의 합

작성일 | In

SWE 4837 부분집합의 합

구하라

아이디어

좀처럼 생각이 나지 않아서 문제를 단계별로 쪼개보기로 했다.

  1. 우선 1부터 6까지의 전체 부분집합을 찍어보자. (12는 값이 너무 크니까 6으로 바꿔놓고 해보자)
A = [i for i in range(1, 7)]
n = len(A)
for i in range(1 << n):  # 1<<n: 부분집합의 개수
    for j in range(n):  # 원소의 수만큼 비트를 비교함 (원소의 포함 여부 판단이 가능)
        if i & (1 << j):  # i의 j번째 비트가 1이면 j번째 원소 출력
            print(A[j], end=",")
    print()
  1. 1에서 N개의 원소를 갖는 부분집합을 출력해보자

    2진수에서 1의 개수를 센다면 가능할 것이다. 다양한 방법이 있겠지만, 비트연산자 방법을 써보자.

def cntBit(v):
    cnt = 0
    while(v != 0):
        cnt += (v & 1)
        v = v >> 1
    return cnt

이걸 구했지만, 문제를 풀기엔 역부족이었다..

  1. 참고한 블로그 [참고한 블로그]https://tothefullest08.github.io/algorithm/2019/03/05/6_4837_%EB%B6%80%EB%B6%84%EC%A7%91%ED%95%A9%EC%9D%98%ED%95%A9/

결국 답안을 보고 공부하는 것으로 방향을 바꿨다.

TC = int(input())
num = [i for i in range(1, 13)]
Len = len(num)

# 부분집합 구하기
# 부분집합을 리스트에 다 담음
lst = []
for i in range(1 << Len):
    sub_lst = []
    for j in range(Len):
        if i & (1 << j):
            sub_lst.append(num[j])
    lst.append(sub_lst)

for tc in range(1, TC+1):
    N, K = map(int, input().split())

    # 길이 맞는 리스트 구하기
    len_lst = []
    for i in lst:
        if len(i) == N:
            len_lst.append(i)

    # 합 일치 유무 확인
    result = 0
    for i in len_lst:  # i가 리스트니까.
        if(sum(i) == K):
            result += 1

    print("#%s %d" % (tc, result))

알게된 사실

  1. 이진수 표현에서 1의 개수 세기

  2. 파이썬에서 함수 작성법

  3. 부분집합 중 개수가 같은 것들을 구하려면, 일단 나올 수 있는 경우의 부분집합을 모두 리스트화 하여, 리스트에 담는다 (2차원 리스트가 되겠지)
  4. 이후 길이에 맞는 리스트를 꺼내가면서 비교한다.
  5. 합 일치 유무를 파악할 때, sum() 함수를 사용할 수 있다.
    • sum(iterable)은 입력받은 리스트나 튜플의 모든 요소의 합을 돌려주는 함수이다.

참고자료 [2진수 표현에서 1의 개수 세기]https://namocom.tistory.com/377 [참고 블로그 - 답안]https://tothefullest08.github.io/algorithm/2019/03/05/6_4837_%EB%B6%80%EB%B6%84%EC%A7%91%ED%95%A9%EC%9D%98%ED%95%A9/

0%