[문제 링크]


발상적으로 좀 어려웠던 문제다. 최단거리를 구하는 것이기 때문에 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' 카테고리의 다른 글

백준 - 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를 이용해서 풀어야한다.


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





#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
백준 - 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
백준 - 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
백준 - 1992 쿼드트리  (1) 2016.05.25
백준 - 10215 Colored Bead Works  (0) 2016.05.25
백준 - 2800 괄호 제거  (1) 2016.05.18


[문제 링크]



LCS2는 다음 포스트에 있는 내용과 같다.


http://hsp1116.tistory.com/37



#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
vector<char> output;
int cache[1001][1001];
char input[1001],compare[1000];
int LCS(int m,int n){
    memset(cache,0,sizeof(cache));
    for(int i=1;i<=m;i++){
        for(int j=1; j<=n;j++){
            if(compare[i-1] == input[j-1]){
                cache[i][j] = cache[i-1][j-1] +1;
                }
            else{
                cache[i][j] = std::max(cache[i-1][j], cache[i][j-1]);
            }
        }
    }
    return cache[m][n];
}
void backTracking(int m, int n){
    if(m==0 || n ==0) return;
    if(cache[m][n] > cache[m-1][n-1] && cache[m][n] > cache[m][n-1] && cache[m][n] > cache[m-1][n]){
        output.push_back(input[n-1]);
        backTracking(m-1, n-1);
    }else if(cache[m][n] > cache[m-1][n] && cache[m][n] == cache[m][n-1]){
        backTracking(m, n-1);
    }else{
          backTracking(m-1, n);
    }
}
int main(){
    scanf("%s%s",input,compare);
    int m = strlen(compare), n = strlen(input);
    printf("%d\n",LCS(m,n));
    backTracking(m,n);
    for(int i=output.size()-1;i>=0;i--)
        printf("%c",output[i]);
}


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

백준 - 1238 파티  (0) 2016.04.22
백준 - 1753 최단경로  (1) 2016.04.22
백준 - 9251 LCS  (0) 2016.04.17
알고스팟 - KOOGLE  (0) 2016.04.14
백준 - 1725, 6549 히스토그램 / 알고스팟 - FENCE  (0) 2016.03.28


[문제 링크]



LCS는 다음 포스트에 있는 내용과 같다.


http://hsp1116.tistory.com/37




#include <cstdio>
#include <algorithm>
#include <cstring>
int cache[1001][1001];
char input[1001],compare[1000];
int LCS(){
    int n = strlen(compare), m = strlen(input);
    memset(cache,0,sizeof(cache));
    for(int i=1;i<=n;i++){
        for(int j=1; j<=m;j++){
            if(compare[i-1] == input[j-1]){
                cache[i][j] = cache[i-1][j-1] +1;
                }
            else{
                cache[i][j] = std::max(cache[i-1][j], cache[i][j-1]);
            }
        }
    }
    return cache[n][m];
}
int main(){
    scanf("%s %s",input,compare);
    printf("%d\n",LCS());
}

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

백준 - 1753 최단경로  (1) 2016.04.22
백준 - 9252 LCS 2  (0) 2016.04.17
알고스팟 - KOOGLE  (0) 2016.04.14
백준 - 1725, 6549 히스토그램 / 알고스팟 - FENCE  (0) 2016.03.28
백준 - 2493 탑  (1) 2016.03.28


[문제 링크]




DP문제이다. 어려운 문제는 아니고, 다음으로 선택할 수 있는 경로의 경우만 알면 쉽게 풀리는 문제인 것 같다.

자신을 기준으로 상하좌우는 접근할 수 없기 때문에, 대각선에 위치한 스티커나, 대각선에서 오른쪽으로 한칸 옆에 있는 스티커를 다음 경로로 선택하면 된다.

이렇게 모든 점수들을 더한 값 중 최대값을 구하면 되었다.

밑은 이를 구현한 코드이다.



