[중급 알고리즘] Brute Force 연습 1

💚 17070 파이프 옮기기 1

파이프가 2개의 칸에 걸쳐있어도 알고리즘 풀이에는 파이프의 오른쪽 칸으로만 파악하면 된다. 방향이 제한되어있기 때문이다.

 

방법의 수가 $10^6$ 이하이므로 Brute Force 탐색이 가능하다.

조금 비효율적으로 반복되는 코드를 작성했더니 역시나 실수가 자주 발생해서 디버깅에 시간이 더 오래 걸렸다.

#include <iostream>
#include <vector>
// 10^6 이하이기 때문에 브루트 포스 가능
using namespace std;
// 오른쪽, 아래, 오른쪽 아래
int dr[] = {0, 1, 1};
int dc[] = {1, 0, 1};
int n;

bool inside(int r, int c) {
    return r >= 0 && r < n && c >= 0 && c < n;
}

int go(vector<vector<int>> &house, int r, int c, int dir) {
    if(r == n - 1 && c == n - 1) {
        return 1;
    }
    
    int cnt = 0;
    
    if(dir == 0) {
        int nr = r + dr[0];
        int nc = c + dc[0];
        
        if(inside(nr, nc) && house[nr][nc] != 1) {
            cnt += go(house, nr, nc, 0);
        }
        
        int nr1 = r + dr[1];
        int nc1 = c + dc[1];
        
        int nr2 = r + dr[2];
        int nc2 = c + dc[2];
        
        if(inside(nr,nc) && inside(nr1, nc1) && inside(nr2, nc2) &&
           house[nr][nc] != 1 && house[nr1][nc1] != 1 && house[nr2][nc2] != 1) {
            cnt += go(house, nr2, nc2, 2);
        }
    }
    else if(dir == 1) {
        int nr = r + dr[0];
        int nc = c + dc[0];
        
        int nr1 = r + dr[1];
        int nc1 = c + dc[1];
        
        if(inside(nr1, nc1) && house[nr1][nc1] != 1) {
            cnt += go(house, nr1, nc1, 1);
        }
        
        int nr2 = r + dr[2];
        int nc2 = c + dc[2];
        
        if(inside(nr,nc) && inside(nr1, nc1) && inside(nr2, nc2) &&
           house[nr][nc] != 1 &&
           house[nr1][nc1] != 1 &&
           house[nr2][nc2] != 1) {
            cnt += go(house, nr2, nc2, 2);
        }
    }
    else if(dir == 2) {
        int nr = r + dr[0];
        int nc = c + dc[0];
        
        if(inside(nr, nc) && house[nr][nc] != 1) {
            cnt += go(house, nr, nc, 0);
        }
        
        int nr1 = r + dr[1];
        int nc1 = c + dc[1];
        
        if(inside(nr1, nc1) && house[nr1][nc1] != 1) {
            cnt += go(house, nr1, nc1, 1);
        }
        
        int nr2 = r + dr[2];
        int nc2 = c + dc[2];
        
        if(inside(nr,nc) && inside(nr1, nc1) && inside(nr2, nc2) &&
           house[nr][nc] != 1 &&
           house[nr1][nc1] != 1 &&
           house[nr2][nc2] != 1) {
            cnt += go(house, nr2, nc2, 2);
        }
    }
    
    return cnt;
    
}
int main() {
    cin >> n;
    
    vector<vector<int>> house(n, vector<int> (n));
    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++) {
            cin >> house[i][j];
        }
    }
    
    cout << go(house, 0, 1, 0) << '\n';
}

💚17069 파이프 옮기기 2

방법의 수 제한이 풀리기 때문에 Brute Force로 풀 수 없게 된다.

여기선 메모이제이션을 위해 DP로 풀어야 한다.

(x, y) → ... →(N,N)로 가는 방법의 수를 d[x][y]에 저장하면 된다.

이문제는 파이프의 방향도 중요하기 때문에 

$d[x][y][dir]$ = 파이프의 한 쪽 끝이 (x,y)에 있고, 방향이 dir일 때 (N, N)에 가는 방법의 수

 

여기서 포인터를 사용해 해당 값을 초기화하고, 값을 메모이제이션하고 사용한다.

