백준: Class 5 - 12852, 2166, 2467

</br> 클래스 5 시작이다
골드 5, 4, 3, 2, 1, 플레 5가 골고루 있다
지금 내가 골드 1이긴 해도 물렙이라 좀 오래 걸릴까
</br>

12852: 1로 만들기 2

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

    dp[n] = 0;
    for(int i = n; i > 1; i--){
        if( dp[i]+1 < dp[i-1] ){
            dp[i-1] = dp[i]+1;
            path[i-1] = i;
        }
        if( i % 2 == 0 && dp[i]+1 < dp[i/2] ){
            dp[i/2] = dp[i]+1;
            path[i/2] = i;
        }
        if( i % 3 == 0 && dp[i]+1 < dp[i/3] ){
            dp[i/3] = dp[i]+1;
            path[i/3] = i;
        }
    }

    cout << dp[1] << endl;

    stack<int> st;
    st.push(1);
    int now = 1;
    while( now != n ){
        st.push(path[now]);
        now = path[now];
    }
    while( st.size() ){
        cout << st.top() << ' ';
        st.pop();
    }
    cout << endl;

연관 문제: 1463: 1로 만들기, https://cyj893.github.io/algorithm/Algorithm10_12/
얘도 바로 전 포스트(11779: 최소비용 구하기 2, https://cyj893.github.io/algorithm/Algorithm16_13/)와 같이 경로를 알아야 한다.
dp에 값을 갱신해 줄 때마다 경로도 갱신해 주고, 되추적하면 된다.
</br>

2166: 다각형의 면적

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

    long long sarea = 0;
    sarea += x[0]*y[n-1] + x[n-1]*y[n-2];
    for(int i = 1; i < n-1; i++){
        sarea += x[i]*y[i-1];
        sarea -= x[i]*y[i+1];
    }
    sarea -= x[n-1]*y[0] + x[0]*y[1];

    if( sarea < 0 ) sarea = -sarea;
    if( sarea % 2 == 0 ) cout << sarea/2.0 << ".0\n";
    else cout << sarea/2.0 << endl;

오버 플로우 날까봐 long long도 다 했는데 틀렸다길래 소수점도 넣어줬는데도 틀렸다길래 뭐야??? 했는데

    cout << fixed;
    cout.precision(1);

c++의 cout은 너무 큰 수는 지수 표기법으로 출력한다고 함…
저렇게 cout << fixed;를 해 주면 소수점 고정시켜서 표현한다는 뜻으로, 막 e 붙고 그런 게 안 나온다
그리고 cout.precision(1);은 전에도 정리했지만 소수점 자리수 의미
그래 정답률은 좀 깎였지만 배웠으니 됐다

signed area는 알고리즘 시간에 배운 건데, 편하겠다 싶었던 건데 바로 생각 나서 써먹었다

| x1 x2 ... xn | > + x1*yn + x2*y1 + ... + xn*yn-1
| y1 y2 ... yn | > - x1*y2 - x2*y3 - ... - xn*y1
ans = sarea / 2;

방향 판단이나 뭐나 여러 모로 써 먹을 데가 많다
다각형을 이루는 순서대로 입력이 주어졌기 때문에 바로 사용할 수 있다.
</br>

2467: 용액

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

    long long ans = 2000000001;
    int a, b;
    int l = 0, r = n-1;
    while( l < r ){
        if( abs(ph[l] + ph[r]) < ans ){
            a = ph[l];
            b = ph[r];
            ans = abs(ph[l] + ph[r]);
        }
        if( ans == 0 ) break;
        if( ph[l] + ph[r] < 0 ) l++;
        else r--;
    }
    cout << a << ' ' << b << endl;

투 포인터로 풀었다
왼쪽 포인터와 오론쪽 포인터가 만날 때까지, 만약 둘을 더한 게 0보다 작으면 왼쪽을 오른쪽으로 옮기고, 아니면 반대로 오른쪽을 왼쪽으로 옮기며 계속 진행한다
</br>

---

정답률이 좀 낮아지고 있다 이럼 안 돼ㅜㅜ
</br>