프로그래머스 의상 c++ // 해쉬 , 경우의수 , 백트래킹

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

프로그래머스

1. 문제해결

ex) 모자 : 3개

상의 : 2개인경우

모자 : 안입음, 1개입, 2개입, 3개입

상의 : 안입, 1개입, 2개입

모든경우의수 == 4*3==12 에서

안입는경우 -1을 하면된다.

 

2. 코드

#include <bits/stdc++.h>

using namespace std;

int ret;
map<string, int> m1;
map<int, int> m2;


int solution(vector<vector<string>> clothes) {
    
    for(auto v : clothes){
        m1[v[1]]++;
    }
    
    ret=1;
    for(auto item : m1){
        ret*=item.second+1;
    }
    ret--;
    
    return ret;
}

 

3. 백트래킹 코드(1번 테스트케이스 시간초과)

모든 옷 한개씩 있는경우만 예외처리 해주면 뚫린다고 한다...

#include <bits/stdc++.h>

using namespace std;

int ret;
map<string, int> m1;
map<int, int> m2;

//현재 k번째 옷을 입을것임.
void go(int k, int cnt){
    //cout<<"go:("<<k<<","<<cnt<<") "<<m2[k]<<"\n";
    
    if(k>=m1.size()){
        //cout<<cnt<<"\n";
        if(cnt>0){
            ret++;
        }
        return;
    }
    
    //go(k+1,cnt+1);
    
    //i : k번째 옷 종류에서 입을 옷의 갯수
    for(int i=0;i<=m2[k];++i){
        go(k+1,cnt+i);
    }
    
}

int solution(vector<vector<string>> clothes) {
    
    for(auto v : clothes){
        m1[v[1]]++;
    }
    
    
    int i=0;
    for(auto item : m1){
        //cout<<item.first<<" "<<item.second<<"\n";
        m2[i]=item.second;
        ++i;
    }
    
    // for(auto item : m2){
    //    cout<<item.first<<" "<<item.second<<"\n";
    // }

    
    go(0,0);
    
    return ret;
}