[파이썬] 백준 1234 : 크리스마스 트리 (골드2)

[파이썬] 백준 1234 : 크리스마스 트리 (골드2)

1234번: 크리스마스 트리

---

문제

---

풀이

방향성 생각

• 트리 높이가 10이고 각 높이에 같은 개수로 채우는 방식이 매우 제한적이다.
• 하드코딩으로 높이마다 처리해주기
• 처음에 개수를 많이 소모해야 가지치기로 불필요한 케이스를 많이 잘라낼 수 있다.
• 낮은 높이부터 채워서 꼭대기로 올라간다.
• 만약 쌓다가 공이 부족하면 탈출. 끝까지 올라갈 수 있으면 리스트에 저장한 가짓수를 모두 곱해서 answer에 더한다.

 

전체코드

n,red,green,blue = list(map(int,input().split()))

answer = 0
def dfs(stage,r,g,b,info):
    
    global answer 
    
    if r<0 or g<0 or b<0:
        return 
    
    if stage == 0:
        temp = 1
        for i in info:
            temp *= i
        answer += temp

    if stage == 10:
        dfs(stage-1,r-10,g,b,info+[1])
        dfs(stage-1,r,g-10,b,info+[1])
        dfs(stage-1,r,g,b-10,info+[1])
        dfs(stage-1,r-5,g-5,b,info+[252])
        dfs(stage-1,r-5,g,b-5,info+[252])
        dfs(stage-1,r,g-5,b-5,info+[252])
        
    elif stage == 9:
        dfs(stage-1,r-9,g,b,info+[1])
        dfs(stage-1,r,g-9,b,info+[1])
        dfs(stage-1,r,g,b-9,info+[1])
        dfs(stage-1,r-3,g-3,b-3,info+[1680])
    
    elif stage == 8:
        dfs(stage-1,r-8,g,b,info+[1])
        dfs(stage-1,r,g-8,b,info+[1])
        dfs(stage-1,r,g,b-8,info+[1])
        dfs(stage-1,r-4,g-4,b,info+[70])
        dfs(stage-1,r-4,g,b-4,info+[70])
        dfs(stage-1,r,g-4,b-4,info+[70])
        
    elif stage == 7:
        dfs(stage-1,r-7,g,b,info+[1])
        dfs(stage-1,r,g-7,b,info+[1])
        dfs(stage-1,r,g,b-7,info+[1])
        
    elif stage == 6:
        dfs(stage-1,r-6,g,b,info+[1])
        dfs(stage-1,r,g-6,b,info+[1])
        dfs(stage-1,r,g,b-6,info+[1])
        dfs(stage-1,r-3,g-3,b,info+[20])
        dfs(stage-1,r-3,g,b-3,info+[20])
        dfs(stage-1,r,g-3,b-3,info+[20])
        dfs(stage-1,r-2,g-2,b-2,info+[90])
        
    elif stage == 5:
        dfs(stage-1,r-5,g,b,info+[1])
        dfs(stage-1,r,g-5,b,info+[1])
        dfs(stage-1,r,g,b-5,info+[1])

    elif stage == 4:
        dfs(stage-1,r-4,g,b,info+[1])
        dfs(stage-1,r,g-4,b,info+[1])
        dfs(stage-1,r,g,b-4,info+[1])
        dfs(stage-1,r-2,g-2,b,info+[6])
        dfs(stage-1,r-2,g,b-2,info+[6])
        dfs(stage-1,r,g-2,b-2,info+[6])
        
    elif stage == 3:
        dfs(stage-1,r-3,g,b,info+[1])
        dfs(stage-1,r,g-3,b,info+[1])
        dfs(stage-1,r,g,b-3,info+[1])
        dfs(stage-1,r-1,g-1,b-1,info+[6])
        
    elif stage == 2:
        dfs(stage-1,r-2,g,b,info+[1])
        dfs(stage-1,r,g-2,b,info+[1])
        dfs(stage-1,r,g,b-2,info+[1])
        dfs(stage-1,r-1,g-1,b,info+[2])
        dfs(stage-1,r-1,g,b-1,info+[2])
        dfs(stage-1,r,g-1,b-1,info+[2])
        
    elif stage == 1:
        dfs(stage-1,r-1,g,b,info+[1])
        dfs(stage-1,r,g-1,b,info+[1])
        dfs(stage-1,r,g,b-1,info+[1])

dfs(n,red,green,blue,[])
print(answer)

 

코멘트

코드가 길어져서그렇지 복붙하면 금방이다..