화투의 개발 블로그

[문제 링크]

동전1에서 이어지는 문제다. 동전1은 경우의 갯수를 구하는 것이라면, 동전2 문제는 해당 경우에 사용되는 동전의 갯수를 구하는 것이다.

예를 들어 4원까지 동전 1,2만을 이용해서 갯수를 구하는 경우를 그려서 점화식을 구해보면

즉 DP(V) = min(DP(V), DV(V-COIN(i))+1) 의 점화식을 구할 수 있다.

다만 비교의 대상을 지정해야 하므로, 아무 값도 입력이 되어있지 않았을 때엔 최소 최적값 비교를 할 수 없기 때문에 DP(N) = DP(N- COIN(i)) + 1로 초기화 해주어야 한다.(초기화를 안해주면 DP(0)=0이므로 출력값은 0만 나온다..)

지금 동전 갯수를 구할 값이 초기화 된 값인지 아닌지, 이를 구하는데 필요한 이전 값이 초기화 되어있는지 조건을 걸어줘서 문제를 풀면 된다.

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

#include <cstdio>
#include <cstring>
#include <algoritm> 
using namespace std;
int n,coin[101],k,cache[10001]={0,};
int main(){
    memset(cache,-1,sizeof(cache));
    scanf("%d %d",&n,&k);
    for(int i=0;i<n;i++){
        scanf("%d",&coin[i]);
    }
    cache[0] = 0;
    //각 동전별로 해당 값을 구하는데 드는 최소 횟수를 구한다.     
    for(int i = 0; i<n; i++){
        for(int j = 0; j<=k;j++){
            if(j>=coin[i] && cache[j-coin[i]]!=-1){
                //아무 값도 입력이 안됬을 경우엔 동전의 갯수를 초기화해준다. 
                if(cache[j]==-1) 
                    cache[j] = cache[j-coin[i]]+1;
                //점화식, 값이 입력되어있으면 이전값과 비교해서 최소값을 넣어준다. 
                else
                    cache[j] = min(cache[j],cache[j-coin[i]]+1);
            }
        }
    }   
    printf("%d",cache[k]);
}

[문제 링크]

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에 대한 학습은 아직 더 필요한거같다.

문제 링크

BFS 문제다. 값의 범위만 조심하면 어려울 것 없는 문제였다.

다만 지금까지 풀었던 BFS는 방문을 체크하는 변수와 현재 탐색 레벨의 변수를 따로 두고 풀었는데, 이번에는 이전 문제와는 다르게,방문을 체크하는 변수 안에 현재 탐색 레벨을 담았다. 다만 그 체크를 위해 맨 처음 값이 1로 시작해야 했기에, 마지막 결과 값에서 1을 빼서 반환했다.

밑은 내가 풀이한 코드이다. 

#include <cstdio>
#include <queue>
using namespace std;
//기존에 풀었던 BFS문제와는 다르게, visited 배열에 현재 레벨도 저장하였다. 
int n, k, visited[100001]={0,};
queue<int> q;
int bfs(){
    //큐에 수빈의 위치를 넣고, 방문을 체크하는 배열에 1을 넣어준다. 
    q.push(n); visited[n] = 1;
    //bfs 시작 
    while(!q.empty()){
        //큐를 꺼내고, 수빈이가 동생의 위치에 도달했는지 확인한다. 
        int p = q.front(); q.pop();
        if(p==k) return visited[p]-1;
        
        //수빈이 현재 위치 -1이 0보다 크거나 같고, 방문한 적이 없을경우. 현재 값에서 레벨을 1증가시켜 큐에 넣어준다. 
        if(p-1>=0&&visited[p-1]==0){
            visited[p-1] = visited[p]+1;
            q.push(p-1);
        }
        //수빈이 현재 위치의 +1이 100,000보다 작거나 같고, 방문한 적이 없을경우.
        if(p+1<=100000&&visited[p+1]==0){
            visited[p+1] = visited[p]+1;
            q.push(p+1);
        }
        //수빈이 현재 위치의 2배가 0보다 크거나 같고, 방문한 적이 없을경우.
        if(2*p<=100000&&visited[2*p]==0){
            visited[2*p] = visited[p]+1;
            q.push(2*p);
        }
    }
}
int main(){
    scanf("%d %d",&n,&k);
    printf("%d",bfs());
}

