백준: Silver2⑤ - 1421, 1455, 1535, 1541

</br> 이제 좀만 더 하면 실버 1
</br>

1421: 나무꾼 이다솜

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

나무를 일정한 크기로 잘라서 최대 수익 얻기
</br>

    int maxL = 0;
    for(int i = 0; i < n; i++){
        int a;
        cin >> a;
        maxL = max(maxL, a);
        v.push_back(a);
    }

    for(int i = 0; i < n; i++){
        for(int j = 1; j < v[i]+1; j++){
            int cut = (v[i]-1)/j;
            long long money = 0;
            for(int k = 0; k < cut+1; k++){
                long long t = ( k + ( (v[i]-k*j)==j ) )*j*w - c*k;
                money = max(money, t);
            }
            dp[j] = max(dp[j], dp[j] + money);
        }
    }

    cout << *max_element(dp, dp + maxL+1) << endl;

dp로 풀 수 있다.
수익[길이 L] = max( 수익[길이 L], 수익[길이 L] + 현재 나무를 길이 L로 잘랐을 때 최대 수익 )
“현재 나무를 L로 잘랐을 때 최대 수익”은 for문으로 0번 잘랐을 때 ~ 최대한 다 잘랐을 때까지 하나 씩 다 확인해 구할 수 있다.

k번 잘랐을 때의 수익은 ( k + ( (v[i]-k*j)==j ) )*j*w - c*k인데, 잘라서 딱 떨어지면 k+1개의 나무 도막, 그게 아니면 k개의 나무 도막을 얻기 때문에 k + ( (v[i]-k*j)==j )과 같이 식을 썼다.
</br>

1455: 뒤집기 II

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

모든 동전을 앞면으로 뒤집는 최소 횟수 구하기

    int cnt = 0;
    for(int i = n-1; i > -1; i--){
        for(int j = m-1; j > -1; j--){
            if( mmap[i][j] ){
                cnt++;
                for(int ii = 0; ii <= i; ii++){
                    for(int jj = 0; jj <= j; jj++){
                        mmap[ii][jj] = 1 - mmap[ii][jj];
                    }
                }
            }
        }
    }
    cout << cnt << endl;

짱 간단… 이거 왜 실버2에 있지
전에 한 풀이 1080번(https://cyj893.github.io/algorithm/Algorithm8_2/)에서와 비슷하게, 0과 1이므로 여러 번 뒤집는 건 의미가 없고 한 번만 뒤집도록 한다.
전부 0이 되어야 하는데, 왼쪽 위 구석 ~ 현재 위치 까지를 모두 뒤집으므로 오른쪽 아래 구석부터 탐색하면 된다.
</br>

1535: 안녕

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

체력 안에서 최대의 기쁨 얻기

방법 1.

void func(int now){
    if( hp <= 0 ){
        return;
    }
    ans = max(ans, joy);
    for(int i = now+1; i < n; i++){
        joy += j[i];
        hp -= l[i];
        func(i);
        joy -= j[i];
        hp += l[i];
    }
}

백트래킹을 이용할 수 있겠더라. 사람 수가 20 이하이므로 20C0 ~ 20C20까지 모든 조합의 경우의 수 합은 2^20 = 1,048,576 이니까 2초 안에 충분히 돌아간다.
또 체력이 다 떨어지면 return 해 주기 때문에 웬만하면 그보다 더 적게 걸릴 거다.
</br>

방법 2.

    for(int i = 1; i < n+1; i++){
        for(int j = 1; j < 101; j++){
            if( j + L[i] < 101  ) dp[i][j] = max(dp[i-1][j], dp[i-1][j+L[i]] + J[i]);
            else dp[i][j] = dp[i-1][j];
        }
    }

    cout << *max_element(dp[n]+1, dp[n]+ 101) << endl;

근데 너무 dp 느낌이라서 그렇게도 풀었다.
dp[현재 사람][체력] = max(dp[현재 사람 넣기 전][체력], dp[현재 사람 넣기 전][체력+닳는체력] + 얻는 기쁨)

dp[n]에 99, 99, 70, 70, 70, 65, …, 0 이런 식으로 체력 i에서 획득 가능한 최대의 기쁨이 저장이 되어 있을 거라서, 마지막에 max_element를 안 하고 그냥 dp[n][1]을 출력해도 될 것 같다.
</br>

1541: 잃어버린 괄호

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

식에 괄호 넣어서 최솟값 만들기

int readNum(){
    int k = 0;
    for( ; i < s.size(); i++){
        if( s[i] == '+' || s[i] == '-' ) break;
        if( k == 0 ) k += s[i]-'0';
        else k = k*10 + s[i] - '0';
    }
    i--;
    return k;
}

// in main()
    s = '+' + s;
    int ans = 0;
    for( ; i < s.size(); i++){
        if( s[i] == '-' ) break;
        if( s[i] == '+' ) continue;
        ans += readNum();
    }
    for( ; i < s.size(); i++){
        if( s[i] == '-' || s[i] == '+' ) continue;
        ans -= readNum();
    }
    cout << ans << endl;

간단한 그리디다
좀 보니까 그냥 쭉 더해 가다가, -가 한 번이라도 나왔으면 다 빼주면 된다.

수 읽기 처리만 잘하면 된다.
</br>

---

드디어 실버 1이다~~ 일주일 안에 골5는 가겠다
</br>