[백준] 알고리즘 강의 1일차 문제 및 복습

브루트 포스

1. 16968번 : 차량 번호 문제

16968번: 차량 번호판 1

#include <bits/stdc++.h>
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() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    string s;
    cin >> s;
    cout << go(s, 0, ' ');
    
}

최대 길이 _ _ _ _ 4^26 해도 초과하지 않으니 재귀로 문제를 해결한다.

재귀의 가장 중요한 부분은 탈출문을 잘 생각해야 한다.

이 문제에서의 탈출문은 입력받은 문자열 s의 길이와, 카운트하는 인덱스가 같을 경우 종료시킨다.

가능한 번호판을 다 구해라

인 경우 재귀로 해결해도 좋다. 다만 시간복잡도가 상당한거 같으니 아래를 추천한다.

조합을 이용해서 문제를 해결할 수 있다.

for (int i = 0; i < s.length(); i++) {
        int cnt = (s[i] == 'c' ? 26 : 10); 
        if (i>0&&s[i] == s[i-1]) {
            cnt=cnt-1;
        }
        ans *= cnt;
    }

2. 16917번 : 양념 반 후라이드 반 문제

16917번: 양념 반 후라이드 반

구매할 반반 치킨의 수를 정해두면, 나머지 치킨을 몇 개 구매해야하는지 구할 수 있다.

모든 경우의 수를 다 해봐야 최소값을 찾을 수 있다.

그냥 단순히 if else문으로 내가 직접 구현해보았다.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int a, b, c, x, y;
    cin >> a >> b >> c >> x >> y;
    int oprice = 0, hprice = 0;
    oprice = a * x + b * y;
    if (x == y) hprice = x * 2 * c;
    else if (x > y) hprice = min(y * 2 * c + (x - y) * a, y*2*c+(x-y)*2*c);
    else hprice = min(x * 2 * c + (y - x) * b,x*2*c+(y-x)*2*c);
    cout << min(oprice, hprice);
}

이런식으로 조건식을 찾아서 구현할줄만 알면 모든 경우의 수를 다 해보는것보다 좋아보인다.

모든 경우의 수를 해보는 방법

for (int i=1; i<=100000; i++) {
        int price = 2*i*c + max(0, x-i)*a + max(0, y-i)*b;
        if (ans > price) ans = price;
    }

x,y의 범위가 100000으로 반반치킨은 이 값의 두배가 필요하므로 반반치킨=2i개가 필요하다.

이에 즉 1<=2i<=200000 i는 1<=i<=100000의 범위에 대해서 구해주면 된다.

 
        int price = 2*i*c + max(0, x-i)*a + max(0, y-i)*b;
 

이 부분이 위에서 내가 직접 if else문을 짯던걸 한줄로 해결할 수 있는 문장이다.

아직은 내가 많이 부족한거같다. 코드의 효율성을 좀 더 신경써야겠다.

 

3. 16922번 : 로마 숫자 만들기

16922번: 로마 숫자 만들기

 

서로 다른 수는 미리 제외 시킬 수 있다.

v i i x = 17

x i i v = 17

v i x i = 17

합이 같다면 순서만 다른 조합은 필요없다.I : A개V : B개X : C개L : N-A-B-C개 항상 길이가 N이 되어야함.각 N 자리수에 로마 숫자가 몇개 오는지를 결정해서 해결할 수 있음.

#include <bits/stdc++.h>
using namespace std;
bool check[1001];
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n - i; j++) {
            for (int z = 0; z <= n - i - j; z++) {
                int l = n - i - j - z;
                int sum = i + 5 * j + 10 * z + l * 50;
                check[sum] = true;
            }
        }
    }
    int ans = 0;
    for (int i = 1; i <= 1000; i++) {
        if (check[i]) ans += 1;
    }
    cout << ans;
}

4. 16924번 : 십자가 찾기

16924번: 십자가 찾기

가장 중요한 조건 만들 수 있는 경우에는 필요한 십자가의 수 k(0 ≤ k ≤ N×M)를 출력한다.

모든 *을 십자가의 중앙이라고 가정하고, 최대한 크게 그려본다.

즉 십자가의 크기 5개짜리를 만들 수 있으면 1~4개까지는 무조건 그릴 수 있으므로 최대한 크게 그려본다.

 

auto : 자동으로 변수를 생각해서 출력해줌

range based for

vector<int> v = {10, 20, 30, 40};
for (int i: v) {
    cout << i << ' ';  // 실핼결과: 10 20 30 40
}

 

#include <bits/stdc++.h>
using namespace std;
bool check[101][101];
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    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>> v;
    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 >= 0 && i + k < n && j - k >= 0 && j + k < m) {
                        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) {
                    v.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";
        }
    }
    cout << v.size() << "\n";
    for (auto &t : v) {
        int x, y, len;
        tie(x, y, len) = t;
        cout << x << " " << y << " " << len << "\n";
    }
}

a[i][j] = 가장 중심의 별이라 가정하고, 위아래양옆을 검사하여 만약 십자가면 l의 변수에 k값을 저장(k값은 십자가의 크기를 저장한다.)