[백준] 9375번 : 패션왕 신해빈

문제

 

---

풀이

 

문제 자체는 아주 쉬운 경우의 수 문제다.

X, Y 종류의 의상이 있다고 하자. 각 종류별 의상은 이러하다.

X - a, b

Y - c

 

X 종류의 의상에 대해 선택할 수 있는 경우는 {입지 않음, a, b}이고,

Y 종류의 의상에 대해 선택할 수 있는 경우는 {입지 않음, c}이다.

둘다 입지 않을 수는 없으니 3x2-1=5가 선택할 수 있는 총 경우의 수이다.

 

입력을 잘 처리해서 정리하는게 거의 다인 문제인거다.

---

소스코드

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
using namespace std;

struct outfit { //옷 정보 저장
    string name;
    string kind;
};

struct kindCnt { //종류별 옷의 개수 저장
    string kind;
    int cnt;
};
outfit* clothes = new outfit[30];
kindCnt* arr = new kindCnt[30];

int ootd(int n) {
    int cnt = 0;
    int mul = 1;
    bool isExist;

    for (int i = 0; i < n; i++) //개수 초기화
        arr[i].cnt = 0;
    for (int i = 0; i < n; i++) {
        isExist = false;
        for (int j = 0; j < cnt; j++) { //이미 있던 종류 옷이면 개수만 증가하고 break
            if(arr[j].kind.compare(clothes[i].kind)==0){
                arr[j].cnt++;
                isExist = true;
                break;
            }
        }
        if (!isExist) { //새로운 종류의 옷이면 새로 입력
            arr[cnt].kind = clothes[i].kind;
            arr[cnt++].cnt++;
        }
    }
    for (int i = 0; i < cnt; i++) //종류별로 하나의 옷 + 안 입는 선택지이므로 각 개수에 1씩 더해서 곱함
        mul *= (arr[i].cnt + 1);
    return mul - 1; //모든 종류의 옷을 안입는 경우 1개를 뺌
}

int main() {
    int T, n;

    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> n;
        for (int j = 0; j < n; j++)
            cin >> clothes[j].name >> clothes[j].kind;
        cout << ootd(n) << '\n';
    }
}

전체 소스코드다.

 

struct outfit { //옷 정보 저장
    string name;
    string kind;
};

struct kindCnt { //종류별 옷의 개수 저장
    string kind;
    int cnt;
};
outfit* clothes = new outfit[30];
kindCnt* arr = new kindCnt[30];

입력은 outfit 구조체에 저장된다.

outfit 구조체 배열을 살펴보며 각 종류별 의상의 수를 정리해 kindCnt 구조체에 저장할 것이다.

 

    for (int i = 0; i < n; i++) {
        isExist = false;
        for (int j = 0; j < cnt; j++) { //이미 있던 종류 옷이면 개수만 증가하고 break
            if(arr[j].kind.compare(clothes[i].kind)==0){
                arr[j].cnt++;
                isExist = true;
                break;
            }
        }
        if (!isExist) { //새로운 종류의 옷이면 새로 입력
            arr[cnt].kind = clothes[i].kind;
            arr[cnt++].cnt++;
        }
    }

ootd 함수에서 kindCnt 구조체의 arr 배열을 채우는 과정이다.

특정 옷 종류에 대해 이 종류의 옷이 이미 arr 배열에 존재한다면 옷의 수량만 늘려주고, arr 배열에 없는 옷이라면 새롭게 넣어준다.

 

    for (int i = 0; i < cnt; i++) //종류별로 하나의 옷 + 안 입는 선택지이므로 각 개수에 1씩 더해서 곱함
        mul *= (arr[i].cnt + 1);
    return mul - 1; //모든 종류의 옷을 안입는 경우 1개를 뺌

문제의 핵심적인 풀이라고 할 수 있는 부분은 이 3줄이 전부다.