문제 링크

나는 BFS로 푼 문제이다. 시작 점이 꼭 1번 건물이 아닐 수도 있으므로 모든 건물의 정보를 입력 받는 과정에, 그 이전 단계가 있는 건물들은 시작 건물이 아니라 단정하고 시작 건물들이 가능한 건물들은 처음에 큐에 미리 넣어주고 BFS를 진행하였다.

이 문제에 함정이 있는 게, 문제는 최소 시간을 구하라고 하는데 따지고 보면 그냥 그 단계까지 누적 최고 건설 시간들만 구해주면 된다. 왜냐하면 특정 단계 건물을 짓기 위해서는 선행 건물들을 모두 지어야 하는데, 선행 건물들 중에 건설 시간이 짧은 것을 아무리 먼저 지어도 건설 시간이 긴 건물이 지어지기 전까지는 그 특정 단계의 건물을 지을 수 없기 때문이다. 

이 로직 대로 코드를 짰는데, 처음에 문제를 풀 때 시간 초과가 났었다. 뭐가 문제인가 고민을 해봤더니, 초기에는 build배열에서 첫 번째 인덱스는 현재 건물, 두 번째 인덱스는 다른 건물을 인덱스로 두고, 그 배열 값이 참이면 경로가 존재한다고 하고 풀이를 진행했었다.

이 과정에서 매 루프마다 그때의 건물 배열을 1부터, n까지 전부 다 경로 검사를 진행해야 하니 시간 초과가 일어난 것이다. 그래서 일일이 해당 인덱스에 저장하는 방법을 버리고 해당 건물이 가진 경로의 개수를 path 배열 에다가 저장하고, 배열의 1 인덱스부터 다음 경로들을 저장하는 방법을 택하니 시간 초과에서 벗어났다. 

밑은 위의 과정대로 작성한 코드이다.

#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm> 
using namespace std;
//각 건물의 인덱스 0번에 건설 시간을 저장한다. 
int t,build[1001][1001],isFirst[1001]={0,},value[1001],path[1001];
int x,y,n,k,w;
queue<int> q; 
 
int bfs(){  
    int ret = 0;
    //시작점이 가능한 것들을 전부 큐에 넣는다. 
    for(int i=1;i<=n;i++){
        if(isFirst[i]==0){
            q.push(i);
            //초기 빌드의 누적 비용을 건설 비용으로 초기화한다. 
            value[i] = build[i][0];
        }
    }   
    //BFS를 진행한다. 
    while(!q.empty()){
        //큐에서 인덱스를 하나씩 꺼내서, 다음 경로에서 가능한 것을 찾는다.
         int p = q.front(); q.pop();
        //원하는 건물에 도달하면, 최대 값을 넣어준다.
         if(p==w) ret = max(ret,value[p]);
         else{
         for(int i=1;i<=path[p];i++){
            if(build[p][i]>=1){
                int a = build[p][i];
                // 다음 빌드를 짓는 데에 드는 최대 비용을 구한다. 최대 비용이 안되면 enqueue 하지 않는다.  
                if(value[a] < value[p]+build[a][0]){
                    value[a] =value[p] + build[a][0];
                    q.push(a);
                 }
             }
         }
        }
    }
    return ret;
}
int main(){
    scanf("%d",&t);
    while(t--){
        //초기화// 
        for(int i=0; i<q.size();i++) q.pop();
        memset(build,0,sizeof(build));
        memset(value,0,sizeof(value));
        memset(isFirst,0,sizeof(isFirst));
        memset(length,0,sizeof(length));
        
        //건물의 갯수와 건설 규칙 순서 
        scanf("%d %d",&n,&k);
        //각 건물 0번 인덱스에 건물의 건설 시간을 저장한다. 
        for(int i=1;i<=n;i++)
            scanf("%d",&build[i][0]);
       //각 건물의 경로 초기화           
        for(int i=0;i<k;i++){
            scanf("%d %d",&x,&y);
            int a = ++path[x];
            //해당 경로가 있음을 표시하기위해  1을 저장한다. 
            build[x][a] = y;
            //또한 해당 경로가 시작점이 가능한지 아닌지도 체크를 해야된다.
            isFirst[y] = 1; 
        } 
        //목표 건물 
        scanf("%d",&w);
        printf("%d\n",bfs());       
    } 
}

