개발자 김수진

[문제]

www.acmicpc.net/problem/1937

[풀이]

판다는 대나무를 다 먹어 치우면 상,하,좌,우 중 하나로 이동할 수 있다.

단, 이전에 먹었던 대나무보다 많은 대나무가 존재하는 곳으로만 이동할 수 있다.

판다가 최대한 살 수 있는 일수를 구하면 된다.

DP 배열에 해당 위치에서 이동할 수 있는 최대 거리를 저장했다.

따라서 DFS 함수를 통해 미리 DP 배열의 값을 구해놨다면 DP 배열에 저장된 값을 return  하면 된다.

아직 DP 배열에 0이 저장되어 있다면 다시 DFS 함수를 호출하여 해당 좌표에서 가장 멀리 갈 수 있는 거리를 구하면 된다.

아래 코드와 같이 DFS 함수를 통해 (1,1) ~ (N,N)까지 해당 좌표에서 가장 멀리 갈 수 있는 거리를 구하여 최댓값을 구하면 된다. 

[코드]

시간 : 128ms

#include <iostream>
#include <algorithm>
#define MAX 501

using namespace std;

int DP[MAX][MAX]={0,};
int map[MAX][MAX]={0,};
int dx[4] ={-1,1,0,0};
int dy[4] ={0,0,-1,1};
int res=0;
int N;


int DFS(int x, int y)
{
    if(DP[x][y])   return DP[x][y];
    DP[x][y] =1;
    
    for(int i=0;i<4;i++){
        
        int nx= x+dx[i];
        int ny= y+dy[i];
        
        if(nx < 0 || ny <0 || nx >= N || ny >= N)   continue;
        if(map[nx][ny] <= map[x][y])    continue;
        
        DP[x][y] = max(DP[x][y] , DFS(nx,ny)+1);
        

    }
    return DP[x][y];
}


int main(void)
{
    
    cin >> N;
    
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            cin >> map[i][j];
        }
    }
    
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            res = max(res , DFS(i,j));
        }
    }
    cout << res;
    
    return 0;
    
}

[문제]

www.acmicpc.net/problem/13459

[풀이]

보드의 정보가 입력으로 주어지고 , 10번 이하의 움직임으로 빨간공이 빠져나갈 수 있으면 1을 출력하고 없으면 0을 출력한다.

먼저 입력으로 보드의 크기와 상태를 입력받았다.

장애물인 있는 좌표는 map에 -1을 저장하고, 구멍이 존재하는 좌표는 1을 저장했다.

DFS를 사용해서 풀었다. DFS 함수에서 인자 값으로 몇 번 움직였는지를 나타내는 cnt 를 넘겨주었다.

문제 조건에 의해 cnt가 10보다 크거나 같다면  return false를 하여 DFS 함수를 끝냈다.

DFS 함수에서는 for문을 통해 상,하,좌,우로 움직일 수 있도록 하였다. 

solve 함수는 공을 움직이는 함수로 인자로 전달받은 dir 방향으로 움직이도록  하였다.

문제의 조건들을 잘 신경써야 될 것 같다.

Ex )

1. 빨간공과 파란공 모두 탈출하면 실패

2. 파란공이 먼저 탈출하면 실패 

3. 보드의 한 칸에는 하나의 공만 존재할 수 있음

[코드]

시간 : 24ms

#include <iostream>
#define MAX 11

using namespace std;


struct pos{
    int x,y;
};

pos R,B;

int N,M;
int map[MAX][MAX]={0,};

int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};

int solve(int dir)
{
    int rx = R.x;
    int ry = R.y;
    
    while(1){
        if(map[rx][ry] != 0)    break;
        rx += dx[dir];
        ry += dy[dir];
    }
    
    int bx = B.x;
    int by = B.y;

    while(1){
        if(map[bx][by] != 0)    break;
        bx += dx[dir];
        by += dy[dir];
    }
    
    if(map[rx][ry] == 1 && map[bx][by] != 1)    return 1;
    else if(map[bx][by] == 1)   return -1;
    
    rx-= dx[dir];
    ry-= dy[dir];
    
    bx -= dx[dir];
    by -= dy[dir];
    
    if(rx == bx && ry == by){
        if(dir == 0 ) R.x > B.x ? rx++ : bx++ ;
        else if (dir == 1) R.y > B.y ? by-- : ry--;
        else if(dir == 2)   R.x > B.x ? bx-- : rx--;
        else if(dir == 3)   R.y > B.y ? ry++ : by++;

    }
    
    R={rx,ry};
    B={bx,by};
    
    return 0;
}

