[중급 알고리즘] Brute Force 문제

💚 16968 차량 번호판 1

- 차량 번호판은 길이가 4이하이면서, c와 d로 이루어진 문자열

- c는 문자, d는 숫자

- 같은 문자나 숫자가 두 번 연속해서 나타나면 안된다.

- 가능한 차량 번호판의 개수를 구하는 문제 

 

- 전체 경우의 수를 살펴보는 것이 가능하다.

- 조합을 해결해 풀 수도 있다.(난 처음에 바로 이걸 생각했다.)

예를 들어 cccc인 경우에는 $26 \times (26 - 1) \times (26 - 1) \times (26 - 1) \times (26 - 1) $ 

ccdd인 경우에는 $26 \times (26 - 1) \times 10 \times (10 -1)$

 

#include <iostream>

using namespace std;

int go(string &s, int index, char last) {
    if(s.length() == index) {
        return 1;
    }
    
    char start = (s[index] == 'c') ? 'a': '0';
    char end = (s[index] == 'c') ? 'z' : '9';
    
    int ans = 0;
    for(char i = start;i <= end;i++) {
        if(i != last) {
            ans += go(s, index + 1, i);
        }
    }
    
    return ans;
}

int main() {
    string s;
    cin >> s;
    cout << go(s, 0, ' ') << '\n';
    return 0;
}

 

💚 16917 양념 반 후라이드 반

반반치킨  * 2 = 양념 치킨 한 마리, 후라이드 치킨 한 마리를 만들 수 있다는 점에 문제가 까다로워졌다.

반반치킨을 몇 마리 구할지를 결정해야 한다.(항상 짝수 개 시켜야 한다.)

그러면 나머지 치킨을 몇 마리 살지 결정할 수 있따.

 

반반 치킨을 $2i$개 구매하였다면, 양념 치킨은 $X - i$개, 후라이드 치킨은 $Y - i$개 구매해야 한다.

 

💚 16922 로마 숫자 만들기

로마 숫자의 순서는 아무 의미 없다.

어떤 로마 숫자를 몇 개 쓸건지만 결정

대신 여기서 서로 다른 수의 개수를 세야한다는 점은 놓치면 안된다.

#include <iostream>
#include <algorithm>
using namespace std;
// 서로 다른 수를 체크하기 위한 배열
bool check[50 * 20 + 1];
int main() {
    int n;
    cin >> n;
    
    for(int i = 0;i <= n;i++) {
        for(int j = 0;j <= n - i;j++) {
            for(int k = 0;k <= n - i - j;k++) {
                int l = n - i - j - k;
                int sum = i + 5 * j + 10 * k + 50 * l;
                check[sum] = true;
            }
        }
    }
    
    int ans = 0;
    for(int i = 1;i <= 50 * 20;i++) {
        if(check[i]) ans++;
    }
    
    cout << ans << '\n';
    
}

 

💚 16924 십자가 찾기

#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>
using namespace std;
bool check[100][100];
int main() {
    int n, m;
    cin >> n >> m;
    vector<string> a(n);
    
    for(int i = 0;i < n;i++) {
        cin >> a[i];
    }
    
    vector<tuple<int,int,int>> ans;
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < m;j++) {
            if(a[i][j] == '*') {
                int l = 0;
                for(int k = 1;;k++) {
                    // 상하좌우로 같은 길이의 십자가
                    if(i + k < n && i - k >= 0 && j + k < m && j - k >= 0){
                        if(a[i + k][j] == '*' && a[i - k][j] == '*' && a[i][j + k] == '*' && a[i][j - k] == '*') {
                            l = k;
                        }
                        else {
                            break;
                        }
                    }
                    else {
                        break;
                    }
                }
                
                if(l > 0) {
                    ans.push_back(make_tuple(i + 1, j + 1, l));
                    check[i][j] = true;
                    for(int k = 1;k <= l;k++) {
                        check[i + k][j] = true;
                        check[i - k][j] = true;
                        check[i][j - k] = true;
                        check[i][j + k] = true;
                    }
                }
            }
        }
    }
    
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < m;j++) {
            if(a[i][j] == '*' && check[i][j] == false) {
                cout << -1 << '\n';
                return 0;
            }
        }
    }
    
    cout << ans.size() << '\n';
    for(auto &t: ans) {
        int x, y, len;
        tie(x, y, len) = t;
        cout << x << ' ' << y << ' ' << len << '\n';
    }
    
    return 0;
}

 

💚 16936 나3곱2

