[문제 링크]


발상적으로 좀 어려웠던 문제다. 최단거리를 구하는 것이기 때문에 BFS로 전체 경우를 계산에 풀 면 되는데.


처음엔 구슬들을 모두 벡터로 처리해 복잡해져서 고전했다. 


좌표가 겹치게 되는 구슬은 어차피 이후 행적은 모두 동일하기 때문에 그냥 SET으로 중복되는부분은 제거하는 방식으로 풀면 된다.



#include <iostream>
#include <string>
#include <queue>
#include <set>
using namespace std;
int t, n, m;
char maze[11][11];
typedef pair<int, int> coordi;
const char nextAc[4] = { 'L','R','U','D' }, reAc[4] = { 'R','L','D','U' };
const int relPos[4][2] = { { -1,0 },{ 1,0 },{ 0,-1 },{ 0,1 } };
coordi exitPos;
class Info {
public:
    set<coordi > pos;
    string ret;
    Info() { ret = ""; }
    Info(set<coordi > nSet, string nRet) {
        pos = nSet;
        ret = nRet;
    }
};
Info* Maze(Info in) {
    queue<Info> q;
    q.push(in);
    //BFS
    while (!q.empty()) {
        Info cur = q.front(); q.pop();
        char curAc = ' ';
        if (cur.ret.length() != 0) curAc = cur.ret[cur.ret.length() - 1];
        for (int i = 0; i<4; i++) {
            set<coordi> nextSet;
            //가지치기. 
            if (nextAc[i] != curAc && curAc != reAc[i]) {
                for (set<coordi>::iterator it = cur.pos.begin(); it != cur.pos.end(); it++) {
                    int px = (*it).first, py = (*it).second;
                    bool flag = true;
                    //다음 이동이 벽이기 전까지 이동. 혹은 현재 위치가 출구일때 까지
                    while (maze[py + relPos[i][1]][px + relPos[i][0]] != '#') {
                        px += relPos[i][0];
                        py += relPos[i][1];
                        if(maze[py][px] == 'O') flag = false;
                    }
                    if(flag) nextSet.insert(make_pair(px, py));
                }
                //다음 값이 현재 값과 일치하면 continue
                if (nextSet == cur.pos) continue;
                //set의 사이즈가 0이면 모두 탈출 -> 결과 객체 반환 
                if(nextSet.size() == 0){
                    return new Info(nextSet, cur.ret + nextAc[i]);
                }
                //현재 액션의 길이가 10이 넘어서면 NULL 반환 
                else if ((cur.ret + nextAc[i]).length() > 10) return NULL;
                q.push(Info(nextSet, cur.ret + nextAc[i])); 
            
            }
        }   
    }
    return NULL;
}
int main() {
    cin >> t;
    while (t--) {
        Info in;
        cin >> n >> m;
        for (int y = 0; y<n; y++) {
            for (int x = 0; x<m; x++) {
                cin >> maze[y][x];
                if (maze[y][x] == '.') in.pos.insert(make_pair(x, y));
                else if (maze[y][x] == 'O') {
                    exitPos = make_pair(x, y);
                }
            }
        }
        Info* retInfo = Maze(in);
        if (retInfo == NULL) cout << "XHAE" << endl;
        else cout << retInfo->ret << endl;
    }
}

'Algorithm > Problems' 카테고리의 다른 글

백준 - 10218 Maze  (1) 2016.06.20
백준 - 10217 KCM Travel  (0) 2016.06.20
백준 - 10216 Count Circle Groups  (0) 2016.06.20
백준 - 10215 Colored Bead Work  (0) 2016.06.20
백준 - 1992 쿼드트리  (1) 2016.05.25
백준 - 10215 Colored Bead Works  (0) 2016.05.25
  1. 1466956084 2016.06.27 00:48

    좋은하루되세요


[문제 링크]



그래프 문제이다. 최단거리를 구하는 문제이기 때문에 다익스트라를 이용해서 풀 수 있다.


다만 가중치만 존재하는 것이 아니라 금액도 같이 주어지기 때문에 DP를 이용해서 풀어야한다.


특정 공항에 도착했을때 남은 금액과 가중치가 모두 다르기 때문이다.