#include <cstdio> #include <cstring> #include <algorithm> int t,n,arr[2][100000],cache[2][100000]; int relPos[4][2] = {{1,1},{1,-1},{2,-1},{2,1}}; int dp(int y, int x){ //기저사례 : y 끝에 도달했을 때 if(x==n-1) return arr[y][x]; int& ret = cache[y][x]; if(ret!=-1) return ret; ret = 0; for(int i=0;i<4;i++){ int px = x + relPos[i][0]; int py = y + relPos[i][1]; //스티커 범위를 초과하지 않으면 if(px<n&&px>=0&&py<2&&py>=0){ //최대값 구하기, 기존 ret와, 이 값+ 현재 좌표값 ret = std::max(ret,dp(py,px)+arr[y][x]); } } return ret; } int main(){ scanf("%d",&t); while(t--){ memset(cache,-1,sizeof(cache)); scanf("%d",&n); for(int y=0;y<2;y++){ for(int x=0;x<n;x++){ scanf("%d",&arr[y][x]); } } //(0,0)으로 시작할 때랑, (1,0)으로 시작할때 중 최댓값을 구하여 출력한다. printf("%d\n",std::max(dp(0,0),dp(1,0))); } }


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

백준 - 10799 쇠막대기  (2) 2016.03.28
백준 - 1520 내리막 길  (0) 2016.03.15
백준 - 1654 랜선자르기  (0) 2016.03.15
백준 - 1912 연속합  (0) 2016.03.07
백준 - 2294 동전 2  (0) 2016.03.07

[문제 링크]


DP문제이다. 정말 내 머리가 DP에서 틀에 박혔다는 생각이 든 문제였다. 원래는 DP[V] = DP[V] + DP[V-COIN[I]]와 같은 점화식으로 문제를 풀어나갔는데.


이 식의 문제점은 다른 순서지만, 같은 종류의 동전을 사용한 것도 모두 다른 값으로 취급해 카운트를 하는 것 같았다. 그래서 그냥 단순하게 위와 같은 방식으로 문제를 풀 경우 출력값이 엄청 크게 나왔다..


그래서 내가 원래 풀었던 것과 반복을 다른 방법으로 진행해야 하는데, 그것은 각 값 별로 방법의 수를 구하는 것이 아니라, 동전 별로 각 값에 대한 방법의 수를 구하는 것이다.



밑의 코드는 원래 방식대로, 값을 기준으로 재귀를 진행한 코드이다. 1,1,1,2와 2,1,1,1과 같은 같은 종류지만 다른 순서로 인것들도 모두 다른 경우로 취급해 엄청 큰 값이 나온다. 

각 동전의 경우에 따른 경우의 갯수를 cache의 2차원 배열로 추가하면 문제 해결이 가능하고, 실제로도 이렇게 답을 구했었지만 이 경우 문제의 메모리 제한 4mb를 초과해버린다.

#include <cstdio> #include <cstring> int n,coin[101],k,cache[10001]; //사용한 동전 갯수가 같으면 같은 경우이다. int dp(int value){ //기저사례 num == k일때 if(value==0) return 1; //기저사례 2, n을 넘어설때, 0 if(value<0) return 0; int& ret = cache[value]; if(ret!=-1) return ret; ret = 0; //점화식 for(int i=0;i<n;i++){ if(value-coin[i] >= 0) ret = ret + dp(value-coin[i]); } return ret; } int main(){ memset(cache,-1,sizeof(cache)); scanf("%d %d",&n,&k); for(int i=0;i<n;i++){ scanf("%d",&coin[i]); } printf("%d",dp(k)); }


밑은 각 동전별로 경우의 수를 구한 코드이다.


#include <cstdio>
int n,coin[101],k,cache[10001]={0,};
int main(){
    scanf("%d %d",&n,&k);
    for(int i=0;i<n;i++){
        scanf("%d",&coin[i]);
    }
    cache[0] = 1;
    
    //각 동전별로 값마다 경우의 수를 구한다.     
    for(int i = 0; i<n; i++){
        for(int j = 0; j<=k;j++){
            if(j>=coin[i])
                cache[j] += cache[j-coin[i]];
        }
    }   
    printf("%d",cache[k]);
}

코드가 훨씬 간결하고 직관적이다. DP에 대한 학습은 아직 더 필요한거같다.

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

백준 - 1912 연속합  (0) 2016.03.07
백준 - 2294 동전 2  (0) 2016.03.07
백준 - 1697 숨바꼭질  (1) 2016.02.28
백준 - 1005 ACM Craft  (0) 2016.02.27
더블릿 - 댐  (0) 2016.02.26

+ Recent posts