BAEKJOON : 10973, 1182

No. 10973

1. Problem

2. My Solution

• next permutation 문제 원리를 반대로 적용
• 내림차순으로 시작해서 오름차순으로 끝난다고 생각
• 오른쪽을 기준으로 오름차순이 발견되는 index 요소를 선택
• Increasing Section 에서 해당 요소보다 작은 첫 번째 요소 swap
• Increasing Section 내림차순 정리

import sys

n = int(sys.stdin.readline())
seq = list(map(int,sys.stdin.readline().rstrip().split()))
flag = False

for i  in range(len(seq)-1, 0,-1):

    if seq[i-1] > seq[i]:                   # 오른쪽을 시작으로 오름차순이 되는 index 찾음
        start = i-1
        flag = True
    
        for j in range(len(seq)-1, start, -1):  # Increasing Section 에서 index 값보다 작은 첫 번째 요소와 swap
            if seq[j] < seq[start]:
                seq[j], seq[start] = seq[start], seq[j]
                break
        
        start = start+1
        end = len(seq)-1

        while(start < end):                     # Increasing Section 내림차순으로 정리
            seq[start], seq[end] = seq[end], seq[start]
            start += 1
            end -= 1

        break

if flag == True:
    print(*seq)
else:
    print(-1)

---

No. 1182

1. Problem

2. My Solution

• 수열에서 해당 index 의 요소가 포함되었는지 아닌지에 대한 정보를 담고있는 비트 마스크를 이용
• N 개의 bit 가 존재한다면 N 개의 요소에 대한 구성여부를 알 수 있음
• N 개의 bit 가 존재한다면 2^n-1 가지의 경우의 수가 존재하므로 for 문을 1 << n 까지 돌림

import sys

n,s = map(int,sys.stdin.readline().rstrip().split())
seq = list(map(int,sys.stdin.readline().rstrip().split()))
count = 0

for i in range(1,1 << n):
    sum = 0
    for j in range(n):
        if i & (1 << j):
            sum += seq[j]

    if sum == s:
        count += 1

print(count)   

3. Others' Solutions

• itertools 모듈의 combinations 함수 이용
• 부분집합을 구해야 하므로 길이 1부터 n 까지 조합을 모두 구함

from itertools import combinations

n, s = map(int, input().split())
cnt = 0
a = list(map(int, input().split()))

for i in range(1, n+1):
    b = list(combinations(a, i))
    for j in b:
        if sum(j) == s:
            cnt += 1
print(cnt)

4. Learned

• 파이썬에서 부분집합을 구하기 위해 itertools 모듈의 combinations 함수를 이용하여 길이 1부터 요소개수까지 조합을 모두 구하면됨
• 메모리의 제한이 존재한다면 비트마스크를 이용하겠지만 파이썬은 제한이 없음