#include <iostream>
#include <vector>
// 10^6 이하이기 때문에 브루트 포스 가능
using namespace std;
// 오른쪽, 아래, 오른쪽 아래
int dr[] = {0, 1, 1};
int dc[] = {1, 0, 1};
int n;

bool inside(int r, int c) {
    return r >= 0 && r < n && c >= 0 && c < n;
}

long long go(vector<vector<int>> &house, vector<vector<vector<long long>>> &visited, int r, int c, int dir) {
    if(r == n - 1 && c == n - 1) {
        return 1;
    }
    // 포인터 활용
    long long &cnt = visited[r][c][dir];
    if(cnt != -1) return cnt;
    
    // 초기화
    cnt = 0;
    
    if(dir == 0) {
        int nr = r + dr[0];
        int nc = c + dc[0];
        
        if(inside(nr, nc) && house[nr][nc] != 1) {
            cnt += go(house, visited, nr, nc, 0);
        }
        
        int nr1 = r + dr[1];
        int nc1 = c + dc[1];
        
        int nr2 = r + dr[2];
        int nc2 = c + dc[2];
        
        if(inside(nr,nc) && inside(nr1, nc1) && inside(nr2, nc2) &&
           house[nr][nc] != 1 && house[nr1][nc1] != 1 && house[nr2][nc2] != 1) {
            cnt += go(house, visited, nr2, nc2, 2);
        }
    }
    else if(dir == 1) {
        int nr = r + dr[0];
        int nc = c + dc[0];
        
        int nr1 = r + dr[1];
        int nc1 = c + dc[1];
        
        if(inside(nr1, nc1) && house[nr1][nc1] != 1) {
            cnt += go(house, visited, nr1, nc1, 1);
        }
        
        int nr2 = r + dr[2];
        int nc2 = c + dc[2];
        
        if(inside(nr,nc) && inside(nr1, nc1) && inside(nr2, nc2) &&
           house[nr][nc] != 1 &&
           house[nr1][nc1] != 1 &&
           house[nr2][nc2] != 1) {
            cnt += go(house, visited, nr2, nc2, 2);
        }
    }
    else if(dir == 2) {
        int nr = r + dr[0];
        int nc = c + dc[0];
        
        if(inside(nr, nc) && house[nr][nc] != 1) {
            cnt += go(house, visited, nr, nc, 0);
        }
        
        int nr1 = r + dr[1];
        int nc1 = c + dc[1];
        
        if(inside(nr1, nc1) && house[nr1][nc1] != 1) {
            cnt += go(house, visited, nr1, nc1, 1);
        }
        
        int nr2 = r + dr[2];
        int nc2 = c + dc[2];
        
        if(inside(nr,nc) && inside(nr1, nc1) && inside(nr2, nc2) &&
           house[nr][nc] != 1 &&
           house[nr1][nc1] != 1 &&
           house[nr2][nc2] != 1) {
            cnt += go(house, visited, nr2, nc2, 2);
        }
    }
    
    return cnt;
    
}
int main() {
    cin >> n;
    
    vector<vector<int>> house(n, vector<int> (n));
    vector<vector<vector<long long>>> visited(n, vector<vector<long long>>(n, vector<long long> (3, -1)));
    for(int i = 0;i < n;i++){
        for(int j = 0;j < n;j++) {
            cin >> house[i][j];
        }
    }
    
    cout << go(house, visited, 0, 1, 0) << '\n';
}

💚16638 괄호 추가하기 2✨

- 길이가 N인 수식

- 연산자 우선순위가 존재한다. 연산자 우선순위는 곱하기가 더하기, 빼기보다 높다.

- 식에 괄호를 추가하면, 괄호 안에 들어있는 식은 먼저 계산되어야 한다.

- 괄호 안에는 연산자가 하나만 있어야 하고, 중첩된 괄호는 사용할 수 ㅇ벗다.

- 괄호를 적절히 추가해서 만들 수 있는 결과의 최댓값을 구하는 문제

 

괄호를 추가해서 먼저 계산한 다음

X(곱하기)를 계산한 다음

+와 -를 계산하면 된다.

#include <iostream>
#include <vector>
#include <string>
using namespace std;

struct Term {
    int num;
    int op;
};

