문제 42578. 의상

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/42578

프로그래머스

 

 

난이도 : Lv.2

 

문제 요약 설명

코니는 매일 다른 옷을 조합하여 입는것을 좋아합니다.

예를 들어 코니가 가진 옷이 아래와 같고, 오늘 코니가 동그란 안경, 긴 코트, 파란색 티셔츠를 입었다면 다음날은 청바지를 추가로 입거나 동그란 안경 대신 검정 선글라스를 착용하거나 해야합니다.

종류	이름
얼굴	동그란 안경, 검정 선글라스
상의	파란색 티셔츠
하의	청바지
겉옷	긴 코트

• 코니는 각 종류별로 최대 1가지 의상만 착용할 수 있습니다. 예를 들어 위 예시의 경우 동그란 안경과 검정 선글라스를 동시에 착용할 수는 없습니다.
• 착용한 의상의 일부가 겹치더라도, 다른 의상이 겹치지 않거나, 혹은 의상을 추가로 더 착용한 경우에는 서로 다른 방법으로 옷을 착용한 것으로 계산합니다.
• 코니는 하루에 최소 한 개의 의상은 입습니다.

코니가 가진 의상들이 담긴 2차원 배열 clothes가 주어질 때 서로 다른 옷의 조합의 수를 return 하도록 solution 함수를 작성해주세요.

입력

• 코니가 가진 의상들이 담긴 2차원 배열 clothes

입력 제한

• clothes의 각 행은 [의상의 이름, 의상의 종류]로 이루어져 있습니다.
• 코니가 가진 의상의 수는 1개 이상 30개 이하입니다.
• 같은 이름을 가진 의상은 존재하지 않습니다.
• clothes의 모든 원소는 문자열로 이루어져 있습니다.
• 모든 문자열의 길이는 1 이상 20 이하인 자연수이고 알파벳 소문자 또는 '_' 로만 이루어져 있습니다.

입력 예제

// input
[["yellow_hat", "headgear"], ["blue_sunglasses", "eyewear"], ["green_turban", "headgear"]]

// ans
5

 

풀이 방식

우선, clothes에 들어있는 모든 종류의 옷들을 카테고리별로 분류하고, 각 카테고리에 해당하는 옷들의 개수를 구해야한다. 그러기위해 어김없이 오늘도 map자료구조를 사용하여 <category이름, 해당 카테고리에 포함된 옷들의 개수>로 매핑한다. 

매핑을 완료했다면, 이제 다이나믹 프로그래밍(dp)방식으로 모든 경우의 수를 구한다. 타뷸레이션 방식으로 이용하였고, 점화식은 다음과 같다.

 

        case1[i] = case1[i-1] * v1[i] + case2[i-1] * v1[i];
        case2[i] = case2[i-1] + case1[i-1];

 

점화식이 이렇게 생긴 이유

case1은 해당 카테고리의 옷을 선택한 경우, case2는 해당 카테고리의 옷을 선택하지 않은 경우이다.

카테고리를 순차적으로 순회하면서 경우의 수를 구할 때(타뷸레이션) 현재 카테고리의 옷을 선택하는 모든 경우의 수는 이전의 모든 경우의 수(case1[i-1]+case2[i-2]) * 현재 카테고리의 옷의 개수가 된다. 

반면, 현재 카테고리의 옷을 선택하지 않는 경우는, 선택하지 않았기에 경우의 수가 1이므로 (case1[i-1]+case2[i-2]) * 1의 경우의 수가 된다.

따라서, 해당 점화식을 통해 모든 카테고리를 순회한 후, case1의 값과 case2의 값의 마지막 값을 더하면 해당 값이 answer가 된다.

정답 코드 

#include <string>
#include <vector>
#include <map>
#include <iostream>

using namespace std;

int solution(vector<vector<string>> clothes) {
    map<string, int> m1;
    int answer = 0;
    
    string category;
    for(int i = 0; i < clothes.size(); i++){
        category = clothes[i][1];
        m1[category]++;
    }
    int m1_size = m1.size();
    
    vector<int> v1;
    int idx = 1;
    for(auto it : m1){
       v1.push_back(it.second);
    }
    
    vector<int> case1(m1_size);     // 해당 카테고리의 옷을 선택한 경우.
    vector<int> case2(m1_size);     // 해당 카테고리의 옷을 선택하지 않은 경우.
        
    case1[0] = v1[0];
    case2[0] = 1;
    for(int i = 1; i < m1_size; i++){
        case1[i] = case1[i-1] * v1[i] + case2[i-1] * v1[i];
        case2[i] = case2[i-1] + case1[i-1];
    }
    
    // 하나도 착용하지 않는 경우는 포함하지 않으므로 1을 뺀다.
    answer = case1[m1_size-1] + case2[m1_size-1] - 1;
    return answer;
}