#include <cstdio>
#include <vector>
#include <utility>
#include <queue>
#include <cstring>
#define MAXV 987654321
using namespace std;
int t, n, m, k,cache[102][10002];
class Info {
public:
    int v, x, d;
    Info(int v, int x, int d) :v(v), x(x), d(d) {
    }
};
struct cmp {
    bool operator()(Info x, Info y) {
        return x.d > y.d;
    }
};
vector<Info> adj[102];
int kcmTravel() {
    int ret = MAXV;
    priority_queue<Info, vector<Info>, cmp> pq;
    //memoization reset 
    memset(cache, -1, sizeof(cache));
    cache[1][0] = 0;
    pq.push(Info(1, 0, 0));
    while (!pq.empty()) {
        Info cur = pq.top(); pq.pop();
        //현재 저장된 가중치보다 크거나 비용이 초과하면  continue 
        if (cur.d > cache[cur.v][cur.x] || cur.x > m) continue;
        //인접리스트 체크 
        for (int i = 0; i < adj[cur.v].size(); i++) {
            Info tmp = adj[cur.v][i];
            int acCost = tmp.x + cur.x;
            if ((cache[tmp.v][acCost] == -1 || cache[tmp.v][acCost] > cur.d + tmp.d)&& cur.x + tmp.x <= m) {
                cache[tmp.v][acCost] = cur.d + tmp.d;
                pq.push(Info(tmp.v, acCost, cur.d + tmp.d));
            }
        }
    }
    //도착지의 최소 비용을 구한다. 
    for (int i = 0; i <= m; i++) {
        if (cache[n][i] != -1 && ret>cache[n][i])
            ret = cache[n][i];
    }
    return ret;
}
int main() {
    scanf("%d", &t);
    while (t--) {
        //인접리스트 초기화 
        for (int i = 0; i <= 101; i++) adj[i].clear();
        int u, v, x, d;
        //input 
        scanf("%d %d %d", &n, &m, &k);
        for (int i = 0; i<k; i++) {
            scanf("%d %d %d %d", &u, &v, &x, &d);
            adj[u].push_back(Info(v, x, d));
        }
        int tmp = kcmTravel();
        printf(tmp == MAXV ? "Poor KCM\n" : "%d\n", tmp);
    }
}

'Algorithm > Problems' 카테고리의 다른 글

백준 - 10218 Maze  (1) 2016.06.20
백준 - 10217 KCM Travel  (0) 2016.06.20
백준 - 10216 Count Circle Groups  (0) 2016.06.20
백준 - 10215 Colored Bead Work  (0) 2016.06.20
백준 - 1992 쿼드트리  (1) 2016.05.25
백준 - 10215 Colored Bead Works  (0) 2016.05.25


[문제 링크]


도달 할 수 있는 진영을 그래프의 형태로 만들고 그래프의 갯수를 세면 된다.


서로 연결되지 않은 진영이 있기 때문에 모두 연결하다보면 다수의 그래프를 취한다.


이를 BFS든 DFS든 완전탐색을 해나가며 탐색한 그래프의 갯수를 세면 답을 구할 수 있다.


 

#include <cstdio>
#include <utility>
#include <vector>
#define createCamp(x,y,r) make_pair(make_pair(x,y),r);
using namespace std;
int t, n, x, y, r;
typedef pair<pair<int, int>, int> Camp;
vector<int> adj[3001];
Camp c[3001];

//인접 여부 
bool groupOk(Camp a, Camp b) {
    int distance = (a.first.first - b.first.first)*(a.first.first - b.first.first)
        + (a.first.second - b.first.second)*(a.first.second - b.first.second);
    return distance <= (a.second + b.second)*(a.second + b.second);
}
int countCirclegroup() {
    int ret = 0;
    bool visited[3001] = { false, };
    //인접리스트 초기화 
    for (int i = 0; i<n; i++) {
        for (int j = 0; j<n; j++) {
            if (groupOk(c[i], c[j])) {
                adj[i].push_back(j);
                adj[j].push_back(i);
            }
        }
    }
    //탐색 
    vector<int> v;
    for (int i = 0; i<n; i++) {
        if (visited[i]) continue;
        visited[i] = true;
        v.push_back(i);
        while (!v.empty()) {
            int cur = v.back(); v.pop_back();
            for (int j = 0; j<adj[cur].size(); j++) {
                int tmp = adj[cur][j];
                if (!visited[tmp]) {
                    visited[tmp] = true;
                    v.push_back(tmp);
                }
            }
        }
        ret++;
    }
    return ret;
}
int main() {
    scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 0; i<n; i++) {
            adj[i].clear();
            scanf("%d %d %d", &x, &y, &r);
            c[i] = createCamp(x, y, r);
        }
        printf("%d\n", countCirclegroup());
    }
}


