백준: Silver1② - 1074, 1148, 1149

</br> 계속 실버 1 풀이
</br>

1074: Z

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

0 1
2 3

배열을 z 모양으로 탐색하는데 몇 번째로 될 지 찾기

int func(int n, int r, int c){
    if( n == 1 )
        if( r == 0 )
            if( c == 0 ) return 0;
            else         return 1;
        else
            if( c == 0 ) return 2;
            else         return 3;
    int p4 = pow(4, n-1);
    int half = pow(2, n-1);
    if( r < half )
        if( c < half ) return func(n-1, r, c);
        else           return p4 + func(n-1, r, c-half);
    else
        if( c < half ) return 2 * p4 + func(n-1, r-half, c);
        else           return 3 * p4 + func(n-1, r-half, c-half);
}

사분면으로 나눠 순서대로 0사분면, 1사분면, …, 3사분면이라고 하면,
1사분면의 탐색 번호는 0사분면에 4^(n-1)을 더한 것과 같고, 나머지도 저것들의 정수배씩 차이난다.

따라서 재귀로 4분의 1씩만 탐색하면 된다.

f(n) = f(n/4) + 1
     = f(n/4*4) + 1 + 1
     ...
     = 시간복잡도 O(log4n)

</br>

1148: 단어 만들기

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

퍼즐 만들기

    for(string s : p){
        memset(nums, -1, 26 * sizeof(int));
        memset(pz, 0, 26 * sizeof(int));

        for(char c : s){
            pz[c-'A']++;
        }
        for(int i = 0; i < 26; i++){
            if( pz[i] ) nums[i]++;
        }

        for(string d : v){
            memset(tmp, 0, 26 * sizeof(int));
            bool b = false;
            for(char c : d){
                tmp[c-'A']++;
                if( tmp[c-'A'] > pz[c-'A'] ){
                    b = true;
                    break;
                }
            }
            if( b ) continue;
            for(int i = 0; i < 26; i++){
                if( tmp[i] ) nums[i]++;
            }
        }

        vector<char> q1, q2;

        int minNum = 2000000;
        int maxNum = -1;

        for(int i = 0; i < 26; i++){
            if( nums[i] != -1 ){
                minNum = min(minNum, nums[i]);
                maxNum = max(maxNum, nums[i]);
            }
        }

        for(int i = 0; i < 26; i++){
            if( nums[i] == minNum ) q1.push_back(i+'A');
            if( nums[i] == maxNum ) q2.push_back(i+'A');
        }

        for(char c: q1){
            cout << c;
        }
        cout << ' ' << minNum << ' ';
        for(char c: q2){
            cout << c;
        }
        cout << ' ' << maxNum << endl;
    }

그냥 구현 문제인 것 같다
귀찮긴 한데 그냥 만드니까 정답 나왔다
</br>

1149: RGB거리

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

색마다 비용이 다르고 인접한 집끼리 다른 색으로 칠할 때 거리를 전부 칠하는 최소 비용

    dp[0][0] = rgb[0][0];
    dp[0][1] = rgb[0][1];
    dp[0][2] = rgb[0][2];

    for(int i = 1; i < n; i++){
        dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + rgb[i][0];
        dp[i][1] = min(dp[i-1][2], dp[i-1][0]) + rgb[i][1];
        dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + rgb[i][2];
    }

    cout << min({dp[n-1][0], dp[n-1][1], dp[n-1][2]}) << endl;

간단한 dp 문제다
dp[현재 집][칠할 색] = min(dp[이전 집][칠할 색과 다른 색1], dp[이전 집][칠할 색과 다른 색2]) + (칠할 색의 비용)
색의 수가 많아지면 for문으로 이쁘게 적어야 겠나 싶었지만 3개 뿐이니까 그냥 했다
</br>

---

재밌네
</br>