int DFS(int cnt)
{
    if(cnt >= 10 )  return 0;
    
    for(int i=0;i<4;i++){
        
        pos tmp_R = R;
        pos tmp_B = B;
        
        int res = solve(i);
        
        if(res==1 ) return 1;
        else if(res == -1)  continue;
        
        if(DFS(cnt+1) == 1)  return 1;
        
        R = tmp_R;
        B = tmp_B;
    }
    return -1;
}

int main(void)
{
    cin >> N >> M ;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            char ch;
            cin >> ch;
            
            if (ch == '#')  map[i][j]=-1;
            else if(ch == 'O')  map[i][j] = 1;
            else if(ch == 'R')  {
                R.x = i;
                R.y = j;
            }
            else if(ch == 'B')  {
                B.x = i;
                B.y = j;
            }
        }
    }
    
    if(DFS(0) == 1) cout << "1";
    else cout << "0";
    
    return 0;
    
}

[문제]

www.acmicpc.net/problem/1744

[풀이]

길이가 N인 수열이 주어지고 수열의 합의 최댓값을 구하는 문제.

숫자끼리 서로 묶어서 곱하여 더할 수 있다.

단 모든 수는  한번만 묶거나, 묶지 않아야한다.

큰 수 끼리 곱할수록 값이 더 커지므로 처음에는 vector만 사용해서 풀었다.

음수, 양수를 따로 벡터에 저장한 뒤 정렬하여 풀었는데 틀렸습니다가 나오길래 priority_queue를 사용해서 풀었다.

priority_queue는 기본적으로 오름차순 정렬을 하고 , greater를 붙일 경우 내림차순으로 정렬한다.

음수, 양수를 각각 negative, positive 큐에 저장하고 두개씩 빼서 서로 곱하여 더해준다. 

따라서 queue의 크기가 홀수이면 안되므로 , 홀수일 경우 1을 push하여 짝수 개로 맞춰준다. 

음수에 0을 곱할 경우 더 큰 값을 얻을 수 있다. 

따라서 0이 존재한다면 1 대신에 0을 negative에 push 하였다.

[코드]

시간 : 0ms

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

#define MAX 10001
using namespace std;



int main(void)
{
    int N;
    int sum=0;
    int cnt =0;
    
    priority_queue <int,vector<int>,greater<int>> positive;
    priority_queue <int> negative;


    cin >> N;
    for(int i=0;i<N;i++){
        int num;
        cin >> num;
        
        if(num == 1)    sum+=1;
        else if(num == 0)   cnt++;
        else if (num > 0 )  positive.push(num);
        else negative.push(num);
    }
    
    if(positive.size()%2 != 0)  positive.push(1);
    if(negative.size()%2 != 0)  {
        if(cnt != 0)    negative.push(0);
        else    negative.push(1);
    }
    
    while(!positive.empty()){
        int num1 = positive.top();
        positive.pop();
        int num2 = positive.top();
        positive.pop();
        
        sum += num1*num2;
    }
    while(!negative.empty()){
        int num1 = negative.top();
        negative.pop();
        int num2 = negative.top();
        negative.pop();
        
        sum += num1*num2;
    }
    
    cout << sum;
    return 0;
}

[문제]

www.acmicpc.net/problem/2638

[풀이]

모눈종이 위에 치즈가 존재하고 , 치즈가 공기와 접촉하는 변이 2개 이상일 경우 한시간 뒤에 녹게된다.

(치즈 내부에 있는 치즈 공간은 공기와 접촉하지 않는 것으로 가정한다. )

이 때 치즈가 모두 녹는데 걸리는 시간을 구하는 문제이다.

BFS를 사용해 외부 공간을 queue에 저장하였다.

queue에서 하나씩 pop 할 때마다 해당 좌표의 상하좌우 중에서 치즈가 존재하는지 확인한다.

치즈가 존재한다면 , 치즈가 존재하는 좌표의 visited 배열 값을 +1 해준다.

위와 같이 반복하여 while문을 나왔을 때, visited 배열의 값이 2 이상인 경우 접촉하는 변이 2개 이상인 경우이므로 

해당 좌표 map 배열의 값을 0으로 update 해준다. 

[코드]

시간 : 8ms

#include <iostream>
#include <queue>
#define MAX 101

using namespace std;

struct pos{
    int x,y;
};

int map[MAX][MAX]={0,};
int N,M;

int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};