'Algorithm > Problems' 카테고리의 다른 글

백준 - 10218 Maze  (1) 2016.06.20
백준 - 10217 KCM Travel  (0) 2016.06.20
백준 - 10216 Count Circle Groups  (0) 2016.06.20
백준 - 10215 Colored Bead Work  (0) 2016.06.20
백준 - 1992 쿼드트리  (1) 2016.05.25
백준 - 10215 Colored Bead Works  (0) 2016.05.25


[문제 링크]



처음엔 완전 탐색으로 풀었는데 이 문제는 비트마스킹 DP로 풀어야 한다.


여기서 주어진 칸의 갯수는 4X4로 16개이며, unsigned int형으로 비트마스킹 하면 각각 칸에 대해서 4가지(00,01,10,11) 상태를 표현이 가능하다.


이 각 경우에 대해 주어진 조건에 맞춰 확률을 모두 계산해 더해주면 된다.


(비트마스킹의 시프트로 해결해도 되고, 배열과 비트마스크를 바꿔가며 해결해도 된다. 밑의 코드는 두가지 경우를 모두 사용해보았다. 입맛에 맞게 사용하면 되지만 비트마스킹만을 사용하는게 더 빠른 속도로 통과된다.)



#include <iostream>
#include <cstdio>
#include <utility>
#include <map>
#include <vector>
//반복문 매크로
#define FOR(k,a,b) for(int k = a; k<b; k++)
#define M_FOR(k,a,b) for(int k = a; k >= b; k--)
#define D_FOR(a,b,c,d) for(int i = a; i<b; i++) for(int j = c; j<d; j++)
//구슬 비트 
#define W_BIT (8*i+2*j)
using namespace std;
//memoization 
map<unsigned int, double> cache[17];
typedef pair<unsigned int, double> dishStat;
int T, actCount;
unsigned int dish;
char act[17];

//bitmask -> vector 
vector<vector<char> > getStatVector(unsigned int dish) {
    vector< vector<char> > ret;
    ret.resize(4);
    D_FOR(0, 4, 0, 4) {
        if (dish&(1 << W_BIT)) ret[i].push_back('W');
        else if (dish&(1 << (W_BIT+1))) ret[i].push_back('G');
        else ret[i].push_back('E');
    }
    return ret;
}
  