int main() {
    int n;
    cin >> n;
    
    string s;
    cin >> s;
    vector<Term> a(n);
    
    for(int i = 0;i < n;i++) {
        // 수
        if(i % 2 == 0) {
            a[i] = {s[i] - '0', 0};
        }
        
        // 부호
        else {
            int op = 1;
            if(s[i] == '-') {
                op = 2;
            }
            else if(s[i] == '*') {
                op = 3;
            }
            
            a[i] = {0, op};
        }
    }
    
    int m = (n - 1) / 2;
    int ans =  -2147483648;
    
    for(int i = 0;i < (1 << m);i++) {
        bool ok = true;
        for(int j = 0;j < m - 1;j++) {
            // 연속 괄호 불가능
            if((i & (1 << j)) > 0 && (i & 1 << (j + 1)) > 0) {
                ok = false;
            }
        }
        
        if(!ok) continue;
        vector<Term> b(a);
        for(int j = 0;j < m;j++) {
            if((i & (1 << j)) > 0) {
                int k = 2 * j + 1;
                if(b[k].op == 1) {
                    b[k - 1].num += b[k + 1].num;
                    // -1: 연산 대상에서 제외
                    b[k].op = -1;
                    b[k + 1].num = 0;
                }
                else if(b[k].op == 2) {
                    b[k - 1].num -= b[k + 1].num;
                    b[k].op = -1;
                    b[k + 1].num = 0;
                }
                else if(b[k].op == 3) {
                    b[k - 1].num *= b[k + 1].num;
                    b[k].op = -1;
                    b[k + 1].num = 0;
                }
            }
        }
        
        vector<Term> c;
        for(int j = 0;j < n;j++) {
            if(j % 2 == 0) {
                c.push_back(b[j]);
            }
            else {
                if(b[j].op == -1) {
                    j += 1;
                }
                else {
                    // 곱하기면 우선 연산
                    if(b[j].op == 3) {
                        int num = c.back().num * b[j + 1].num;
                        c.pop_back();
                        c.push_back({num, 0});
                        j += 1;
                    }
                    else {
                        c.push_back(b[j]);
                    }
                }
            }
        }
        
        b = c;
        int m2 = ((int)b.size() - 1) / 2;
        int res = b[0].num;
        // 곱하기는 이미 연산했기 때문에 없음
        for(int j = 0;j < m2;j++) {
            int k = 2 * j + 1;
            if(b[k].op == 1) {
                res += b[k + 1].num;
            }
            else if(b[k].op == 2) {
                res -= b[k + 1].num;
            }
        }
        
        if(ans < res) {
            ans = res;
        }
    }
    cout << ans << '\n';
}

💚 17085 십자가 2개 놓기

십자가의 중심 = N * M

십자가 크기의 최댓값 = min(N, M) / 2

총 방법의 수 = N * M * min(N, M) $<= 15^3 = 3,375$

십자가 두 개를 놓을 수 있는 방법의 수는 3,375 * 3,375 = 11,390,625 이하다.

모든 방법을 시도해봐도 시간 안에 해결할 수 있다.

 

💚 16987 계란으로 계란치기

#include <iostream>
#include <vector>
#include <string>
using namespace std;
int s[10];
int w[10];
int n;

int go(int index) {
    if(index == n) {
        int cnt = 0;
        for(int i = 0;i < n;i++) {
            if(s[i] <= 0) {
                cnt += 1;
            }
        }
        
        return cnt;
    }
    // 이미 깨진 계란 패스
    if(s[index] <= 0) {
        return go(index + 1);
    }
    
    int ans = 0;
    bool ok = false;
    for(int j = 0;j < n;j++) {
        int i = index;
        if(i == j) continue;
        if(s[j] > 0) {
            ok = true;
            s[i] -= w[j];
            s[j] -= w[i];
            int temp = go(index + 1);
            if(ans < temp) ans = temp;
            s[i] += w[j];
            s[j] += w[i];
        }
    }
    
    // 가능한 경우가 없으면 현재 계란 패스
    if(!ok) {
        return go(index + 1);
    }
    
    return ans;
}

int main() {
    cin >> n;
    for(int i = 0;i < n;i++) {
        cin >> s[i] >> w[i];
    }
    
    cout << go(0) << '\n';
    return 0;
}