bool BFS()
{
    bool flag= false;
    
    int visited[MAX][MAX]={0,};
    
    queue <pos> q;
    q.push({0,0});
    visited[0][0]=-1;
    
    while(!q.empty()){
        
        int x = q.front().x;
        int y = q.front().y;
        q.pop();
        
        for(int i=0;i<4;i++){
            int nx = x+dx[i];
            int ny = y+dy[i];
            
            if(nx<0 || ny < 0 || nx >= N || ny >= M)    continue;
            if(map[nx][ny] == 1){
                visited[nx][ny]++;
                continue;
            }
            if(visited[nx][ny]!=0)  continue;
            
            q.push({nx,ny});
            visited[nx][ny] = -1;
            
        }
    }
    
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++){
            if(visited[i][j] >= 2){
                map[i][j] = 0;
                flag = true;
            }
        }
    }
    
    return flag;
}

int main(void)
{
    cin >> N >> M;
    for(int i=0;i<N;i++){
        for(int j=0;j<M;j++)    cin >> map[i][j];
    }
    
    int cnt =0;
    
    while(1){
        if(BFS()==false)    break;
        cnt++;
    }
    
    cout << cnt;
    return 0;
    
}

[문제]

www.acmicpc.net/problem/5014

[풀이]

S층에서  G층으로 가기 위해 눌러야 하는 버튼 수의 최솟값을 구하는 문제이다. 

BFS를 사용해 풀 수 있었다.

visited 배열을 사용해 이미 방문한 층이라면 넘어가고 

처음 방문한 층이라면 이전 층의 버튼 수 +1 을 저장한다.

이렇게 while문을 진행하다가 G 층을 만나면 버튼 수를 출력하고 BFS 함수를 return 한다.

 queue가 empty가 되어 while문이 끝나는 경우 엘레베이터로 이동할 수 없는 경우이므로 

"use the stairs"를 출력하고 BFS 함수를 return 한다.

[코드]

시간 : 8ms

#include <iostream>
#include <queue>
#define MAX 1000001

using namespace std;

/* S -> G , 못가면 use the stair 출력 */
int F,S,G,U,D;
int visited[MAX]={0,};
int dpos[2] = {0,};


void BFS(){

    queue <int> q;
    q.push(S);
    visited[S]=1;
    while(!q.empty()){
        
        int pos = q.front();
        q.pop();
        
        if(pos == G){
            cout << visited[pos]-1;
            return;
        }
        
        for(int i=0;i<2;i++){
            int npos = pos + dpos[i];
            
            if(npos < 1 || npos > F ||visited[npos]!=0)    continue;
            
            visited[npos] = visited[pos]+1;
            q.push(npos);
        }
    }
    
    cout << "use the stairs";
    return;

}

int main(void)
{
    cin >>F >> S >> G >> U >> D;
    dpos[0] = U;
    dpos[1] = -1*D;
    BFS();
    return 0;
}

[문제]

www.acmicpc.net/problem/11559

[풀이]

상하좌우 중에서 같은 색깔의 뿌요가 4개 이상 존재한다면 뿌요는 터지게 된다.
뿌요들이 터지고 나서 위에 다른 뿌요들이 있다면 중력의 영향을 받아 차례대로 아래로 떨어지게 된다.

먼저 BFS 함수에서 상하좌우에 같은 색깔의 뿌요가 존재하는지 확인한다.

존재한다면 vector에 push 하여서 queue가 empty가 될 때까지 진행한다. 

while문을 빠져나와서 벡터의 사이즈가 4보다 크거나 같다면 뿌요가 터질 수 있는 조건을 성립하므로

뿌요가 존재하는 위치의 값을 0으로 update 해준다.

이와 같은 방식으로 모든 좌표에 대해서 확인을 한다. 

뿌요가 하나도 터지지 않았다면  BFS 함수가 return false  하므로 main 함수의  while문도 끝나게 된다.

return true를 했다면 뿌요가 터졌기 때문에 터진 뿌요 위에 다른 뿌요가 존재하면 아래로 내려올 수 있도록 하는 solve 함수를 호출한다.

solve 함수는 열을 기준으로 아래서부터 뿌요가 존재한다면 벡터에 하나씩 담아준다.

그리고 한번에 아래서부터 채워준다.

[코드]

시간 : 0ms

#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;

struct pos{
    int x,y;
};

int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int map[12][6]={0,};

void solve()
{
    vector <int> v;

    for(int i=0;i<6;i++)
    {
        for(int j=11;j>=0;j--){
            if(map[j][i] != 0 ) v.push_back(map[j][i]);
            map[j][i]=0;
        }
        
        int idx = 11;
        for(int j=0;j<v.size();j++) map[idx--][i]=v[j];
        v.clear();
    }
}

