아인스트라세의 SW 블로그

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

백준 14890번 문제 경사로 풀이이다.

구현 문제인데, 어떻게 하면 효율적으로 풀 지 고민을 해 보았다.

만약 경사로가 다음과 같이 나타난다면 다음과 같은 자료구조로 변환하여 문제를 풀이하였다.

1 1 1 1 2 2 3 3 3 3 3

만약 위와 같은 형태로 경사로가 구성되어 있다면, 1이 4개 2가 2개 3이 5개이므로 다음과 같은 형태로 저장한다.

(1, 4) (2, 2) (3, 5)

경사로를 놓는데에 L의 길이가 필요하다면, 낮은 위치에 길이를 L만큼 제외하고 음수가 되게 되면 실패한다고 생각하였다.

 

#include <bits/stdc++.h>
using namespace std;

int field[105][105];
int road[105];
typedef pair<int, int> pii;
int main() {
    int n;
    int l;
    cin >> n >> l;
    int ans = 0;
    for (int i=1; i <= n; i++) {
        for (int j=1;j <= n; j++) {
            cin >> field[i][j];
        }
    }
    
    //garo check
    vector<pii> arr; //값, 연속개수
    for (int i=1; i <= n; i++) {
        arr.clear();
        int prev = field[i][1];
        int prev_num = 1;
        for (int j=2; j <= n ;j++) {
            auto& cur = field[i][j];
            if (cur != prev) {
                arr.push_back(make_pair(prev, prev_num));
                prev_num = 0;
            }
            prev_num++;
            prev = cur;
        }
        arr.push_back(make_pair(prev, prev_num));

        bool correct = true;
        for (int k=1; k < (int)arr.size(); k++) {
            auto& p_height = arr[k-1].first;
            auto& p_length = arr[k-1].second;
            auto& c_height = arr[k].first;
            auto& c_length = arr[k].second;
            int delta = p_height - c_height;
            if (delta*delta > 1) {
                correct = false;
                break;
            }
            if (p_height == c_height+1) {
                c_length -= l;
                if (c_length < 0) {
                    correct = false;
                }
            } else if (p_height+1 == c_height) {
                p_length -= l;
                if (p_length < 0) {
                    correct = false;
                }
            }
        }
        
        if (correct) {
            ans++;
        }
    }
    
    //sero check
    for (int i=1; i <= n; i++) {
        arr.clear();
        int prev = field[1][i];
        int prev_num = 1;
        for (int j=2; j <= n ;j++) {
            auto& cur = field[j][i];
            if (cur != prev) {
                arr.push_back(make_pair(prev, prev_num));
                prev_num = 0;
            }
            prev_num++;
            prev = cur;
        }
        arr.push_back(make_pair(prev, prev_num));

        bool correct = true;
        for (int k=1; k < (int)arr.size(); k++) {
            auto& p_height = arr[k-1].first;
            auto& p_length = arr[k-1].second;
            auto& c_height = arr[k].first;
            auto& c_length = arr[k].second;
            int delta = p_height - c_height;
            if (delta*delta > 1) {
                correct = false;
                break;
            }
            if (p_height == c_height+1) {
                c_length -= l;
                if (c_length < 0) {
                    correct = false;
                }
            } else if (p_height+1 == c_height) {
                p_length -= l;
                if (p_length < 0) {
                    correct = false;
                }
            }
        }
        
        if (correct) {
            ans++;
        }
    }
    
    cout << ans << endl;
    
	return 0;
}

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

백준저지 14889번 스타트와 링크 문제 풀이이다.

N값이 크지 않으므로 dfs를 통한 완전 탐색으로 문제 해결이 가능하다.

다음은 풀이 코드이다.

 

#include <bits/stdc++.h>

using namespace std;

bool team[20];
int n;
int s[20][20];
int ans;
int abs(int v) {
    if (v<0) return -v;
    else return v;
}
void check() {
    int start=0;
    int link=0;
    vector<int> ss, ll;
    ss.reserve(n/2);
    ll.reserve(n/2);
    for (int i=0; i <n; i++) {
        if (team[i]) {
            ss.push_back(i);
        } else {
            ll.push_back(i);
        }
    }
    for (int i=0; i < n/2; i++) {
        for (int j=0; j < n/2; j++) {
            if (i==j) continue;
            start += s[ss[i]][ss[j]];
        }
    }
    for (int i=0; i < n/2; i++) {
        for (int j=0; j < n/2; j++) {
            if (i==j) continue;
            link += s[ll[i]][ll[j]];
        }
    }
    ans = min(ans, abs(start-link));
}
void dump() {
    for (int i=0; i < n; i++) {
        cout << team[i] << ", ";
    }
    cout << '\n';
}
void dfs(int i, int j) {
    if (j > n-i) return;
    if (i >= n) {
        if (j == 0) {
            // dump();    
            check();
        }
        return;
    }
    team[i] = true;
    dfs(i+1, j-1);
    team[i] = false;
    dfs(i+1, j);
}
int main() {
    ans = 987654321;
    cin >> n;
    for (int i=0; i < n; i++) {
        for (int j=0; j < n;j++) {
            cin >> s[i][j];
        }
    }
    dfs(0, n/2);
    cout << ans << '\n';
    return 0;
}

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

백준 14888번 문제 연산자 끼워넣기 풀이이다.

N값이 크지 않으므로 dfs를 통한 완전탐색으로 문제를 해결할 수 있다.

 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
int arr[12];
int n;

//returns (min, max) value
pll dfs(ll lval, int index, int plus, int minus, int mult, int div) {
    if (index >= n) return make_pair(lval, lval);
    ll rmin = 9876543210000LL;
    ll rmax = -9876543210000LL;
    
    ll rval = (ll)arr[index];
    if (plus > 0) {
        pll ret = dfs(lval + rval, index+1, plus-1, minus, mult, div);
        rmin = min(rmin, ret.first);
        rmax = max(rmax, ret.second);
    }
    if (minus > 0) {
        pll ret = dfs(lval - rval, index+1, plus, minus-1, mult, div);
        rmin = min(rmin, ret.first);
        rmax = max(rmax, ret.second);
    }
    if (mult > 0) {
        pll ret = dfs(lval * rval, index+1, plus, minus, mult-1, div);
        rmin = min(rmin, ret.first);
        rmax = max(rmax, ret.second);
    }
    if (div > 0) {
        pll ret = dfs(lval / rval, index+1, plus, minus, mult, div-1);
        rmin = min(rmin, ret.first);
        rmax = max(rmax, ret.second);
    }
    
    return make_pair(rmin, rmax);
}
int main() {
    
    cin >> n;
    for (int i=0; i <n; i++) {
        cin >> arr[i];
    }
    int a,b,c,d;
    cin >> a >> b >> c >> d;
    pll ans = dfs(arr[0], 1, a, b, c, d);
    cout << ans.second << '\n' << ans.first << endl;
	return 0;
}