[코드트리 프로그래밍 연습] N개 중에 M개 고르기(Simple) / xor 결과 최대 만들기

https://www.codetree.ai/missions/2/problems/max-of-xor/submissions

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

n, m = map(int,input().split())

arr = list(map(int,input().split()))
selected = []

ans = -1

def f(d):
    global ans
    if d == m:
        s = 0
        for item in selected:
            s = s^item

        ans = max(ans,s)
        return
    
    for i in range(n):
        if arr[i] not in selected:
            selected.append(arr[i])
            f(d+1)
            selected.pop()
        
f(0)
print(ans)

위 방법으로 풀었었다. 다만, 위 방법의 문제가 있는데 1, 2, 3, 4, 5 가 있고, 처음에 3을 선택했다면 그 이후에는 4,5 만 선택해야 한다. 하지만 위 코드는 그러한 로직이 없기에 시간초과라는 결과를 얻게 되었다.

 

n, m = map(int,input().split())

arr = list(map(int,input().split()))
selected = []

ans = -1

def f(d,k):
    global ans
    if d == m:
        s = 0
        for item in selected:
            s = s^arr[item]

        ans = max(ans,s)
        return
    
    for i in range(k,n):
        if i not in selected:
            selected.append(i)
            f(d+1,i+1)
            selected.pop()
        
f(0,0)
print(ans)

단순히 함수 안에 변수를 하나 추가하여 자신보다 뒤에 있는 인덱스를 선택할 수 있도록 만들면 그만이다.