백준: Gold5② - 1038, 1068, 1089

</br> 계속 계속
</br>

1038: 감소하는 수

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

https://cyj893.github.io/algorithm/Algorithm9_3/
이 문제는 전에 푼 문제랑 똑같아서 패스한다
인덱스만 달라짐…
</br>

1068: 트리

https://www.acmcpc.net/problem/1068

오랜만에 보는 트리 문제다~~ 어떤 노드를 삭제했을 때 리프 노드는 몇 개일 지 세기

vector<int> v[51];
int del[51];
void func(int d){
    del[d] = 1;
    for(int i = 0; i < v[d].size(); i++){
        func(v[d][i]);
    }
}

// in main()
    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        if( a == -1 ) continue;
        v[a].push_back(i);
    }
    cin >> k;
    func(k);
    int cnt = 0;
    for(int i = 0; i < n; i++){
        if( del[i] == 0 ){
            cnt++;
            if( v[i].size() != 0 ){
                for(int t : v[i]){
                    if( !del[t] ){
                        cnt--;
                        break;
                    }
                }
            }
        }
    }
    cout << cnt << endl;

근데 트리를 구현할 필요는 없는 문제다
일단 입력 받을 때 벡터 배열에 자식들을 푸시해서 저장해 놓는다
그 다음 재귀 함수로 자식 노드들을 다 방문하며 del[]에 삭제 되었다고 표시한다.
이후 삭제되지 않은 노드들을 방문하며, 자식이 하나도 없는 지를 확인하고 카운트하면 된다

참고로 처음 입력이 무조건 -1이 아니다… 그래서 한 번 틀림ㅜ
</br>

1089: 스타트링크 타워

https://www.acmcpc.net/problem/1089

디지털 숫자의 전구가 꺼졌을 수도 있을 때 가능한 수들의 평균 구하기

#include <bits/stdc++.h>
#define R "..#"
#define L "#.."
#define LR "#.#"
#define A "###"

using namespace std;

vector<string> nums[10] = { {A, LR, LR, LR, A},
                           {R, R, R, R, R},
                           {A, R, A, L, A},
                           {A, R, A, R, A},
                           {LR, LR, A, R, R},
                           {A, L, A, R, A},
                           {A, L, A, LR, A},
                           {A, R, R, R, R},
                           {A, LR, A, LR, A},
                           {A, LR, A, R, A}    };
vector<string> v[10];
vector<int> cannum[10];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.precision(11);

    int n;
    cin >> n;

    for(int i = 0; i < 5; i++){
        string s;
        cin >> s;
        string t = s.substr(0, 3);
        v[0].push_back(t);
        for(int j = 1; j < n; j++){
            t = s.substr(3*j+j, 3);
            v[j].push_back(t);
        }
    }

    for(int ind = 0; ind < n; ind++){
        vector<string> t = v[ind];
        for(int i = 0; i < 10; i++){
            bool b = true;
            for(int j = 0; j < 5; j++){
                for(int k = 0; k < 3; k++){
                    if( t[j][k] == '#' && nums[i][j][k] == '.' ){
                        b = false;
                        break;
                    }
                }
                if( !b ) break;
            }
            if( b ) cannum[ind].push_back(i);
        }
    }
    double ans = 0;
    for(int i = 0; i < n; i++){
        int sz = cannum[i].size();
        if( cannum[i].size() == 0 ){
            cout << -1 << endl;
            return 0;
        }
        double sum = 0;
        int p = pow(10, n-i-1);
        for(int a : cannum[i]){
            sum += a;
        }
        sum = sum / sz;
        ans += sum*p;
    }
    cout << ans << endl;
}

와~~ 귀찮은 문제 아두이노 할 때 이런 거 비슷한 거 했었는데
0~9 까지 일단 string을 저장해 두고, 입력 받은 문자가 그 숫자를 만들 수 있는 지 확인한다
그다음 가능한 숫자들로 만들 수 있는 수들의 합의 평균 구하기
ex) 1111, 1113, 1114 ...와 같이 가능한 조합을 다 구하고 더하기는 귀찮을 것 같아서, 각 자리마다 평균을 내서 더해주는 식으로 구했다.
</br>

---

현재 143문제를 풀고 학교 랭킹 130등이다
지금 탑 100에 들려면 190문제는 풀어야 한다 갈 길이 머네
매일 10문제 풀면 일주일 안에 되긴 할 텐데 음
</br>