[백준] 알고리즘 2일차 문제 및 복습

1. 16936번 : 나3곱2

16936번: 나3곱2

3으로 나누는 것 - 3^k x A    /    3    =  3^k-1 x A

즉 3으로 몇 번 나눠지냐 이걸 확인해준 후, 오름차순으로 정렬만 해주면 된다.

문제에서 항상 정답이 존재하는 경우에만 입력으로 주어지고, 애당초 수열B는 A를 섞어서 입력받는 거기 때문에, 안되는 경우는 없다.

 

3으로 몇번 나눠지는가?의 갯수

9 - 3 - 6 - 12 - 4 - 8

#include <bits/stdc++.h>
using namespace std;
bool cmp(pair<long, long> &a, pair<long, long> &b) {
    if (a.second == b.second) {
        return a.first < b.first;
    }
    else return a.second > b.second;
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n;
    cin >> n;
    vector<pair<long,long>> v;
    for (int i = 0; i < n; i++) {
        long long x, temp;
        int count=0;
        cin >> x;
        temp = x;
        while (1) {
            if (temp % 3 == 0) {
                count++;
                temp /= 3;
            }
            else break;
        }
        v.push_back(make_pair(x,count));
    }
    sort(v.begin(), v.end(), cmp);
    for (int i = 0; i < v.size(); i++) {
        cout << v[i].first << " ";
    }
}

백터의 사용방법을 계속 익혀나가야 겠다.

pair = 2개의 인자 즉 쌍을 입력받을 때 사용

tuple = 3개 이상의 인자를 입력받을 때 사용

백터의 sort 기본 정렬은 오름차순이다.

pair에서도 마찬가지인데, second 값을 기준으로 요리를 하고싶다면 함수를 하나 생성하여 비교해줄 수 있다.

 

2. 16937번 : 두 스티커

16937번: 두 스티커

세로를 접할 때 =     R1+R2<=H max(c1,c2)<=W

가로를 접할 때 =     max(R1,R2)<=H C1+C2<=R

회전을 할때와 안할때도 각각 생각해주어야 한다.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int h, w, n;
    cin >> h >> w >> 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];
        int c1 = c[i];
        for (int j = i + 1; j < n; j++) {
            int r2 = r[j];
            int c2 = c[j];
            for (int rot1 = 0; rot1 < 2; rot1++) {
                for (int rot2 = 0; rot2 < 2; rot2++) {
                    int range = (r1 * c1) + (r2 * c2);
                    if (r1 + r2 <= h && max(c1, c2) <= w) {
                        ans = max(range, ans);
                    }
                    if (max(r1, r2) <= h && c1 + c2 <= w) {
                        ans = max(range, ans);
                    }
                    swap(r2, c2);
                }
                swap(r1, c1);
            }
        }
    }
    cout << ans;
}

3. 16938번 : 캠프 준비

16938번: 캠프 준비

yabmoons.tistory.com/272

조합 / 순열에 관하여 재귀함수로 잘 정리되어있는 블로그입니다. 참고하면 재귀에 관한 조합을 확실히 이해할 수 있다.

 

#include <bits/stdc++.h>
using namespace std;
int n, l, r, x,ans;
int a[16];
vector<int> v;
bool check[16];
void go(int idx,int cnt,int _sum) {
    if (cnt >= 2) {
        int min = 987654321;
        int max = -987654321;
        int sum = 0;

        for (int i = 0; i < v.size(); i++) {
            sum = sum + a[v[i]];
            if (a[v[i]] < min) min = a[v[i]];
            if (a[v[i]] > max) max = a[v[i]];
        }
        if (l <= sum && sum <= r && max - min >= x) ans++;
    }
    for (int i = idx; i < n; i++) {
        if (check[i] == true) continue;
        if (_sum + a[i] <= r) {
            check[i] = true;
            v.push_back(i);
            go(i, cnt+1, _sum + a[i]);
            v.pop_back();
            check[i] = false;
        }
    }
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
      //n=문재 개수, l<=문제 난이도합<=r, 가장어려움-가장쉬움>=x
    cin >> n >> l >> r >> x;
    
    for (int i = 0; i < n; i++) cin >> a[i];
    go(0, 0, 0);
    cout << ans;
}

4. 16943번 : 숫자 재배치

순열을 생각해서 문제를 해결한다. 

#include <bits/stdc++.h>
using namespace std;
int ia[10];
int n,b;
bool check[10];
int go(int idx,int num) {
    if (idx == n) {
        return num;
    }
    int ans = -1;
    for (int i = 0; i < n; i++) {
        if (check[i] == true) continue;
        if (idx == 0 && ia[i] == 0) continue;
        check[i] = true;
        int temp = go(idx+1, ia[i]+num*10);
        if (temp < b) {
            if (ans == -1 || ans < temp) {
                ans = max(temp, ans);
            }
        }
        check[i] = false;
    }
    return ans;
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    string a;
    cin >> a>>b;
    n = a.size();
    for (int i = 0; i < n; i++) {
        ia[i] = a[i] - '0';
    } // a를 숫자로 ia배열에 재저장
   
    cout << go(0, 0);

}