bool BFS()
{
    bool check = false;
    vector <pos> v;

    int visited[12][6]={0,};
    queue <pos> q;
    int num =0;
    
    for(int i=0;i<12;i++){
        for(int j=0;j<6;j++){
            
            if(map[i][j] != 0 && visited[i][j] == 0 ){
                num=1;
                q.push({i,j});
                visited[i][j]=1;
                v.push_back({i,j});
            }
            
            while(!q.empty()){
                
                int x = q.front().x;
                int y = q.front().y;
                q.pop();
                
                for(int k=0;k<4;k++){
                    
                    int nx = x+dx[k];
                    int ny = y+dy[k];
                    
                    if(nx < 0 || ny <0 || nx >= 12 || ny >= 6 || visited[nx][ny] != 0)  continue;
                    if(map[x][y] != map[nx][ny] )   continue;
                    q.push({nx,ny});
                    v.push_back({nx,ny});
                    visited[nx][ny] = 1;
                }
            }
            
            if(v.size() >=4){
                for(int k=0;k<v.size();k++)
                    map[v[k].x][v[k].y]=0;
                check=true;
            }
            v.clear();
        }
    }
    
    return check;
}

int main(void)
{
    for(int i=0;i<12;i++){
        for(int j=0;j<6;j++){
            char ch1;
            cin >> ch1;
            if(ch1 == '.')  map[i][j] = 0;
            else if(ch1 == 'R')  map[i][j] = 1;
            else if(ch1 == 'G')  map[i][j] = 2;
            else if(ch1 == 'B')  map[i][j] = 3;
            else if(ch1 == 'P')  map[i][j] = 4;
            else if(ch1 == 'Y')  map[i][j] = 5;
        }
    }
    int cnt =0;
    
    while(1){
        if(!BFS())    break;
        solve();
        cnt++;
    }
    
    cout << cnt;
    return 0;
    
}

[문제]

www.acmicpc.net/problem/14719

[풀이]

하반기 어느 기업 코테에서 굉장히 이 문제와 유사한 문제가 나왔었다.

현재 위치를 기준으로 왼쪽과 오른쪽으로 나누고 

그 중에서 가장 큰 값을  left, right 변수에 저장한다.

left와 right 중에서 작은 값을 고르고 여기서 현재 블록의 높이를 빼주면 

해당 블록의 고이는 빗물의 양이 된다.

위와 같은 방식으로 두번째 블록부터 마지막 블록 전까지 반복해주면 된다.

[코드]

시간 : 0ms

#include <iostream>
#include <algorithm>
#define MAX 501

using namespace std;

int W,H;
int block[MAX]={0,};


int main(void)
{
    int total=0;
    
    cin >> H >> W;
    for(int i=0;i<W;i++)    cin >> block[i];
    
    for(int i=1;i<W-1;i++){
        
        int right=0;
        int left=0;
        
        for(int j=0;j<i;j++)    left = max(left, block[j]);
        for(int j=W-1; j>i;j--) right =max(right, block[j]);
        
        total += max( 0 , min(left,right)-block[i]);
    }
   
    cout << total;
    return 0;
}

[문제]

www.acmicpc.net/problem/10844

[풀이]

DP 배열을 2차원을 선언하여 풀었다.

DP[i][j]는 i자리 수에서 마지막 숫자가 J인 경우의 수를 나타낸다.

예를 들어 DP[2][2]는 'X2'인 경우로 12,32가 있으므로 2이다.

따라서 계단 수를 구하는 것이므로 점화식을 아래와 같이 세울 수 있다.

DP[i][j] = DP[i-1][j-1] + DP[i-1][j+1];

단 , j가 0이거나 9인 경우 따로 예외처리 해줘야된다.

[코드]

#include <iostream>
#define MAX 101
#define MOD 1000000000

using namespace std;

int DP[MAX][10]={0,};

int main(void)
{
    int N;
    
    cin >> N;

    for(int i=1;i<10;i++)   DP[1][i] = 1;
    
    for(int i=2;i<=N;i++){
        for(int j=0;j<10;j++){
            if(j==0)    DP[i][j] = DP[i-1][1]%MOD;
            else if(j==9)   DP[i][j] = DP[i-1][8]%MOD;
            else DP[i][j]= (DP[i-1][j-1] + DP[i-1][j+1])%MOD;
        }
    }
    
    int sum =0;
    for(int i=0;i<10;i++)   sum=(sum+DP[N][i])%MOD;
    cout << sum%MOD;
    return 0;
}