백준: Class 3 ④ - 9019, 9095, 9375

</br> 클래스 3 계속 계속
</br>

9019: DSLR

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

    while( t-- ){
        int b, a;
        cin >> b >> a;
        for(int i = 0; i < 10001; i++){
            visited[i] = 0;
        }

        string ans; int sz = INT_MAX;
        queue< pair<int, string> > q;
        q.push(make_pair(b, ""));
        visited[b] = 1;
        while( q.size() ){
            int n = q.front().first;
            string s = q.front().second;
            q.pop();
            if( n == a ){
                ans = s;
                break;
            }

            int D, S, L, R;
            D = (2*n) % 10000;
            if( n == 0 ) S = 9999;
            else S = n -1;
            L = (n%1000)*10 + n/1000;
            R = (n%10)*1000 + n/10;

            if( visited[D] == 0 ){
                q.push(make_pair(D, s+'D'));
                visited[D] = s.size();
            }
            if( visited[S] == 0 ){
                q.push(make_pair(S, s+'S'));
                visited[S] = 1;
            }
            if( visited[L] == 0 ){
                q.push(make_pair(L, s+'L'));
                visited[L] = 1;
            }
            if( visited[R] == 0 ){
                q.push(make_pair(R, s+'R'));
                visited[R] = 1;
            }
        }
        cout << ans << '\n';
    }

이거도 bfs로 가능
현재 수와 현재까지의 커맨드를 페어로 묶어서 큐에 넣는다.

</br>

9095: 1, 2, 3 더하기

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

    dp[0] = 0;
    dp[1] = 1;
    dp[2] = dp[1] + 1;
    dp[3] = dp[2] + dp[1] + 1;
    for(int i = 4; i <= 11; i++){
        dp[i] = dp[i-3] + dp[i-2] + dp[i-1];
    }
    while( t-- ){
        int n;
        cin >> n;
        cout << dp[n] << '\n';
    }

짱 쉬운데 출력문을 안 지워서 한 번 틀렸다…
dp[i] = (dp[i-3]에 3) + (dp[i-2]에 2) + (dp[i-1]에 1)이면 된다.
</br>

9375: 패션왕 신해빈

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

방법 1.

void ncr(int n, int r, int now, int d, int k){
    if( d == r ){
        cnt += k;
        return;
    }
    for(int i = now+1; i < n; i++){
        ncr(n, r, i, d+1, k*c[i]);
    }
}

// in main()
    while( t-- ){
        int n;
        cin >> n;
        int ind = 0;
        map<string, int> mp;
        for(int i = 0; i < n; i++){
            string s1, s2;
            cin >> s1 >> s2;
            if( mp.count(s2) ) c[mp[s2]]++;
            else{
                c[ind] = 1;
                mp[s2] = ind++;
            }
        }
        cnt = n;
        for(int i = 2; i <= ind; i++){
            ncr(ind, i, -1, 0, 1);
        }
        cout << cnt << '\n';
    }

조합으로 구현해 보았다
제출하니 시간초과 난다 헉!!
</br>

방법 2.

    while( t-- ){
        int n;
        cin >> n;
        int ind = 0;
        map<string, int> mp;
        for(int i = 0; i < n; i++){
            string s1, s2;
            cin >> s1 >> s2;
            if( mp.count(s2) ) c[mp[s2]]++;
            else{
                c[ind] = 1;
                mp[s2] = ind++;
            }
        }
        cnt = 1;
        for(int i = 0; i < ind; i++){
            cnt *= c[i]+1;
        }
        cout << cnt-1 << '\n';
    }

그래서… 경우의 수 계산을 다시 해 보자

c[0] + 1    // (0번 옷들 중 하나 고르기) + (0번 중 아예 안 고르기)
이렇게 보면
cnt = (c[0]+1) * (c[1]+1) * ... * (c[ind-1]+1) - 1
마지막 1 빼기는 아무 것도 안 입은 사태를 위해

수학 공부를 다시 좀 해야 할까
</br>

---

256문제 풀고 학교 랭킹 70등이다 문제 수 갭이 크네
50등 안에 가려면 320문제는 풀어야 하네ㄷㄷ
</br>