[백준] 1029 그림 교환, python

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

 

 

 

 

 

 

파이썬 함수 결과값 자동 캐싱(cache, lru_cache), python

파이썬 함수 결과값 자동 캐싱(cache, lru_cache), python

 

파이썬 함수 cache를 사용하면 동일한 인자에 대해 캐싱된 함수 결과를 반환하므로 dp와 동일한 효과를 얻을 수 있다.

dfs를 통해 가격이 이전 가격 보다 높으면 set에 해당 아티스트를 추가하면서 탐색을 진행하였다.

 

 

소유했던 사람 목록에 없고, 산 가격보다 큰 가격이라면 dfs로 계속 탐색해준다.

dict, list, set과 같이 원소를 추가, 삭제할 수 있는 자료형은 해시값이 바뀌는 unhashable type이므로 함수 캐싱을 할때 사용할 수 없다.

따라서 소유했던 사람 목록을 list, set이 아닌 비트마스킹으로 관리해주었다.

 

 

 

 

 

i번째 요소의 포함여부를 알고싶다면, (1<<i) | s 가 s와 같다면 i번째 요소가 포함된것이고, 다르다면 포함되지않은 것이다.

set에서의 in 과 동일한 결과를 얻을 수 있다.

 

 

 

 

 

만약 set에 포함시키고 싶다면 s와 (1<<i) 를 or연산을 해주면 된다.

 

 

 

s에 포함된 원소의 개수를 알고싶다면, s를  이진수로 바꾼뒤 1의 개수를 세어주면된다.

 

 

 

from functools import*

n = int(input())
prices = [[int(x) for x in input()] for _ in range(n)]

answer = 0

# cur,p,s 가 같다면 캐싱된 값을 사용한다.
@cache
def dfs(cur, p, s):
    global answer
    answer = max(answer,s.bit_count())
    for i in range(n):
        # 소유했던 사람 목록에 없고, 가격이 더 크다면
        if (1<<i)|s != s and p<=prices[cur][i]:
            # 가격을 업데이트하고 소유했던 사람 목록에 추가한다.
            dfs(i, prices[cur][i],s | (1<<i))

dfs(0,0,1)

print(answer)