[프로그래머스/C++] 의상

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

먼저 옷의 종류를 map을 이용해 분류를 했다는 가정하에 풀이를 소개하겠다.

(이름이 같은 옷은 없으므로, 특정 의상의 수만 파악하면 문제를 풀 수 있기 때문이다.)

 

약 3가지 방법을 소개하는데, 가장 효율이 좋은 방법은 마지막 방법이다.

그러므로 효율적인 풀이가 필요하다면 마지막 풀이를 보는 것을 추천한다.

 

1. 단순 재귀

 

처음 문제를 봤을 때, 풀이가 생각이 날듯 말듯 했다.

 

뭔가 경우의 수를 잘 빼면 해결 될 것 같았는데, 다른 방법이 빠르게 생각이 나지 않아서 먼저 재귀로 문제를 해결했다.

 

하지만, 재귀로 문제를 풀면서 최악의 경우에는 시간복잡도가 많이 커지겠다는 예상이 들었다.

 

먼저 재귀로 푼 방법을 소개하면, 

 

n개의 의상 중 i개의 의상을 입는 방법을 재귀적으로 계산하도록 코드를 구현한 것이다.

 

처음에 1이 표시된 부분은 하나의 의상만 입는 경우다.

이때, 첫번째 종류의 의상을 선택하면 개수가 3이므로 3을 answer에 더한다.

 

이후 2번째 종류의 옷을 입게 되면 두개의 의상을 입는 경우다.

그러므로 3*2를 곱한 값을 또 answer에 더한다.

 

마지막으로 3번째 종류의 옷을 입으면 세개의 의상을 입는 경우이므로 3*2*1을 곱한 경우의 수를 answer에 더해나가는 방식이다.

 

하지만 이렇게 코드를 구현하면 문제는 풀리지만 재귀가 많이 생겨 시간이 오래걸린다는 단점이 있다.

 

 

Code (단순 재귀)

 

 

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

int answer;

void DFS(int nowIdx, int nowCnt,  vector<int> &clothCnt)
{
    for (int i=nowIdx+1; i<clothCnt.size(); i++){
        answer+=nowCnt*clothCnt[i];
        if (i!=clothCnt.size()-1){
            DFS(i, nowCnt*clothCnt[i], clothCnt);
        }
    }
}

int solution(vector<vector<string>> clothes) {
    answer = 0;
    int idx=1;
    unordered_map<string, int> CM; //index로 한다.
    for (int i=0; i<clothes.size(); i++){
        if (CM[clothes[i][1]]==0){
            CM[clothes[i][1]]=idx;
            idx++;
        }
    }
    vector<int> clothCnt(idx,0);
    for (int i=0; i<clothes.size(); i++){
        clothCnt[CM[clothes[i][1]]]+=1;
    }
    DFS(0,1,clothCnt);
    return answer;
}

 

---

 

2. DP

 

다음 방법은 DP를 이용한 방법이다. 

 

재귀적으로 문제를 풀고나니 중복되는 부분의 계산을 DP로 해결할 수 있겠다는 생각이 들었다.

 

그래서 DP[i]를 다음과 같이 정의했다.

 

DP[i] = i번째 이후에 나오는 옷의 종류를 조합하는 모든 경우의 수

 

이를 이용하면 다음과 같이 점화식을 만들 수 있다.

 

$$DP[i] = cnt[i+1] * \sum\limits_{j=i+1}^N (DP[j])$$

 

이를 이용해 코드를 구현하면 빠르게 문제를 해결할 수 있다.

 

 

Code (단순 재귀)

 

 

#include <string>
#include <vector>
#include <unordered_map>
using namespace std;

int DFS(int nowIdx, vector<int> &clothCnt, vector<int> &DP)
{
    if (DP[nowIdx]!=-1)
    {
        return DP[nowIdx];
    }
    int saveCnt=clothCnt[nowIdx];
    for (int i=nowIdx+1; i<clothCnt.size(); i++){
        saveCnt+=clothCnt[nowIdx]*DFS(i,clothCnt,DP);
    }
    return DP[nowIdx]=saveCnt;
}

int solution(vector<vector<string>> clothes) {
    int answer = 0;
    int idx=1;
    unordered_map<string, int> CM; //index로 한다.
    for (int i=0; i<clothes.size(); i++){
        if (CM[clothes[i][1]]==0){
            CM[clothes[i][1]]=idx;
            idx++;
        }
    }
    vector<int> clothCnt(idx,0);
    vector<int> DP(idx,-1);
    for (int i=0; i<clothes.size(); i++){
        clothCnt[CM[clothes[i][1]]]+=1;
    }
    DP[idx-1]=clothCnt[idx-1];
    DFS(1,clothCnt,DP);    
    for (int i=1; i<DP.size(); i++){
        answer+=DP[i];
    }
    return answer;
}

 

 

3. 경우의 수 (단순 곱셈)

 

마지막 방법은 가장 단순한 방법이다.

 

이 문제의 풀이가 바로 떠오르지 않은 이유는 의상의 종류를 몇 개 선택하느냐에 따라 다르기 때문이다.

 

하지만 단순히 생각하면 특정 부위의 옷을 입거나, 선택해서 입는 경우로 나눌 수 있다.

 

즉, 특정 부위의 옷을 안입는 경우도 경우의 수에 포함하면 다음과 같이 모든 경우의 수를 계산할 수 있다.

 

[(A부위 옷의 수+1) * (B부위 옷의 수+1) * (C부위 옷의 수 +1) ... ] - 1(옷을 하나도 안입는 경우)

 

여기서 +1을 하는 이유는 특정 부위의 옷을 입지 않는 경우를 포함하기 때문이다.

 

그러면 옷을 하나도 안입는 경우인 1만 모든 경우의 수에서 빼주면 다른 옷을 입는 경우의 수를 구할 수 있다.

 

 

---

문제를 일단 풀고 다른 방법이 있나 봤더니 허탈했다

최근에 고민을 오래 하는 것 보다 먼저 구현하는게 더 잘 풀리는 경우가 있어서 먼저 풀고 봤는데, 이 문제는 풀이를 고민했으면 더 잘 풀렸을 문제였다;;

고민하는데 적당한 시간을 쓰는게 좋을 것 같다. 

 

프로그래머스