백준: Silver⑬ - 1735, 1748, 1874, 1904, 1966

</br> 계속
</br>

1735: 분수 합

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

두 분수의 합 기약 분수로 나타내기

int gcd(int a, int b){
    if( b > a ) return gcd(b, a);
    if( a % b == 0 ) return b;
    return gcd(b, a%b);
}

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

    int c1,p1, c2,p2;
    cin >> c1 >> p1 >> c2 >> p2;

    int p = p1 * p2;
    int c = c1 * p2 + c2 * p1;

    int gcdnum = gcd(p, c);

    cout << c/gcdnum << ' ' << p/gcdnum << '\n';
}

기약분수 전 단순히 구한 분모와 분자를 각각 p, c에 저장하고, 두 수의 최대공약수를 구해서 나눠주면 끝
</br>

1748: 수 이어 쓰기 1

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

수를 이어 쓰면 자리수가 얼마일까

    long long cnt = 0;
    long long c = 10, d = 1;
    while( c <= n ){
        cnt += (c - c/10) * d;
        c *= 10;
        d++;
    }
    cnt += (n - c/10 + 1) * d;
    cout << cnt<<endl;

시간 제한이 0.15초인 문제
long long 하는 걸 까먹어서 한 번 틀렸다 어휴
자리수 단위로 끊으면서 몇 개 있는 지 더하면 된다
</br>

1874: 스택 수열

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

스택에 푸시 팝하면서 수열 만들 수 있는 지 확인하기

    int c = 1, i = 0;
    queue<char> q;
    while( i < n ){
        while( st.empty() || st.top() < nums[i] ){
            st.push(c);
            c++;
            q.push('+');
        }
        if( st.top() != nums[i] ){
            cout << "NO\n";
            return 0;
        }
        st.pop();
        q.push('-');
        i++;
    }
    while( q.size() ){
        cout << q.front() << '\n';
        q.pop();
    }

출력이 “NO”를 해야 하는데 “No”라고 해서 또 한 번 틀렸다
스택에 현재 수열의 수가 될 때까지 계속 푸시하고, 되면 팝한다
그런데 만약 스택의 탑이 수열을 넘어서거나 하면 실패
</br>

1904: 01타일

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

00타일과 1타일로 n자리수는 몇 개 만들 수 있을까

    dp[1] = 1;
    dp[2] = 2;
    for(int i = 3; i <= n; i++){
        dp[i] = dp[i-2]%15746 + dp[i-1]%15746;
    }

    cout << dp[n]%15746 << endl;

dp 문제다
dp[i] = dp[i-2] + dp[i-1]
피보나치랑 똑같이 생겼다
근데 바로 이걸 찾진 못하고ㅋㅋ

    dp[1][0] = 0;
    dp[1][1] = 1;
    dp[2][0] = 1;
    dp[2][1] = 1;
    for(int i = 3; i <= n; i++){
        dp[i][0] = dp[i-2][0] + dp[i-2][1];
        dp[i][1] = dp[i-1][0] + dp[i-1][1];
    }
    cout << dp[n][0] + dp[n][1] << endl;

처음 생각한 게 끝자리가 0인 거랑 1인 거랑 구분하자고 봤다
끝에 00을 붙일 경우, dp[i-2]의 애들을 들고 와야 하고
끝에 1을 붙일 경우, dp[i-1]의 애들을 들고 오면 된다
근데 생각하니까 그게 저 위의 식이었다ㅋㅋ
</br>

1966: 프린터 큐

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

00타일과 1타일로 n자리수는 몇 개 만들 수 있을까

    while( t-- ){
        int n, m;
        cin >> n >> m;
        deque< pair<int, int> > dq;
        priority_queue< int, vector<int>, less<int> > pq;
        for(int i = 0; i < n; i++){
            int a;
            cin >> a;
            dq.push_back(make_pair(a, i));
            pq.push(a);
        }
        int cnt = 0;
        while( 1 ){
            while( dq.front().first != pq.top() ){
                pair<int, int> p = dq.front();
                dq.pop_front();
                dq.push_back(p);
            }
            cnt++;
            int i = dq.front().second;
            if( i == m ){
                cout << cnt << '\n';
                break;
            }
            dq.pop_front();
            pq.pop();
        }
    }

중요도가 가장 큰 게 나올 때까지 패스해야 하므로, 덱큐로 계속 패스한다.
중요도는 우선순위 큐에 넣고 걔를 프린트하게 될 때마다 팝해주면 된다.
</br>

---

이제 슬슬 골드 5도 섞어서 풀어 봐야겠다~~
지금 정답률은 46.599%
</br>