5. 15683번 : 감사

15683번: 감시

이 문제는 dfs를 이용하여 단순 구현문제인데,

주의할점은 90도씩 방향을 바꿀 수 있다는 점이다.

1번 cctv는 한 방향만 신경 써주면 된다

2번 cctv는 양옆 위아래 이렇게 두 개를 신경 써야 하기 때문에 

for (int i = 0; i <= 2; i += 2) {
            int _y = y;
            int _x = x;
            while (true) {
                int ny = _y + dy[(dir+i)%4];
                int nx = _x + dx[(dir+i)%4];

이부분을 작성해주면 된다. i의 값에 따라 기준점에서 부터 i=0일때, 양옆 2일때 위아래의 검사를 하게 된다.

dx, dy의 값의 위치를 잘 생각하면서 넣어주는 것을 주의해야한다. 나는 반대로 넣었다가 마지막에 이해하여 제대로 넣었다.

#include <bits/stdc++.h>
using namespace std;
int n, m,ans=987654321;
int arr[10][10];
int dx[4] = { 0,1,0,-1 };
int dy[4] = { -1,0,1,0 };
vector<pair<int, int>> v;
vector<pair<int, int>> cctv(int here, int dir) {
    vector<pair<int, int>> _change;
    int y = v[here].first;
    int x = v[here].second; //어떤 cctv 번호인지
    if (arr[y][x] == 1) {
        int _y = y;
        int _x = x;
        while (true) {
            int ny = _y + dy[dir];
            int nx = _x + dx[dir];
            if (ny >= 0 && ny < n && nx >= 0 && nx < m && arr[ny][nx] != 6) {
                if (arr[ny][nx] == 0) {
                    arr[ny][nx] = 8;
                    _change.push_back({ ny,nx });
                }
                    _y = ny;
                    _x = nx;
                
            }
            else break;
        }
    }
    else if(arr[y][x]==2) {
        for (int i = 0; i <= 2; i += 2) {
            int _y = y;
            int _x = x;
            while (true) {
                int ny = _y + dy[(dir+i)%4];
                int nx = _x + dx[(dir+i)%4];
                if (ny >= 0 && ny < n && nx >= 0 && nx < m && arr[ny][nx] != 6) {
                    if (arr[ny][nx] == 0) {
                        arr[ny][nx] = 8;
                        _change.push_back({ ny,nx });
                    }
                        _y = ny;
                        _x = nx;
                    
                }
                else break;
            }
        }
    }
    else if (arr[y][x] == 3) {
        for (int i = 0; i < 2; i++) {
            int _y = y;
            int _x = x;
            while (true) {
                int ny = _y + dy[(dir + i) % 4];
                int nx = _x + dx[(dir + i) % 4];
                if (ny >= 0 && ny < n && nx >= 0 && nx < m && arr[ny][nx] != 6) {
                    if (arr[ny][nx] == 0) {
                        arr[ny][nx] = 8;
                        _change.push_back({ ny,nx });
                    }
                        _y = ny;
                        _x = nx;
                    
                }
                else break;
            }
        }
    }
    else if (arr[y][x] == 4) {
        for (int i = 0; i < 3; i++) {
            int _y = y;
            int _x = x;
            while (true) {
                int ny = _y + dy[(dir + i) % 4];
                int nx = _x + dx[(dir + i) % 4];
                if (ny >= 0 && ny < n && nx >= 0 && nx < m && arr[ny][nx] != 6) {
                    if (arr[ny][nx] == 0) {
                        arr[ny][nx] = 8;
                        _change.push_back({ ny,nx });
                    }
                    _y = ny;
                    _x = nx;

                }
                else break;
            }
        }
    }
    else if (arr[y][x] == 5) {
        for (int i = 0; i < 4; i++) {
            int _y = y;
            int _x = x;
            while (true) {
                int ny = _y + dy[(dir + i) % 4];
                int nx = _x + dx[(dir + i) % 4];
                if (ny >= 0 && ny < n && nx >= 0 && nx < m && arr[ny][nx] != 6) {
                    if (arr[ny][nx] == 0) {
                        arr[ny][nx] = 8;
                        _change.push_back({ ny,nx });
                    }
                    _y = ny;
                    _x = nx;

                }
                else break;
            }
        }
    }
    return _change;
}
void dfs(int here) {
    if (here == v.size()) {
        int cnt = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (arr[i][j] == 0) cnt++;
            }
        }
        ans = min(cnt, ans);
        return;
    }
    for (int k = 0; k < 4; k++) {
        vector<pair<int, int>> _changed = cctv(here, k);
        dfs(here + 1);
        for (pair<int, int> b : _changed) {
            arr[b.first][b.second] = 0;
        }
    }
    return;
}
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
     
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> arr[i][j];
            if (arr[i][j] != 0 && arr[i][j] != 6) {
                v.push_back(make_pair(i, j));
            }
        }
    }
    dfs(0);
    cout << ans;

}