double getProb(int curAct, unsigned int curDish) {
    //기저사례 1 : 모든 액션 실행.
    if(curAct == actCount) return curDish==dish? 1:0;
    //기저사례 2 : DP 
    if (cache[curAct].find(curDish) != cache[curAct].end())
        return cache[curAct][curDish];
    vector<vector<char> > ret = getStatVector(curDish);
        //구슬일 경우
        if (act[curAct] == 'W' || act[curAct] == 'G') {
            int centNum = 0, curBead = act[curAct] == 'W' ? 0 : 1;
            D_FOR(1, 3, 1, 3) if (ret[i][j] == 'E')  centNum++;
            //중앙 공간이 3개 비었을 경우, 대각선 100% 
            if (centNum == 3) {
                if (ret[1][1] != 'E') cache[curAct][curDish] += getProb(curAct + 1, curDish | (1 << (20 + curBead)));
                else if (ret[1][2] != 'E') cache[curAct][curDish] += getProb(curAct + 1, curDish | (1 << (18 + curBead)));
                else if (ret[2][1] != 'E') cache[curAct][curDish] += getProb(curAct + 1, curDish | (1 << (12 + curBead)));
                else if (ret[2][2] != 'E') cache[curAct][curDish] += getProb(curAct + 1, curDish | (1 << (10 + curBead)));
            }
            //중앙 공간이 1,2,4개 남았을경우, 1/centNum 
            else if (centNum <= 4 && centNum > 0) {
                D_FOR(1, 3, 1, 3) {
                    if (ret[i][j] == 'E')
                        cache[curAct][curDish] += getProb(curAct + 1, curDish | (1 << (W_BIT + curBead))) / centNum;
                }
            }
            //중앙이 꽉찼을 경우, 1/나머지공간 
            else {
                D_FOR(0, 4, 0, 4) if (ret[i][j] == 'E') centNum++;
                D_FOR(0, 4, 0, 4) {
                    if (ret[i][j] == 'E')
                        cache[curAct][curDish] += (getProb(curAct + 1, curDish | (1 << (W_BIT + curBead)))) / centNum;
                }
  
            }
        }
        //나머지 액션 
        else {
            unsigned int nextDish = curDish;
            if (act[curAct] == 'L') {
                FOR(k,0, 4) D_FOR(0, 4, 1, 4) { 
                    //직전 -1~-2비트가 00이면 오른쪽으로 2bit shift 
                    if (!(nextDish &(3 << (W_BIT - 2)))) {
                        nextDish = ((nextDish & (3 << (W_BIT))) >> 2) | (nextDish&~(3 << (W_BIT)));
                    }
                }
                cache[curAct][curDish] += getProb(curAct + 1, nextDish);
            }
            else if (act[curAct] == 'R') {
                FOR(k,0, 4) FOR(i,0,4) M_FOR(j,2,0) {
                    //이후 1~2비트가 00이면 왼쪽으로 2bit shift 
                    if (!(nextDish &(3 << (W_BIT + 2)))) {
                        nextDish = ((nextDish & (3 << (W_BIT))) << 2) | (nextDish&~(3 << (W_BIT)));
                    }
                }
                cache[curAct][curDish] += getProb(curAct + 1, nextDish);
            }
            else if (act[curAct] == 'T') {
                FOR(k,0, 4) D_FOR(1,4,0,4) {
                    //이전 -7~-8비트가 00이면 오른쪽으로 8bit shift
                    if (!(nextDish &(3 << (W_BIT - 8)))) {
                        nextDish = ((nextDish & (3 << (W_BIT))) >> 8) | (nextDish&~(3 << (W_BIT)));
                    }
                }
                cache[curAct][curDish] += getProb(curAct + 1, nextDish);
            }
              
            else if (act[curAct] == 'B') {
                FOR(k,0, 4) M_FOR(i,2,0) FOR(j,0,4){
                    //이후 7~8비트가 00이면 왼쪽으로 8bit shift 
                    if (!(nextDish &(3 << (W_BIT + 8)))) {
                        nextDish = ((nextDish & (3 << (W_BIT))) << 8) | (nextDish&~(3 << (W_BIT)));
                    }
                }
                cache[curAct][curDish] += getProb(curAct + 1, nextDish);
            }
        }    
   return cache[curAct][curDish];
}
 
int main() {
    cin >> T;
    while (T--) {
        dish = 0;
        cin >> actCount;
        FOR(k, 0, actCount) cin >> act[k];
        D_FOR(0, 4, 0, 4) {
            char tmp;
            cin >> tmp;
            if (tmp == 'W') dish |= 1 << W_BIT;
            if (tmp == 'G') dish |= 1 << (W_BIT+1);
        }
        cache[actCount][dish] = 1.0;
        printf("%.9lf\n", getProb(0, 0));
        FOR(k, 0, 17)cache[k].clear();
    }
}


'Algorithm > Problems' 카테고리의 다른 글

백준 - 10217 KCM Travel  (0) 2016.06.20
백준 - 10216 Count Circle Groups  (0) 2016.06.20
백준 - 10215 Colored Bead Work  (0) 2016.06.20
백준 - 1992 쿼드트리  (1) 2016.05.25
백준 - 10215 Colored Bead Works  (0) 2016.05.25
백준 - 2800 괄호 제거  (1) 2016.05.18

[문제 링크]



0과 1로되어있는 데이터를 쿼드트리로 압축하는 문제이다.

