프로그래머스 - 위장

프로그래머스 - 위장

조합을 구해서 풀어버리면 시간초과가 난다. 핵심은 수식으로 정리하다보면 수식 1줄로 바로 풀 수 있다.

먼저 수식을 위해 각 조합별로 몇 가지의 의상이 있는지를 map을 이용해서 체크한다.

[["yellowhat", "headgear"], ["bluesunglasses", "eyewear"], ["green_turban", "headgear"]] 같은 경우에는 m["headgear"]는 2이고, m["eyewear"]는 1이다. (이를 간단하게 A, B라고 부르겠다)

문제에서 원하는 것은 A만 입는 경우, B만 입는 경우, AB 모두 입는 경우의 합이다.
3가지 종류로 확장해서 생각하면
A만 입는 경우, B만 입는 경우, C만 입는 경우
AB를 입는 경우, AC를 입는 경우, BC를 입는 경우
ABC를 입는 경우이다.
만약 A의 종류가 3개고, B의 종류가 4개라면 AB를 입는 경우는 12가지가 된다.

따라서 위 수식을 정리하면
A + B + C + AB + AC + BC + ABC가 된다.
곱셉법칙으로 묶기 위해서 1을 더해주고 1을 빼준다.
A + B + C + AB + AC + BC + ABC + 1 - 1
=> A + B + C + AB + AC + BC(1+A) + 1 - 1
=> B + C + AB + AC + (1+BC)(1+A) - 1
=> B(1+A) + C(1+A) + (1+BC)(1+A) - 1
=> (B+C)(1+A) + (1+BC)(1+A) - 1
=> (1+B+C+BC)(1+A) - 1
=> (1+B)(1+C)(1+A) - 1

따라서 각 옷 종류에 존재하는 옷의 수에 1씩 더해서 모두 곱한 뒤 1을 빼주면 바로 정답이 된다.

만약 이를 조합을 이용해서 각각의 경우를 모두 구하고, A B C AB AC , ... 등의 연산을 모두 진행해주면 1번 케이스에서 다음과 같이 시간초과가 날 것이다.

따라서 수식을 통해서 구해야 시간초과가 나지 않고, 모든 케이스에서 바로 구할 수 있다.

코드는 아래와 같다.

#include <vector>
#include <map>

using namespace std;

int solution(vector<vector<string>> clothes) {
    map<string, int> m;
    for(int i=0;i<clothes.size();i++) {
        if(m.find(clothes[i][1]) == m.end())
            m.insert( {clothes[i][1], 1 } );
        else
            m[clothes[i][1]]++;
    }
    int answer = 1;
    for(auto it : m) 
        answer *= (it.second + 1);
    return answer - 1;
}