[파이썬] 백준 #4312 3의 제곱

Seori·2022년 8월 10일

algorithm python silver 백준

백준

목록 보기

4/8

오늘 배운 부분집합을 복습하려고 고른 문제였는데, 시간 제한이 1초라서 배운 방법을 적용하기가 쉽지 않았다.😥

문제

다음과 같이 모든 음이 아닌 3의 제곱수가 들어있는 집합이 있다.

S = {1, 3, 9, 27, 81, ...}

S의 모든 부분집합을 구한 뒤, 이 집합을 가지고 있는 원소값의 합으로 오름차순 정렬했을 때, n번째 집합을 구하는 프로그램을 작성하시오.

입력

입력을 여러 개의 줄로 이루어져 있고, 각 줄에는 n이 주어진다. n은 19자리를 넘지 않는 양의 정수이다. 입력의 마지막 줄에는 0이 있다.
1
7
14
783
1125900981634049
0

출력

각 입력에 대해서, n번째 집합을 예제 출력 형식과 같게 출력한다.
{ }
{ 3, 9 }
{ 1, 9, 27 }
{ 3, 9, 27, 6561, 19683 }
{ 59049, 3486784401, 205891132094649, 717897987691852588770249 }

풀이 과정

input으로 n을 받아서, S의 n번째 부분집합을 출력하는 문제이다.
수 시간 고민하다가 답지 찬스를 쓰고 말았다. 답지를 보고 공부해서 다시 적용시켜 해결했다.

0. 모범 답안 분석

while True:
	n = int(input())
	if n == 0:
		break
	n -= 1			---------------------------------------(a)
	print("{", end=" ")
	i = 0
	while n != 0:
		if n % 2:
			print(3**i, end=", " if n // 2 else " ")	---(b)
		n //= 2
		i += 1
	print("}")
모범 답안에서 핵심은 (a)와 (b) 두 부분이었다.
이 문제와 답안을 이해하기 위해서는 먼저 부분집합과 2진법 숫자간의 관계를 알아야 한다.

S = [1, 3, 9]의 부분집합을 예시로 들어 설명해보겠다.
S의 부분집합은 [ ], [1], [3], [1, 3], [9], [1, 9], [3, 9], [1, 3, 9] 순으로 총 8개이다.
원소가 3개이므로 2^3개의 부분집합이 있는 것이다.

개수가 2^n인 점을 염두에 두고 다음 표를 살펴보자.

순서 집합 2진수 구상
0 [ ] 000 [X X X]
1 [1] 001 [X X 1]
2 [3] 010 [X 3 X]
3 [1, 3] 011 [X 3 1]
4 [9] 100 [9 X X]
5 [1, 9] 101 [9 X 1]
6 [3, 9] 110 [9 3 X]
7 [1, 3, 9] 111 [9 3 1]

2진수에서 1과 0을 각각 on/off 스위치로 생각해보자.
S = [1, 3, 9]인 집합에서 숫자처럼 [9, 3, 1]로 배열한 후 2진수에 대입하여 on/off를 실시하면 S의 n번째 부분집합을 구할 수 있다.

※ 문제 조건의 오름차순 정렬은 S가 3의 n승인 집합이므로 신경쓰지 않아도 된다.
앞의 원소를 아무리 더해도 뒤의 원소보다 작기 때문이다.

따라서 답안을 다시 살펴보면
(a)는 n이 1일 때 공집합이 되어야 하므로 위 표에서 '순서'값에 맞도록 n에 -1을 해준 것이고,
(b)는 n을 2진수화하여 표의 '구상'대로 출력하기 위한 코드이다.

순서	집합	2진수	구상
0	[ ]	000	[X X X]
1	[1]	001	[X X 1]
2	[3]	010	[X 3 X]
3	[1, 3]	011	[X 3 1]
4	[9]	100	[9 X X]
5	[1, 9]	101	[9 X 1]
6	[3, 9]	110	[9 3 X]
7	[1, 3, 9]	111	[9 3 1]

1. 입력 값 받기

while True:
    n = int(input())

    if n == 0:
        break
0이 입력될 때까지 반복하도록 while True로 시작한다.

2. S의 부분집합 구하기

    n += -1

    arr = []
    a = 0
    while True:
        arr.append(3 ** a)
        a += 1
        if n < 2 ** a:       # 입력값 n이 부분집합의 갯수 2**a보다 작을 때까지만 루프
            break

    P = []
    for i in range(len(arr)):
        if n & (1<<i):
            P.append(arr[i])
0에서 알아본 것처럼 n이 1일 때 '순서'가 0인 공집합을 출력하기 위해서, n값을 -1해준다.

그리고 문제 조건에서 소요 시간이 1초로 짧았기 때문에
집합 S 대신 입력값에 따라 3의 a승을 포함하는 집합 arr를 설정했다.
P 는 설정된 arr 집합의 n번째 부분집합이 된다.

3. 값 출력하기

    print('{ ', end = '')
    for i in P:
        if i == ' ':
            print('}')
            break
        elif i == P[-1]:
            print(f'{i}', end = ' ')
        else:
            print(f'{i}', end = ', ')
    print('}')
이제 남은건 P의 값을 형식에 맞게 출력해주는 것이다.
출력 형식이 대괄호와 띄어쓰기를 포함하고 있어서 상당히 애를 먹었다.

- 답안

# 입력값 받기(0이 나올 때까지 루프)
while True:
   n = int(input())
   
   if n == 0:
       break

# 문제 조건을 맞추기 위하여 n - 1
   n += -1

# 3의 a승 집합인 arr 설정. 입력값 n에 따라 arr의 길이가 달라진다.
   arr = []
   a = 0
   while True:
       arr.append(3 ** a)
       a += 1
       if n < 2 ** a:            # 입력값 n이 부분집합의 갯수 2**a보다 작을 때까지만 루프
           break

# arr의 n번째 부분집합 리스트 P 설정
   P = []
   for i in range(len(arr)):
       if n & (1<<i):
           P.append(arr[i])

# P의 값을 형식에 맞게 출력
   print('{ ', end = '')
   for i in P:
       if i == ' ':
           print('}')
           break
       elif i == P[-1]:
           print(f'{i}', end = ' ')
       else:
           print(f'{i}', end = ', ')
   print('}')