문제 해결 방법은 다양한데, 분할 정복으로 푼다는 점에선 모두 일치한다.


해결방법 중 하나는 그냥 전부 분할해서, 반환 받은 값이 모두 일치하면 하나로 출력하고, 다르면 나눠 출력하는 방법이 있고.

또 하나는 검사해 나가면서 하나라도 다른 값이 있으면 분할하는 방법이 있다.


나는 두 번째 방법으로 해결하였다. 밑은 이를 구현한 코드이다.



#include <cstdio>
int N, input[64][64];
void quadTree(int x, int y, int size) {
    int cur = input[y][x];
    bool flag = true;
    for (int i = y; (i< y + size) && flag; i++) 
        for (int j = x; (j<x + size) && flag; j++) 
            if (cur != input[i][j]) flag = false;
    //전부 일치했으면 초기 문자 출력 
    if (flag) printf("%d", cur);
    //아니면 4개로 분할한다. 
    else {
        printf("(");
        quadTree(x, y, size / 2);
        quadTree(x + size / 2, y, size / 2);
        quadTree(x, y + size / 2, size / 2);
        quadTree(x + size / 2, y + size / 2, size / 2);
        printf(")");
    }
}
int main() {
    scanf("%d", &N);
    for (int i = 0; i< N; i++) 
        for (int j = 0; j < N; j++) 
            scanf("%1d", &input[i][j]);
    quadTree(0, 0, N);
}


'Algorithm > Problems' 카테고리의 다른 글

백준 - 10216 Count Circle Groups  (0) 2016.06.20
백준 - 10215 Colored Bead Work  (0) 2016.06.20
백준 - 1992 쿼드트리  (1) 2016.05.25
백준 - 10215 Colored Bead Works  (0) 2016.05.25
백준 - 2800 괄호 제거  (1) 2016.05.18
백준 - 11583 인경호의 징검다리  (0) 2016.05.12
  1. 1466096058 2016.06.17 01:54

    잘 읽고 가여~

[문제 링크]



'문제 조건' 만큼은 명확하게 주어주기 때문에 어렵지 않다. 다만 이걸 코드를 옮기는게 너무 어려웠다.


난 이 문제를 비트마스크와 DP로 풀었다.


(왠만하면 끝까지 비트마스크로 풀고싶었는데 중간에 구슬 액션부분은 머리아파서 그냥 벡터로 변환했다)


이 문제에 구슬이 공간이 16개가 주어지는데, 빈공간(00), 흰색구슬(01), 초록색구술(10)처럼 공간마다 2비트씩 할당해서 

모든 접시의 상태를 unsigned int형으로 표현이 가능하다.


상태공간을 비트마스크로 표현한 뒤에는 문제에 주어진 조건을 따라 가면 된다.


(메모이제이션은 map으로 표현하였다. 표현 공간이 unsigned int형 최대 32비트이기 때문에 배열로는 표현이 어렵고 공간 낭비가 크다.)