어떤 수를 3으로 나눈다.

소인수분해했을 때 3의 지수가 줄어들거나 같을 수는 있으나 많아질 수는 없다.

곱2로 3을 곱할 수 없기 때문

따라서 3의 지수가 가장 높은 수가 처음 수로 와야 한다.

그 다음에는 3의 지수가 하나씩 낮은(나3) 수들이 오름차순으로 정렬되어야 한다.(곱2)

a 벡터에 first에는 3의 개수를 음수로 넣고, second에는 실제수를 넣어서 3의 개수 내림차순, 실제 수 오름차순으로 정렬한 뒤 그대로 출력하면 된다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>
using namespace std;
bool check[100][100];
int main() {
    int n;
    cin >> n;
    // 3의 개수, 실제 수
    vector<pair<int, long long>> a(n);
    
    for(int i = 0;i < n;i++) {
        long long num;
        cin >> num;
        a[i].second = num;
        while(num % 3 == 0) {
            num /= 3;
            a[i].first += 1;
        }
        // 내림차순 정렬을 위함
        a[i].first = -a[i].first;
    }
    sort(a.begin(), a.end());
    
    for(int i = 0;i < n;i++) {
        cout << a[i].second << ' ';
    }
    
    cout << '\n';
    return 0;
}

💚 16937 두 스티커

#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>
using namespace std;

int main() {
    int h, w;
    cin >> h >> w;
    int n;
    cin >> n;
    vector<int> r(n), c(n);
    
    for(int i = 0;i < n;i++) {
        cin >> r[i] >> c[i];
    }
    
    int ans = 0;
    for(int i = 0;i < n;i++) {
        int r1 = r[i], c1 = c[i];
        for(int j = i + 1;j < n;j++) {
            int r2 = r[j], c2 = c[j];
            for(int rot1 = 0;rot1 < 2;rot1++) {
                for(int rot2 = 0;rot2 < 2;rot2++) {
                    // 두 스티커의 조합을 만든 후 회전하며 확인
                    if(r1 + r2 <= h && max(c1, c2) <= w) {
                        int temp = r1 * c1 + r2 * c2;
                        if(ans < temp) ans = temp;
                    }
                    
                    if(max(r1, r2) <= h && c1 + c2 <= w) {
                        int temp = r1 * c1 + r2 * c2;
                        if(ans < temp) ans = temp;
                    }
                    swap(r2, c2);
                }
                swap(r1, c1);
            }
        }
    }
    
    cout << ans << '\n';
    return 0;
}

💚 16938 캠프 준비

#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>
using namespace std;
int n, l, r, x;
int a[15];
int go(int index, int cnt, int sum, int easy, int hard) {
    if(index == n) {
        if(cnt >= 2 && l <= sum && sum <= r && hard - easy >= x) return 1;
        else return 0;
    }
    
    int cnt1 = go(index + 1, cnt + 1, sum + a[index], min(easy, a[index]), max(hard, a[index]));
    int cnt2 = go(index + 1, cnt, sum, easy, hard);
    
    return cnt1 + cnt2;
}
int main() {
    cin >> n >> l >> r >> x;
    for(int i = 0;i < n;i++) {
        cin >> a[i];
    }
    
    cout << go(0, 0, 0, 1000000, 0) << '\n';
    return 0;
}

 

💚 16943 숫자 재배치

string도 일종의 char 배열이기 때문에  next_permutation 사용이 가능하다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>
using namespace std;

int main() {
    string a;
    int b;
    cin >> a >> b;
    int ans = -1;
    sort(a.begin(), a.end());
    do {
        int c = stoi(a);
        if(a[0] != '0' && c < b) {
            if(ans == -1 || ans < c) {
                ans = c;
            }
        }
    }while(next_permutation(a.begin(), a.end()));
    
    cout << ans << '\n';
    return 0;
}

 

💚 16637 괄호 추가하기✨

- 길이가 N인 수식이 있다.($N <= 19$, 홀수)

- 수식의 정수는 0부터 9까지, 연산자는 +, -, *이다. 연산자 우선순위는 모두 같다.

예를 들어 3 + 8 * 7 - 9 * 2의 결과는 136이다.

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

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

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

- 3 + 8 * 7 - 9 * 2의 경우 136

 

괄호의 의미: 그 연산자를 먼저 연산해야 한다.

중첩도 없고, 연속도 없기 때문에 어떤 연산자를 먼저 계산할지만 알면 된다.

