백준: Silver2② - 1080, 1105, 1106

</br> 실버 2 문제들 이어서
</br>

1080: 행렬

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

01 행렬을 3x3 씩 반전 시켜서 목표 행렬 만들기

    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        for(int j = 0; j < m; j++){
            a[i][j] = s[j] - '0';
        }
    }
    for(int i = 0; i < n; i++){
        string s;
        cin >> s;
        for(int j = 0; j < m; j++){
            if( s[j] - '0' != a[i][j] ) b[i][j] = 1;
        }
    }

    if( chkSame() ){
        cout << 0 << endl;
        return 0;
    }
    if( n < 3 || m < 3 ){
        cout << -1 << endl;
        return 0;
    }

    int ans = 0;

    for(int i = 0; i < n-2; i++){
        for(int j = 0; j < m-2; j++){
            if( b[i][j] ){
                change(i, j);
                ans++;
            }
            if( chkSame() ){
                cout << ans << endl;
                return 0;
            }
        }
    }

    cout << -1 << endl;

문제 조건이 좀 명확했으면!!
n, m이 3보다 작을 때도 뒤집을 수 있게 만들었더니 틀렸대서 뭔가 했는데 3x3 크기가 안 되면 못 뒤집게 한단다.

아무튼, a를 입력 받고 b에 b와 a의 차이를 저장한다. 그냥 그대로 입력 받고 a와 b를 비교해도 되지만 이게 보기도 더 편하게 보이고 코드도 간단해 지는 것 같아서…

ex)
// 입력
0000
0010
0000

1001
1011
1001

// 저장
1001
1001
1001

어차피 0과 1이기 때문에, 같은 곳이 2번 바뀌는 건 의미가 없다(최솟값을 구하므로).
따라서 처음부터 보면서 다른 게 있으면 3x3으로 뒤집어 주고, 다른 게 있을 때마다 그렇게 해 준다.
그리고 만약 행렬이 모두 0, 즉 다른 게 전혀 없으면 ans를 출력하고 종료하고,
for문이 끝나 버리면 답이 없다는 뜻이므로 -1을 출력하고 종료한다.
</br>

1105: 팔

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

수의 범위를 받고, 그 사이에 8을 가장 적게 포함한다면 그 때 8의 개수 구하기

    string l, r;
    cin >> l >> r;
    int cnt = 0;

    if( l == r ){
        for(int i = 0; i < l.size(); i++){
            if( l[i] == '8'){
                cnt++;
            }
        }
        cout << cnt << endl;
        return 0;
    }
    if( r.size() == l.size() ){
        int i = 0;
        for( ; i < l.size(); i++){
            if( l[i] == r[i] ){
                if( r[i] == '8' ) cnt++;
            }
            else{
                break;
            }
        }
        cout << cnt << endl;
    }
    else{
        cout << 0 << endl;
    }

갑자기 엄청 쉬운 문제다. 뭐지
8만 포함 안 하면 되기 때문에, 어쩔 수 없이 포함해야 하는 8만 세 주면 된다.
정수로서 계산할 필요가 없고, 자리수를 세는 게 편하기 때문에 string으로 받는다.

만약 l과 r이 같으면 가능한 수는 l(= r)밖에 없기 때문에 그냥 거기의 8의 수를 세 주고 끝낸다.

만약 둘의 사이즈가 같다면, 앞의 같은 부분은 어쩔 수 없이 포함해야 하는 부분이므로 거기서 8의 개수를 센다.
나머지 다른 부분 부터는 8의 개수를 셀 필요가 없으므로 바로 끝낸다.
ex) 981, 989 -> 98은 무조건 포함이므로 8 한 개.

만약 r의 자리수가 l보다 크면 무조건 8이 없는 수를 만들 수 있으므로 0을 출력하고 끝낸다.
</br>

1106: 호텔

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

적어도 c명의 손님을 가장 싼 비용으로 구하기

    for(int i = 1; i < c+1; i++){
        dp[i] = 10000000;
    }

    dp[0] = 0;
    for(int i = 1; i < c+1; i++){
        for(int j = 0; j < price.size(); j++){
            dp[i] = min(dp[i], dp[max(0, i-customers[j])] + price[j]);
        }
    }

    cout << dp[c] << endl;

그리디로는 안 풀리니 dp로 보면 되겠다
대충 dp[손님 수] = min(dp[손님 수 - i] + 비용[i])라고 식을 잡을 수 있다.
dp는 점화식만 알면 구현이 너무 쉬워서 좋아

</br>

---

3문제 씩 끊으니까 포스트 분량이 적당한 거 같다
</br>