변수가 쓸대 없이 많아진 것 같아 나중에 시간을 내서 리팩토링을 해야겠단 생각이 든다.

정답률이 15%라 엄청 긴장하고 풀었는데 그 정도 까지의 문제는 아니었던 것 같다.

문제 링크

#include <cstdio>
#include <queue>
using namespace std;
//맵의 크기 t, 맵 변수 a, 댐 시간 변수 k, 홍수 넘침 여부 변수 flood 
int t,a[101][101],k,flood[101][101]={0,},x,y;
//해당 좌표 정보를 저장하는 구조체 
typedef struct{
    int x,y,count;  
}Point;
//bfs를 위한 큐 
queue<Point> q;
//해당 위치의 상대 좌표. 물의 확산 비교를 위해 
int relPos[4][2]= {{1,0},{-1,0},{0,1,},{0,-1}};
int bfs(){
    int ret=0;
    // 초기 좌표의 정보 값을 저장한 구조체를 만들고, 큐에 넣는다. 
    Point p = {x,y,0}; flood[y][x] = 1;
    q.push(p);  
    // bfs 시작 
    while(!q.empty()){
        p = q.front(); q.pop();
        for(int i=0; i<4;i++){
            int px = p.x + relPos[i][0];
            int py = p.y + relPos[i][1];
            //보드판의 범위 안에 있고, 방문한 적이 없고, 건물이 아니어야 한다. 
            if(px>0&&py>0 && px<t+1&&py<t+1 && flood[py][px]==0 && a[py][px]==0){
                //해당 거리에 홍수가 났음을 체크 
                flood[py][px] = 1;
                Point np = {px,py,p.count+1};
                //만약 이 위치에서 댐을 막았으면 ret의 카운트를 증가. 
                if(p.count+1==k) ret++;
                q.push(np);
            }
        }
    }   
    return ret;
}
int main(){
    scanf("%d",&t);
    // 맵 초기화 
    for(int i =1; i<=t;i++){
        for(int j=1;j<=t;j++){
            scanf("%d",&a[i][j]);
        }
    }
    scanf("%d %d",&x,&y);
    scanf("%d",&k);
    int ret = bfs();
    printf(ret==0?"OH, MY GOD":"%d",ret);
}

#include <cstdio>
//맵의 크기 t, 맵변수 a, 댐 시간 변수 k, 홍수 넘침여부 변수 flood 
int t,a[101][101],k,flood[101][101]={0,},x,y;
//해당 좌표 정보를 저장하는 구조체 
typedef struct{
    int x,y,count;  
}Point;

//bfs를 위한 큐 
Point q[10000];
int front=0,rear=0;
void enqueue(Point p){
    q[rear++] = p;
}
Point dequeue(){
    return q[front++];
}
bool isEmpty(){
    return front==rear;
}

//해당 위치의 상대좌표. 물의 확산 비교를 위해 
int relPos[4][2]= {{1,0},{-1,0},{0,1,},{0,-1}};
int bfs(){
    int ret=0;
    // 초기 좌표의 정보값을 저장한 구조체를 만들고, 큐에 넣는다. 
    Point p = {x,y,0}; flood[y][x] = 1;
    enqueue(p); 
    // bfs 시작 
    while(!isEmpty()){
        p = dequeue();
        for(int i=0; i<4;i++){
            int px = p.x + relPos[i][0];
            int py = p.y + relPos[i][1];
            //보드판의 범위안에 있고, 방문한적이 없고, 건물이 아니어야한다. 
            if(px>0&&py>0 && px<t+1&&py<t+1 && flood[py][px]==0 && a[py][px]==0){
                //해당 거리에 홍수가 났음을 체크 
                flood[py][px] = 1;
                Point np = {px,py,p.count+1};
                //만약 이 위치에서 댐을 막았으면 ret의 카운트를 증가. 
                if(p.count+1==k) ret++;
                enqueue(np);
            }
        }
    }   
    return ret;
}
int main(){
    scanf("%d",&t);
    // 맵 초기화 
    for(int i =1; i<=t;i++){
        for(int j=1;j<=t;j++){
            scanf("%d",&a[i][j]);
        }
    }
    scanf("%d %d",&x,&y);
    scanf("%d",&k);
    int ret = bfs();
    printf(ret==0?"OH, MY GOD":"%d",ret);
}