연산자가 연달아 있으면 안된다. 연달아 있으면 중첩, 연속 조건 위배되기 때문

 

#include <iostream>
#include <algorithm>
#include <vector>
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) {
                // 이를 통해 수와 부호를 모두 한 번에 파악 가능
                // 수, 부호, 수, 부호 식으로 입력되어있기 때문
                // 괄호가 적용된 연산부터 연산
                // 우선 연산하는 일이 연달아 있는 경우는 없기 때문에 0으로 초기화 가능
                int k = 2 * j + 1;
                if(b[k].op == 1) {
                    b[k - 1].num += b[k + 1].num;
                    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;
                }
            }
        }
        
        int res = b[0].num;
        for(int j = 0;j < m;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;
            }
            else if(b[k].op == 3) {
                res *= b[k + 1].num;
            }
        }
        
        if(ans < res) {
            ans = res;
        }
    }
    cout << ans << '\n';
    return 0;
}

 

💚 15683 감시✨

코드를 최소화할수록 실수할 가능성을 줄인다.

push_back vs. emplace_back

emplace_back이 push_back보다 빠르다는 소문이 있지만 이는 사실이 아니며, 둘은 다른 목적을 위한 도구이다.

 

📌 push_back calls the constructor of the data that you intend to push and pushes it to the container.

📌 emplace_back constructs "in place", so one skips an extra move operation, potentially creating faster bytecode. This is done by forwarding the arguments to the container's template type constructor.

 

On the surface, emplace_back might look like a faster push_back, but there is a subtle difference contained in the act of forwarding arguments.

 

emplace_back의 경우 multi-parameter가 가능하다.

 따라서 맞지 않은 값을 넣는 경우 push_back에서는 바로 오류가 발생하나, emplace_back에서는 컴파일 이후 오류가 발생해 디버깅이 어렵다.

 

참고

https://gumeo.github.io/post/emplace-back/

emplace_back vs push_back | Gudmundur Blog&Bio

#include <iostream>
#include <algorithm>
#include <vector>
#include <tuple>
using namespace std;
int dx[] = {0, 1, 0, -1};
int dy[] = {1, 0, -1, 0};

void check(vector<vector<int>> &a,vector<vector<int>> &b, int x, int y, int dir) {
    int n = a.size();
    int m = a[0].size();
    int i = x;
    int j = y;
    while(0 <= i && i < n && 0 <= j && j < m) {
        // 벽
        if(a[i][j] == 6) break;
        b[i][j] = a[x][y];
        i += dx[dir];
        j += dy[dir];
    }
}

int go(vector<vector<int>> &a, vector<tuple<int,int,int>> &cctv, int index, vector<int> dirs) {
    if(cctv.size() == index) {
        // a와 동일한 사이즈의 벡터 생성
        vector<vector<int>> b(a);
        for(int i = 0;i < cctv.size();i++){
            int what, x, y;
            tie(what, x, y) = cctv[i];
            // cctv 종류별, 방향별 확인
            if(what == 1) {
                check(a, b, x, y, dirs[i]);
            }
            else if(what == 2) {
                check(a, b, x, y, dirs[i]);
                check(a, b, x, y, (dirs[i] + 2)% 4);
            }
            else if(what == 3) {
                check(a, b, x, y, dirs[i]);
                check(a, b, x, y, (dirs[i] + 1) % 4);
            }
            else if(what == 4) {
                check(a, b, x, y, dirs[i]);
                check(a, b, x, y, (dirs[i] + 1) % 4);
                check(a, b, x, y, (dirs[i] + 2) % 4);
            }
            else if(what == 5) {
                check(a, b, x, y, dirs[i]);
                check(a, b, x, y, (dirs[i] + 1) % 4);
                check(a, b, x, y, (dirs[i] + 2) % 4);
                check(a, b, x, y, (dirs[i] + 3) % 4);
            }
        }
        
        int cnt = 0;
        int n = a.size();
        int m = a[0].size();
        
        for(int i = 0;i < n;i++) {
            for(int j = 0;j < m;j++) {
                if(b[i][j] == 0) {
                    cnt += 1;
                }
            }
        }
        
        return cnt;
    }
    
    int ans = 100;
    // 상하좌우
    // CCTV 별로 중복되는 방향을 제한해도 되나 번거롭기 때문에 그냥 탐색
    for(int i = 0;i < 4;i++) {
        dirs[index] = i;
        int temp = go(a, cctv, index + 1, dirs);
        if(ans > temp) {
            ans = temp;
        }
    }
    return ans;
}
int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m));
    vector<tuple<int,int,int>> cctv;
    vector<int> dirs;
    
    for(int i = 0;i < n;i++) {
        for(int j = 0;j < m;j++) {
            cin >> a[i][j];
            // CCTV
            if(a[i][j] >= 1 && a[i][j] <= 5) {
                cctv.emplace_back(a[i][j], i, j);
                dirs.push_back(0);
            }
        }
    }
    cout << go(a, cctv, 0, dirs) << '\n';
    return 0;
}

 

