[알고리즘] 옷 다르게 입기

문제

• 옷이 아래와 같고 다음 날은 오늘과 다른 코디를 해야한다.
  • 얼굴 : 노란 안경, 검정 안대
  • 상의 : 녹색 후드티
  • 하의 : 백바지
  • 겉옷 : 숏 잠바
• 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성하자

입력

[[y_hat, head], [b_glasses, eye], [g_turb, head]]

출력

5

풀이

• KEY : 종류 : 옷 개수 로 배열을 만들고, BACKTRACKING을 이용하여 계산

작성 코드

total = 0
def search_dic(dic, kd):
    if(len(dic) == 0):
        return -1
    else:
        for i in range(len(dic)):
            if(dic[i][0] ==  kd):
                return i
    return -1

def backtr(arr,mx,cur,sm):
    global total
    # print(arr)
    if(mx == cur ):
        total += sm
    elif(len(arr) == 0):
        pass
    else:
        for i in range(len(arr)):
            # print(arr)
            backtr(arr[i+1:],mx,cur+1,sm * arr[i])

def solution(clothes):
    cloth_dic = []
    for tup in clothes:
        idx = search_dic(cloth_dic, tup[1])
        if(-1 != idx ):
            cloth_dic[idx].append(tup[0])
        else :
            cloth_dic.append([tup[1], tup[0]])
    cloth_counts = []
    for cl in cloth_dic:
        cloth_counts.append(len(cl) -1)

    # print(cloth_counts)

    

    for i in range(len(cloth_counts)):
        backtr(cloth_counts,i+1,0,1)
    answer = total

    return answer

a = solution([["yellow_hat", "headgear"],["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]])

print(a)