#include <iostream> #include <cstdio> #include <utility> #include <map> #include <vector> //반복문 매크로 #define FOR(k,a,b) for(int k = a; k<b; k++) #define M_FOR(k,a,b) for(int k = a; k >= b; k--) #define D_FOR(a,b,c,d) for(int i = a; i<b; i++) for(int j = c; j<d; j++) //구슬 비트 #define W_BIT (8*i+2*j) using namespace std; //memoization map<unsigned int, double> cache[17]; typedef pair<unsigned int, double> dishStat; int T, actCount; unsigned int dish; char act[17]; //bitmask -> vector vector<vector<char> > getStatVector(unsigned int dish) { vector< vector<char> > ret; ret.resize(4); D_FOR(0, 4, 0, 4) { if (dish&(1 << W_BIT)) ret[i].push_back('W'); else if (dish&(1 << (W_BIT+1))) ret[i].push_back('G'); else ret[i].push_back('E'); } return ret; } double getProb(int curAct, unsigned int curDish) { //기저사례 1 : 모든 액션 실행. if(curAct == actCount) return curDish==dish? 1:0; //기저사례 2 : DP if (cache[curAct].find(curDish) != cache[curAct].end()) return cache[curAct][curDish]; vector<vector<char> > ret = getStatVector(curDish); //구슬일 경우 if (act[curAct] == 'W' || act[curAct] == 'G') { int centNum = 0, curBead = act[curAct] == 'W' ? 0 : 1; D_FOR(1, 3, 1, 3) if (ret[i][j] == 'E') centNum++; //중앙 공간이 3개 비었을 경우, 대각선 100% if (centNum == 3) { if (ret[1][1] != 'E') cache[curAct][curDish] += getProb(curAct + 1, curDish | (1 << (20 + curBead))); else if (ret[1][2] != 'E') cache[curAct][curDish] += getProb(curAct + 1, curDish | (1 << (18 + curBead))); else if (ret[2][1] != 'E') cache[curAct][curDish] += getProb(curAct + 1, curDish | (1 << (12 + curBead))); else if (ret[2][2] != 'E') cache[curAct][curDish] += getProb(curAct + 1, curDish | (1 << (10 + curBead))); } //중앙 공간이 1,2,4개 남았을경우, 1/centNum else if (centNum <= 4 && centNum > 0) { D_FOR(1, 3, 1, 3) { if (ret[i][j] == 'E') cache[curAct][curDish] += getProb(curAct + 1, curDish | (1 << (W_BIT + curBead))) / centNum; } } //중앙이 꽉찼을 경우, 1/나머지공간 else { D_FOR(0, 4, 0, 4) if (ret[i][j] == 'E') centNum++; D_FOR(0, 4, 0, 4) { if (ret[i][j] == 'E') cache[curAct][curDish] += (getProb(curAct + 1, curDish | (1 << (W_BIT + curBead)))) / centNum; } } } //나머지 액션 else { unsigned int nextDish = curDish; if (act[curAct] == 'L') { FOR(k,0, 4) D_FOR(0, 4, 1, 4) { //직전 -1~-2비트가 00이면 오른쪽으로 2bit shift if (!(nextDish &(3 << (W_BIT - 2)))) { nextDish = ((nextDish & (3 << (W_BIT))) >> 2) | (nextDish&~(3 << (W_BIT))); } } cache[curAct][curDish] += getProb(curAct + 1, nextDish); } else if (act[curAct] == 'R') { FOR(k,0, 4) FOR(i,0,4) M_FOR(j,2,0) { //이후 1~2비트가 00이면 왼쪽으로 2bit shift if (!(nextDish &(3 << (W_BIT + 2)))) { nextDish = ((nextDish & (3 << (W_BIT))) << 2) | (nextDish&~(3 << (W_BIT))); } } cache[curAct][curDish] += getProb(curAct + 1, nextDish); } else if (act[curAct] == 'T') { FOR(k,0, 4) D_FOR(1,4,0,4) { //이전 -7~-8비트가 00이면 왼쪽으로 8bit shift
if (!(nextDish &(3 << (W_BIT - 8)))) { nextDish = ((nextDish & (3 << (W_BIT))) >> 8) | (nextDish&~(3 << (W_BIT))); } } cache[curAct][curDish] += getProb(curAct + 1, nextDish); } else if (act[curAct] == 'B') { FOR(k,0, 4) M_FOR(i,2,0) FOR(j,0,4){ //이후 7~8비트가 00이면 왼쪽으로 8bit shift if (!(nextDish &(3 << (W_BIT + 8)))) { nextDish = ((nextDish & (3 << (W_BIT))) << 8) | (nextDish&~(3 << (W_BIT))); } } cache[curAct][curDish] += getProb(curAct + 1, nextDish); } } return cache[curAct][curDish]; } int main() { cin >> T; while (T--) { dish = 0; cin >> actCount; FOR(k, 0, actCount) cin >> act[k]; D_FOR(0, 4, 0, 4) { char tmp; cin >> tmp; if (tmp == 'W') dish |= 1 << W_BIT; if (tmp == 'G') dish |= 1 << (W_BIT+1); } cache[actCount][dish] = 1.0; printf("%.9lf\n", getProb(0, 0)); FOR(k, 0, 17)cache[k].clear(); } }


'Algorithm > Problems' 카테고리의 다른 글

백준 - 10215 Colored Bead Work  (0) 2016.06.20
백준 - 1992 쿼드트리  (1) 2016.05.25
백준 - 10215 Colored Bead Works  (0) 2016.05.25
백준 - 2800 괄호 제거  (1) 2016.05.18
백준 - 11583 인경호의 징검다리  (0) 2016.05.12
알고스팟 - WEEKLYCALENDAR  (0) 2016.05.09

[문제 링크]



짝 괄호를 지우는 모든 경우의 수를 구하는 문제이다.


처음엔 반복문으로 시도하고자 했으나 총 경우의 수인 2^(괄호 짝의 갯수)를 반복문으로 어떻게 표현할지 감이 오질않아서.


재귀로 해결하였다.


먼저 문자열을 한번 순회하며 스택을 이용해 짝괄호의 인덱스를 저장한다.


이렇게 저장한 인덱스들을 이용해서 문자열을 하나하나 완성해 나가면 된다.


문자열을 만들어 나가는데 가능한 경우의 수는 다음과 같다.


 가능한 경우의 수

 1. 현재 문자가 괄호일경우 : (1) 괄호를 지운다, (2) 괄호를 지우지 않는다.

 2. 현재 문자가 괄호가 아닐 경우 : 문자를 붙이고 문자열을 만들어간다.


여는 괄호가 나왔을 때, 짝 괄호에 괄호를 지웠다고 체크하고, 문자열을 이어 붙인다.

그와 대응되는 짝 괄호가 나타나면 그 괄호는 문자열에 포함시키지 않으면 된다.


완성된 문자열은 set에 저장하고, 모든 괄호를 지우지 않을 경우만 set에서 제거한 뒤에 출력하면 된다.


#include <iostream> #include <string> #include <set> #include <stack> using namespace std; string input; int matching[221], brkNum = 0; bool erasing[221]; set<string> retSet; string ret; void eraseBrackets(int cur){ //기저사례 : 문자열을 완성 if(cur == input.length()){ retSet.insert(ret); return; } if(input[cur] == '('){ //괄호를 지우는 경우 erasing[matching[cur]] = true; eraseBrackets(cur+1); erasing[matching[cur]] = false; } if(input[cur] ==')'&&erasing[cur]){ //짝괄호를 지운 경우 eraseBrackets(cur+1); } //괄호,짝괄호를 안지우거나 일반 문자열일 경우. else{ ret+=input[cur]; eraseBrackets(cur+1); ret.resize(ret.size()-1); } } //괄호 매칭 설정 void matchBrackets(string& input){ stack<int> st; for(int i = 0; i<input.length();i++){ if(input[i] == '(') st.push(i); else if(input[i] == ')'){ //매칭이 되는 괄호를 저장한다. matching[i] = st.top(); matching[st.top()] = i; st.pop(); brkNum++; } } } int main(){ cin>>input; matchBrackets(input); eraseBrackets(0); retSet.erase(input); set<string>::iterator it; for(it = retSet.begin(); it!=retSet.end(); it++) cout<<(*it)<<endl; }


'Algorithm > Problems' 카테고리의 다른 글

백준 - 1992 쿼드트리  (1) 2016.05.25
백준 - 10215 Colored Bead Works  (0) 2016.05.25
백준 - 2800 괄호 제거  (1) 2016.05.18
백준 - 11583 인경호의 징검다리  (0) 2016.05.12
알고스팟 - WEEKLYCALENDAR  (0) 2016.05.09
백준 - 10219 Meats On The Grill  (0) 2016.05.09
  1. 김건우 2016.10.21 23:21

    제가 도저희 뭐가 틀렸는지 몰라서 그러는데 여유 있으시면 어떤부분이 틀렸는지 알수 있을까요?

    import java.util.ArrayList;
    import java.util.Collections;
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Scanner;
    import java.util.Stack;
    import java.util.TreeSet;

    public class Main {
    TreeSet<String> set = new TreeSet<>();
    Stack<Integer> stack = new Stack<>();
    Queue<Integer> queue = new LinkedList<>();
    String line = "";
    ArrayList<Node> list = new ArrayList<>();
    int length;

    public void test() {
    Scanner scanner = new Scanner(System.in);
    line = scanner.nextLine();

    for (int i = 0; i < line.length(); i++) {
    if ('(' == line.charAt(i))
    stack.push(i);
    if (')' == line.charAt(i))
    queue.offer(i);
    }

    while (!stack.empty()) {
    int first = stack.pop();
    int second = queue.poll();
    list.add(new Node(first, second));
    }
    length = list.size();

    for (int i = 0; i < length; i++) {
    recur(i, line);
    }

    ArrayList<String> results = new ArrayList<String>(set);
    Collections.sort(results);

    for(String result : results)
    System.out.println(result);
    }

    void recur(int index, String sss){
    if(index >= length)
    return;

    for(int i = index ; i < length ; i++){
    StringBuffer sb = new StringBuffer(sss);
    Node tempNode = list.get(i);
    int x = tempNode.x;
    int y = tempNode.y;

    sb.insert(x, "#");
    sb.deleteCharAt(x + 1);
    sb.insert(y, "#");
    sb.deleteCharAt(y + 1);

    String temp = sb.toString();
    set.add(temp.replaceAll("#", "").trim());
    recur(i + 1, temp);
    }
    }

    public static void main(String[] args) {
    Main main = new Main();
    main.test();
    }

    class Node {
    int x, y;

    public Node(int x, int y) {
    this.x = x;
    this.y = y;
    }
    }

    }

[문제 링크]



Trailing zero의 최적을 구하는 문제다.

Trailing zero는 숫자에 들어있는 0의 갯수를 말하는데, 숫자에 0이 들어가려면 인수로 10을 가지고 있어야 한다.

따라서 소인수분해 시, 2와 5의 짝 만큼 Trailing zero가 추가된다.


이 문제는 소인수 2와 5를 가장 적게 가지는 경로를 찾는 문제이다.


모든 경로에 대해서 소인수 2와 5의 갯수를 전부 메모이제이션 한다.


앞서 설명한 대로 10이 만들어지려면 2와 5가 동시에 필요하므로, 2나 5중 가장 작은 값이 Trailing zero의 최소값이 된다.


지금 위치부터 K만큼 앞에 있는 징검다리를 비교하면서, 소인수 2와 5의 갯수가 최소가 되는 값을 찾아 각각 저장해나가면 구할 수 있다. 



단 주의해야 할 점은 dp를 할때 재귀(top-down)를 쓰면 시간초과가 발생한다.(연산 갯수가 총 10만개이다.)

이 문제는 반복문(bottom-up)으로풀어야 해결이 가능하다.


#include <cstdio> #include <cstring> #include <algorithm> #define MAX_VAL 987654321; int T, N, K, S[100001], cache[100001][2]; int getPf(int div,int input){ int ret = 0; while(input%div == 0){ ret++; input /=div; } return ret; } void stepping_stone(){ cache[0][0] = getPf(2,S[0]); cache[0][1] = getPf(5,S[0]); for(int cur = 1; cur<N; cur++){ cache[cur][0] = MAX_VAL; cache[cur][1] = MAX_VAL; for(int j=1;j<=K;j++){ int prev = cur-j; if(prev >= 0){ cache[cur][0] = std::min(cache[cur][0],cache[prev][0] + getPf(2,S[cur])); cache[cur][1] = std::min(cache[cur][1],cache[prev][1] + getPf(5,S[cur])); } } } printf("%d\n",std::min(cache[N-1][0],cache[N-1][1])); } int main(){ scanf("%d",&T); while(T--){ scanf("%d %d",&N,&K); for(int i = 0; i<N; i++) scanf("%d",&S[i]); stepping_stone(); } }


'Algorithm > Problems' 카테고리의 다른 글

백준 - 10215 Colored Bead Works  (0) 2016.05.25
백준 - 2800 괄호 제거  (1) 2016.05.18
백준 - 11583 인경호의 징검다리  (0) 2016.05.12
알고스팟 - WEEKLYCALENDAR  (0) 2016.05.09
백준 - 10219 Meats On The Grill  (0) 2016.05.09
더블릿 - 미로찾기/starship_maze  (0) 2016.05.09

+ Recent posts