💚 17088 등차수열 변환

처음 두 개의 수가 정해지면, 등차수열을 만들 수 있다.

첫항과 공차를 알 수 있기 때문이다.

처음 두개의 수를 정하는 경우의 수는 $3 \times 3$

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

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    
    for(int i = 0;i < n;i++) {
        cin >> a[i];
    }
    // 예외 처리
    if(n == 1) {
        cout << 0 << '\n';
        return 0;
    }
    
    int ans = -1;
    
    for(int d1 = -1;d1 <= 1;d1++) {
        for(int d2 = -1;d2 <= 1;d2++) {
            int change = 0;
            if(d1 != 0) change += 1;
            if(d2 != 0) change += 1;
            
            int a0 = a[0] + d1;
            int diff = (a[1] + d2) - a0;
            bool ok = true;
            int an = a0 + diff;
            for(int i = 2;i < n;i++) {
                an += diff;
                if(a[i] == an) continue;
                if(a[i] - 1 == an) {
                    change += 1;
                }
                else if(a[i] + 1 == an) {
                    change += 1;
                }
                else {
                    ok = false;
                    break;
                }
            }
            
            if(ok) {
                if(ans == -1 || ans > change) {
                    ans = change;
                }
            }
        }
    }
    
    cout << ans << '\n';
    return 0;
}

💚 15686 치킨 배달

어차피 거리는 두 좌표로 구할 수 있기 때문에 격자를 사용하지 않아도 된다.

 

💚2210 숫자판 점프

서로 다른 수의 갯수를 셀 때는 set 이용하면 편하다.

set에는 중복이 불가능하기 때문이다.

 

💚9944 N x M 보드 완주하기 ✨💥(굴리기 문제, 2차원 좌표 문제)

- N * M 보드가 있다. 보드의 각 칸은 빈 칸 또는 장애물이다.

- 보드 위에 공을 하나 놓고, 모든 칸을 방문하려고 한다.

- 공은 네 방향 중 한 방향으로 더 이상 이동하지 않을 때까지 이동한다.

(장애물, 경계, 이미 지나간 칸 만나면 더 이상 이동 X)

 

- 보드의 모든 칸 위에 공을 놓았다고 가정하고 모든 네 방향을 다 이동해본다.

#include <iostream>
#include <vector>
using namespace std;\
char a[33][33];
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
int n, m;
bool inside(int x, int y) {
    return 0 <= x && x < n && 0 <= y && y < m;
}

int go(int x, int y, int cnt) {
    int ans = -1;
    if(cnt == 0) {
        return 0;
    }
    
    for(int k = 0;k < 4;k++) {
        int nx = x + dx[k];
        int ny = y + dy[k];
        
        while(inside(nx, ny) && a[nx][ny] == '.'){
            a[nx][ny] = '#';
            cnt -= 1;
            nx += dx[k];
            ny += dy[k];
        }
        // 위 while문 조건으로 인해 반드시 하나 감소해야 .에 위치
        nx -= dx[k];
        ny -= dy[k];
        
        // 움직임이 없는 경우 제외
        if(!(x == nx && y == ny)) {
            int temp = go(nx, ny, cnt);
            if(temp != -1) {
                // temp + 1: 이전 값 + 현재 1
                if(ans == -1 || ans > temp + 1) {
                    ans = temp + 1;
                }
            }
        }
        
        // 원상복귀
        while(!(x == nx && y == ny)) {
            a[nx][ny] = '.';
            cnt += 1;
            nx -= dx[k];
            ny -= dy[k];
        }
    }
    return ans;
}
int main() {
    int tc = 1;
    while(cin >> n >> m) {
        // 이동가능한 칸의 수
        int cnt = 0;
        for(int i = 0;i < n;i++) {
            cin >> a[i];
            for(int j = 0;j < m;j++) {
                if(a[i][j] == '.') {
                    cnt += 1;
                }
            }
        }
        
        int ans = -1;
        for(int i = 0;i < n;i++){
            for(int j = 0;j < m;j++) {
                if(a[i][j] == '.') {
                    // 방문 표시
                    a[i][j] = '#';
                    int temp = go(i, j, cnt - 1);
                    if(temp != -1) {
                        if(ans == -1 || ans > temp) {
                            ans = temp;
                        }
                    }
                    a[i][j] = '.';
                }
            }
        }
        
        cout << "Case " << tc << ": " << ans << '\n';
        tc += 1;
    }
    return 0;
}

 

