[Programmers] Lv2. 의상 | C++

🔗문제 보러가기

프로그래머스

 

👨‍💻풀이 과정

 

처음에는 백트래킹을 통해 조합으로 풀었는데, 테스트 케이스 1번에서 시간 초과가 났습니다. 아무래도 최대 입력 범위인 30개의 옷이 들어있었던 것 같네요. 어떻게 풀 지 고민하다가, 어느 한 분의 수학적 아이디어를 보고 깨달았습니다.

 

• 코니는 하루에 최소 한 개의 의상은 입는다.
• 의상 종류 A의 옷 개수가 n개라면, 해당 종류의 옷들 중 하나를 골라 입거나, 안 입는 경우의 수는 다음과 같다.
  • \( {n \choose 1} + {n \choose 0} = n + 1 \)
• 따라서, 의상 종류 A, B, C의 각 옷 개수가 n, m, k개라면, 총 경우의 수는 다음과 같다.
  • \( ({n \choose 1} + {n \choose 0}) \times ({m \choose 1} + {m \choose 0}) \times ({k \choose 1} + {k \choose 0}) - 1\)
  • 문제 조건에서 코니는 무조건 한 개 이상 의상을 입는다고 했으니, 아무것도 입지 않은 경우를 하나 뺀 것 

 

이런 문제는 수학적 아이디어 센스가 좋지 않으면 못 풀려나요...

 

✏️소스 코드 및 결과

#include <string>
#include <vector>
#include <map>
using namespace std;
using ClothesCount = map<string, int>;

ClothesCount RegisterClothes(const vector<vector<string>>& clothes) {
    ClothesCount result;

    for (const auto clothesInfo : clothes) {
        string type = clothesInfo[1];
        result[type]++;
    }
    return result;
}

int FindCombination(const ClothesCount& clothes) {
    int count = 1;

    for (const auto clothesCount : clothes)
        count *= (clothesCount.second + 1);        // nC1 + nC0
    return count - 1;                              // 아무것도 안 입는 경우 제외
}


int solution(vector<vector<string>> clothes) {
    ClothesCount myClothes = RegisterClothes(clothes);
    int answer = FindCombination(myClothes);
    return answer;
}