백준 16922 파이썬 python : 로마 숫자 만들기 @@황소처럼 우직하게@@ 최적화 연습하기 좋지~

첫 번째 생각, 각 순서에 대해서 4개가 들어갈 수 있으니까 4 ^ 20 시간복잡도

두 번째 생각, 순서는 중요하지 않다고 했으니 그냥 각각 몇개들어가는지 고려하기

마지막, 마지막 문자는 앞에 3개로 정해진거에서 빼기 연산해서 정하기

그러면 20 ^ 3 시간복잡도

n = int(input().strip())

lst = []

for i in range(n + 1):
    for j in range(n + 1 - i):
        for k in range(n + 1 - i - j):
            t = n - i - j - k
            total = i * 1 + j * 5 + k * 10 + t * 50
            lst.append(total)

print(len(set(lst)))

파이썬의 장점을 살려서 set 을 썻다.

다른 방법은, 따로 배열을 만들어서 확인해줄 수 있따. bfs에서 visited 마냥 방문했는지 안했는지