💚 17089 세 친구

- N명의 사람 중에서 세 사람 A, B, C를 고르려고 한다.

- A, B를 구하는 방법 = $O(N^2)$

- A, B가 친구일 때만 C를 구한다.  → 최대 M번만 수행(연산 횟수 대폭 감소)

- 그 다음 C를 구하는 방법 = $O(N)$

- 따라서 총 $O(N^2 + MN)$

 

💚 17406 배열 돌리기4

배열의 요소들을 옮길 때 순서가 매우 중요하다.

순서 꼬여서 틀렸던 경험 다수

직접 배열의 요소들을 옮기는 것이 어려우면 별도의 자료구조에 담아서 옮기는 것도 좋은 방법이다. 경험상 그러면 실수 확률이 확 줄어든다.

그리고 주목해야할 메소드로 rotate가 존재한다. 평소에 하나씩 인덱싱해서 옮기는 것보다 훨씬 유용해보인다.

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>

using namespace std;
void go(vector<vector<int>> &a, tuple<int, int, int> t) {
    int row, col, size;
    tie(row, col, size) = t;
    vector<vector<int>> groups;
    
    for(int s = 1;s <= size;s++) {
        vector<int> group;
        
        // (r - s, c - s) -> (r - s, c + s)
        for(int r = row - s, c = col - s;c < col + s;c++) {
            group.push_back(a[r][c]);
        }
        
        // (r - s, c + s) -> (r + s, c + s)
        for(int r = row - s, c = col + s;r < row + s;r++) {
            group.push_back(a[r][c]);
        }
        
        // (r + s, c + s) -> (r + s, c - s)
        for(int r = row + s, c = col + s;c > col - s;c--) {
            group.push_back(a[r][c]);
        }
        
        // (r + s, c - s) -> (r - s, c - s)
        for(int r = row + s, c = col - s;r > row - s;r--) {
            group.push_back(a[r][c]);
        }
        groups.push_back(group);
    }
    
    // 순서대로 값을 옮겨준다.
    for(int s = 1;s <= size;s++) {
        auto &group = groups[s - 1];
        
        // simple rotation to the right
        // left로 회전하기 위해서는 r만 제거하면 된다.
        rotate(group.rbegin(), group.rbegin() + 1, group.rend());
        
        int len = group.size();
        int index = 0;
        
        for(int r = row - s, c = col - s;c < col + s;c++) {
            a[r][c] = group[index++];
        }
        
        // (r - s, c + s) -> (r + s, c + s)
        for(int r = row - s, c = col + s;r < row + s;r++) {
            a[r][c] = group[index++];
        }
        
        // (r + s, c + s) -> (r + s, c - s)
        for(int r = row + s, c = col + s;c > col - s;c--) {
            a[r][c] = group[index++];
        }
        
        // (r + s, c - s) -> (r - s, c - s)
        for(int r = row + s, c = col - s;r > row - s;r--) {
            a[r][c] = group[index++];
        }
    }
}

int main() {
    int n, m, k;
    cin >> n >> m >> k;
    vector<vector<int>> a(n, vector<int>(m));
    
    for(int i = 0; i <n;i++) {
        for(int j = 0;j < m;j++) {
            cin >> a[i][j];
        }
    }
    
    vector<tuple<int, int, int>> d(k);
    
    for(int i = 0;i < k;i++) {
        int r, c, s;
        cin >> r >> c >> s;
        d[i] = make_tuple(r - 1, c - 1, s);
    }
    
    sort(d.begin(), d.end());
    
    int ans = 100 * 100;
    do {
        auto b = a;
        // 회전 연산 사용
        for(auto &t : d) {
            go(b, t);
        }
        
        for(int i = 0;i < n;i++) {
            int sum = 0;
            for(int j = 0;j < m;j++) {
                sum += b[i][j];
            }
            
            if(ans > sum) ans = sum;
        }
    } while(next_permutation(d.begin(), d.end()));
    cout << ans << '\n';
    return 0;
}