본문 바로가기
알고리즘

[백준 9375] 알고리즘 30일차 : 패션왕 신해빈

by SiO2whocode 2020. 7. 26.
반응형

https://www.acmicpc.net/problem/9375

 

9375번: 패션왕 신해빈

문제 해빈이는 패션에 매우 민감해서 한번 입었던 옷들의 조합을 절대 다시 입지 않는다. 예를 들어 오늘 해빈이가 안경, 코트, 상의, 신발을 입었다면, 다음날은 바지를 추가로 입거나 안경대신

www.acmicpc.net

수학 C++

접근방법

처음엔 조합으로 풀어보려고 했다. 옷을 한개 골랐을 때 ~ cnt(종류의 수)까지의 모든 의상의 조합을 구한 다음에

종류별 옷의 개수를 곱한 뒤 모든 값을 더하려고 했다.

하지만 코드가 너무 복잡해졌다. 포기

이 문제의 가장 큰 힌트는 그 종류의 옷을 안 입는 경우를 추가해서 경우의 수를 구하는 것이다.

그리고 마지막에 아무것도 안입는 경우(1개)를 빼면 된다.

아주 간단한 문제였다.. 진짜 확통 헛배웠나.

앞으로 수학문제가 풀기 싫어지는 문제였다.

 

근데 제출하니까 틀렸습니다 뜨는 거에요.

한 두번 제출했는데 마지막에 개행문자를 안썼다는걸 깨달음.

개행문자 때문에 틀린게 2번째 본인한테 화가 나기 시작

 

다 풀고 나서 보니까 맵 쓰라고 하던데 맵은 안씀 아주 원시적으로 품

 

아무튼 소스코드

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

int main(){
    int c,n;
    cin >> c;
    for(int i = 0 ; i < c ; i++){
        //테스트 케이스
        string name;
        int clothes[30] = {0,};
        string cate[30];
        string catego;
        int cnt = 0;
        bool isin = false;
        cin >> n;
        for(int j = 0 ; j < n ; j++){
            cin >> name >> catego;
            isin = false;
            for(int k = 0 ; k < cnt; k++){
                if(cate[k] == catego){
                    clothes[k]++;
                    isin = true;
                }
            }
            if(!isin){
                //종류 추가
                cate[cnt] = catego;
                clothes[cnt++]++;
            }
        }
        int result = 1;
        for(int s = 0 ; s < cnt ; s++){
            result *= (clothes[s]+1);
        }
        cout << result - 1 << "\n";
    }
    
    return 0;
}

 

반응형

댓글0