개발자 김수진

[문제]

www.acmicpc.net/problem/5624

[풀이]

N개의 수열이 입력으로 주어지고, 하나의 숫자가 앞의 3개의 숫자를 더해서 나타낼 수 있을 때 좋은 수라고 한다.

이 때 입력에서 좋은 수의 갯수를 구해서 출력하면 된다.

좋은 수인지 판단하려는 숫자고 D라고 하면 A+B+C=D를 만족하는 수를 찾으면 된다.

좀더 다르게 생각하면 A+B=D-C 를 만족하는 D를 찾으면 된다.

따라서 D 이전의 숫자들 중에서 A+B의 값을 negative, positive 배열에 저장해놓고

D-C를 만족하는 값이 있는지 확인하는 방법으로 구현했다.

입력으로 주어지는 숫자가 -100,000 ≤ Ai ≤ 100,000이므로 A+B가 음수일수도 있다.

음수는 negative 배열에, 양수는 positive 배열에 저장했다.

[코드]

시간 : 8ms

#include <iostream>
#define MAX 100001

using namespace std;

int N;
int arr[5001]={0,};
bool positive[MAX*2]={0,};
bool negative[MAX*2]={0,};

int main(void)
{
    cin >> N;
    for(int i=0;i<N;i++)    cin >> arr[i];
    
    int cnt =0;
    for(int i=1;i<N;i++){
        for(int j=0;j<i;j++){
            int num =arr[j]+arr[i-1];
            if(num >=0) positive[num]=true;
            else    negative[num*-1]=true;
        }

        for(int j=0;j<i;j++){
            int num =arr[i]-arr[j];
            if(num >=0 && positive[num]){
                cnt++;
                break;
            }
            else if( num<0 && negative[num*-1]){
                cnt++;
                break;
            }
        }
    }
    cout << cnt;
    return 0;
}

[문제]

www.acmicpc.net/problem/1339

[풀이]

입력으로 주어진 알파벳을 숫자로 바꿔서 알파벳 합의 최댓값을 구하는 문제이다.

먼저 해당 알파벳이 몇번째 숫자로 얼마나 나왔는지에 따라 알파벳에 대한 숫자를 지정했다.

예를 들어 ABCD라면, A->9, B->8, C->7, D->6 이렇게 큰 자릿수가 큰 숫자를 가지도록 해야 최댓값을 구할 수 있다.

따라서 visited 배열에 해당 알파벳의 자릿수를 저장하였다.

위의 예시로는 visited[0]=1000, visited[1] = 100, visited[2] = 10, visited[3] = 1

이와 같은 방식으로 입력으로 주어진 알파벳에 대해 저장하였다.

입력이 ABA인 경우 visited[0] = 101, visited[1] = 10이 된다.

이렇게  visited 배열을 저장하고, visited 배열에 저장된 값을 기준으로 정렬하였다.

그리고 9부터 시작하여 큰 값을 가지고 있는 알파벳에 할당하였다.

이런 식으로 각 알파벳에 대해 숫자를 지정하고 합을 구하여 출력하였다. 

[코드]

시간 : 0ms

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
 
using namespace std;

int N;
vector <string> v;

int alphabet[26]={0,};
int visited[26]={0,};

int main(void)
{
    cin >> N;
    for(int i=0;i<N;i++){
        string tmp;
        cin >> tmp;
        v.push_back(tmp);
    }
    vector <pair<int,int>> order;
    
    for(int i=0;i<N;i++){
        string str = v[i];
        int _size = str.size();
        int idx = 1;
        for(int j=_size-1;j>=0;j--){
            visited[str[j]-65] += idx;
            idx *=10;
        }
    }
    for(int i=0;i<26;i++)
        if(visited[i] != 0) order.push_back({visited[i],i});
    
    sort(order.begin(),order.end());
    
    int num=9;
    for(int i=order.size()-1 ; i>=0;i--){
        if(alphabet[order[i].second]==0){
            alphabet[order[i].second]=num;
            if(num>0)   num--;
        }
    }
    int ans =0;
    for(int i=0;i<N;i++){
        string str = v[i];
        int _size = str.size();
        int idx = 1;
        for(int j=_size-1;j>=0;j--){
            ans += alphabet[str[j]-65] * idx;
            idx *= 10;
        }
    }
    cout <<ans;
    return 0;
    
}

[문제]

www.acmicpc.net/problem/4179

[풀이]

지훈이가 미로를 빠져나오는데 최소 시간을 구하는 문제로 아래 문제와 굉장히 유사하여 쉽게 접근할 수 있었다.

www.acmicpc.net/problem/5427

불도 매초마다 상,하,좌,우로 퍼지고 지훈이도 상,하,좌,우로 움직일 수 있으므로 BFS를 사용해서 풀었다.

불과 지훈이는 매초마다 움직이므로 BFS함수에서 불이 먼저 퍼지고, 지훈이가 이동하도록 구현을 하였다.

불의 좌표는 fire 변수에 저장하고, 지훈이의 좌표는 person에 저장하여 person이 empty가 아닐 때까지 while 문을 반복하도록 하였다.

person이 empty가 되어 while을 빠져나온다면 지훈이가 탈출할 방법이 없는 것이므로  "IMPOSSIBLE"을 출력하면서 BFS 함수를 끝내도록 하였다,

또한 지훈이의 위치가 가장자리일 경우 탈출을 할 수 있으므로 visited의 저장된 값을 출력하고 BFS 함수를 끝내도록 하였다.

[코드]

시간 :88ms

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

using namespace std;

struct pos{
    int x,y;
};
     
queue <pos> fire;
queue <pos> person;

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

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

void BFS()
{
    while(!person.empty()){
        
        int fnum = fire.size();
        int pnum = person.size();
        
        while(fnum){
            fnum--;
            int x = fire.front().x;
            int y = fire.front().y;
            
            fire.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||map[nx][ny]!=0)    continue;
                
                fire.push({nx,ny});
                map[nx][ny] = 1;
            }
        }
        
        while(pnum){
            pnum--;
            int x = person.front().x;
            int y = person.front().y;
            
            person.pop();
            if(x == 0 || y ==0 || x==N-1 || y ==M-1) {
                cout << visited[x][y];
                return;
            }
            
            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||map[nx][ny]!=0||visited[nx][ny]!=0)    continue;
                
                person.push({nx,ny});
                visited[nx][ny] = visited[x][y]+1;
            }
        }
    }
    
    cout << "IMPOSSIBLE";
    return;
}

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 == 'F'){
                fire.push({i,j});
                map[i][j]=1;
            }
            else if(ch == 'J') {
                person.push({i,j});
                visited[i][j]=1;
            }
        }
    }
    BFS();
    
    return 0;
}

[문제]

www.acmicpc.net/problem/1018

[풀이]

하나는 맨 왼쪽 위 칸이 흰색인 경우, 하나는 검은색인 경우 서로 완전 반대의 상태가 된다.

따라서 하나의 상태만 구해놓고 반대로 생각하면 된다.

검은색은 1, 흰색은 0으로 구분하여 int형이 아닌 bool형 배열을 사용했다.

먼저 맨 왼쪽 위 칸이 검은색인 경우를 구해서 b라는 배열에 저장했다.

그리고 반복문을 통해 모든 좌표에 대해서

(x,y)가 맨 왼쪽 위 칸이 되어 8*8 크기의 배열로 현재 주어진 입력에서 검은색과 흰색에 대해 각각 바꿔야하는 칸의 갯수를 확인했다. 

이러한 방법으로 (0,0)부터 (N-8,M-8)까지 확인하면서 다시 칠해야 하는 정사각형의 최소 개수를 구할 수 있었다.

모든 좌표에 대해서 확인해줘야 하므로 시간초과를 걱정했지만 

배열의 최대 크기가 50*50 이므로 시간초과는 발생하지 않는다.

[코드]

시간 : 0ms

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

#define MAX 51

using namespace std;

struct pos{
    int x,y;
};

int dx[4] = {-1,0,1,0};
int dy[4] = {0,1,0,-1};
int N,M;
bool visited[MAX][MAX]={0,};
bool map[MAX][MAX]={0,};
bool b[MAX][MAX]={0,};

void black()
{
    queue <pos> q;
    b[0][0]=true;
    q.push({0,0});
    visited[0][0]=true;
    
    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||visited[nx][ny])   continue;
            if(b[x][y]==false) b[nx][ny] = true;
            q.push({nx,ny});
            visited[nx][ny]=true;
        }
    }
}


int solve(int x,int y)
{
    int b_cnt=0;
    int w_cnt=0;
    
    for(int i=x;i<x+8;i++){
        for(int j=y;j<y+8;j++){
            if(map[i][j] != b[i][j])    b_cnt++;
        }
    }
    for(int i=x;i<x+8;i++){
        for(int j=y;j<y+8;j++){
            if(map[i][j] == b[i][j])    w_cnt++;
        }
    }
    return min(b_cnt,w_cnt);
}
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=='B')    map[i][j]=true;
        }
    }
    
    int ans = MAX*MAX;
    black();
    
    for(int i=0;i<=N-8;i++){
        for(int j=0;j<=M-8;j++){
            ans = min(ans,solve(i,j));
        }
    }
    cout << ans;
    return 0;
}

[문제]

www.acmicpc.net/problem/20056

[풀이]

구현 문제로 k번의 이동 후 , 남아있는 파이어볼의 질량을 구하는 문제이다.

파이어볼이 이동하고 , 파이어볼이 2개 이상 존재하는 곳은 파이어볼이 하나로 합쳐진 뒤 4개로 나누어진다.

따라서 파이어볼이 이동하는 move 함수와, 파이어볼이 나누어지는 solve 함수를 따로 구현하였다.

먼저 입력받은 파이어볼의 정보를 fire라는 구조체 벡터에 저장한다.

move 함수에서는 fire 구조체 벡터에 저장된 파이어볼이 하나씩 움직인다.

이 때 신경써야 할 부분은 '1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다.'

따라서 속력 s를 N으로 나머지 연산을 하고, 0보다 작거나 N보다 크고 같은 경우 N을 더해주거나 빼줬다.

한 공간에 2개 이상의 파이어볼이 존재한다면 나누어줘야 하므로 이차원 배열 벡터를 사용해 파이어볼의 위치를 저장했다.

solve 함수에서는 파이어볼이 움직이는 함수로 map의 사이즈가 2보다 크거나 같은 경우 나누어지도록 하였다.

여기서 조심해야 될 부분은 해당 좌표에 존재하는 파이어볼의 방향이 모두 짝수이거나 홀수인 경우와 그렇지 않을 경우의 방향이 달라지므로 신경써줘야 된다.

파이어볼을 나누고 파이어볼의 좌표도 달라졌으므로 map도 clear 해줘야된다. 

또한 파이어볼의 좌표, 속력, 방향, 무게가 모두 바꼈으므로 fire 구조체도 update 해줘야된다.

이와 같은 방법으로 K번 반복한 뒤 , 존재하는 파이어볼의 무게를 모두 더하여 출력하면 된다. 

[코드]

시간 : 16ms

#include <iostream>
#include <vector>

#define MAX 51

using namespace std;

struct FIRE{
    int x,y;
    int m,s,d;
};

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

int N,M,K;
vector <int> map[MAX][MAX];
vector <FIRE> fire;

void solve()
{
    vector <FIRE> tmp;

    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            int num = map[i][j].size();

            if(num >= 2){
                int m=0,s=0,d=0;
                bool odd = false;
                bool even = false;
                for(int k=0;k<num;k++){
                    int idx = map[i][j][k];
                    m += fire[idx].m;
                    s += fire[idx].s;
                    if(fire[idx].d%2 == 0)  even=true;
                    else    odd= true;
                }
                m = m/5;
                s = s/num;
                
                if(m!=0){
                    if(odd && even)  d=1;
                    else    d=0;
                    
                    for(int k=0;k<4;k++){
                        tmp.push_back({i,j,m,s,d});
                        d+=2;
                    }
                }
            }
            else if(num==1)    {
                int idx = map[i][j][0];
                tmp.push_back(fire[idx]);
            }
            map[i][j].clear();
        }
    }
    fire.clear();
    fire = tmp;
}

void move()
{
    for(int i=0;i<fire.size();i++){
                
        int x= fire[i].x;
        int y= fire[i].y;
        int s= fire[i].s;
        int d= fire[i].d;
        
        s = s%N;
        x = x+dx[d]*s;
        y = y+dy[d]*s;
        
        if(x < 0)   x+=N;
        if(x >= N) x -=N;
        
        if(y < 0)   y+=N;
        if(y >= N) y-= N;
        
        fire[i].x = x;
        fire[i].y = y;
        map[x][y].push_back(i);
    }
}

int main(void)
{
    cin >> N >> M >> K;
    
    for(int i=0;i<M;i++){
        int x,y,m,s,d;
        cin >> x >> y >> m >> s >> d;
        fire.push_back({x,y,m,s,d});
    }
    
    for(int i=0;i<K;i++){
        move();
        solve();
    }
    
    int ans=0;
    for(int i=0;i<fire.size();i++)  ans += fire[i].m;
    
    cout << ans;
    return 0;
}

[문제]

www.acmicpc.net/problem/15653

[풀이]

처음에는 DFS 방식으로 접근을 하였다.

하지만 생각을 해보니 DFS 함수의 탈출 조건을 설정할 수 없었다.

따라서 다른 방법을 생각하던 중 BFS 방식으로 풀어야겠다고 생각했다.

BFS 방식에서 처음 입력 값의 빨간, 파란 공의 위치를 시작으로 상,하,좌,우 방향으로 움직이도록 하였다.

이 때 파란 공이 골에 들어가거나, 이미 방문했던 위치라면 continue를 사용해 queue에 push하지 못하도록 하였다.

또한 움직인 빨간 공이 골에 들어갔다면 cnt를 return 하면서 BFS 함수를 끝내도록 하였다.

이러한 방식으로  queue가 empty가 아닐 때까지 반복하도록 하였다.

[코드]

시간 : 0ms

#include <iostream>
#include <queue>

#define MAX 11

using namespace std;

struct pos{
    int x,y;
};

struct ball{
    int rx,ry;
    int bx,by;
    int cnt;
};

pos red,blue,goal;

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

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


pos move(int x, int y,int dir)
{

    while(1){
        x+=dx[dir];
        y+=dy[dir];
        if(x < 0 || y <0 || x >= N || y >= M || map[x][y] != 0 ){
            x -= dx[dir];
            y -= dy[dir];
            break;
        }
        if(goal.x==x && goal.y== y) break;
    }

    return {x,y};
}

int BFS()
{
    queue <ball> q;
    
    q.push({red.x,red.y,blue.x,blue.y,0});
    visited[red.x][red.y][blue.x][blue.y]=true;
    
    while(!q.empty()){

        int rx = q.front().rx;   int ry= q.front().ry;
        int bx = q.front().bx;   int by= q.front().by;
        int cnt = q.front().cnt;
        q.pop();
        
        for(int i=0;i<4;i++){
            
            pos tmp_red = move(rx,ry,i);
            pos tmp_blue = move(bx,by,i);
            
            
            if((tmp_blue.x == goal.x) &&(tmp_blue.y==goal.y))  continue;
            if((tmp_red.x==goal.x)&&(tmp_red.y == goal.y))    return cnt+1;
            
            if((tmp_blue.x==tmp_red.x)&&(tmp_blue.y==tmp_red.y)){
                
                if(i==0){
                    if(rx < bx)  tmp_blue.x++;
                    else    tmp_red.x++;
                }
                else if(i == 1){
                    if(ry < by)  tmp_red.y--;
                    else    tmp_blue.y--;
                }
                else if(i == 2){
                    if (rx < bx) tmp_red.x--;
                    else    tmp_blue.x--;
                }
                else if(i == 3){
                    if( ry< by) tmp_blue.y++;
                    else    tmp_red.y++;
                }
            }
            
            if(visited[tmp_red.x][tmp_red.y][tmp_blue.x][tmp_blue.y])   continue;
            visited[tmp_red.x][tmp_red.y][tmp_blue.x][tmp_blue.y]=true;
            q.push({tmp_red.x,tmp_red.y,tmp_blue.x,tmp_blue.y,cnt+1});
        }
    }
    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')    goal={i,j};
            else if(ch=='R')    red = {i,j};
            else if(ch=='B')    blue = {i,j};
        }
    }
    
    cout << BFS();
    
    return 0;
    
}

[문제]

www.acmicpc.net/problem/2931

[풀이]

맞아서 기분이 좋긴 하지만 뭔가 찝찝하다.

3 5
. . . . .
. M . Z .
. . . . .

위와 같은 예제는 답이 제대로 나오지 않는다.

시작점을 기준으로 DFS 함수를 통해 한칸씩 나아가도록 하였다.

이 때 현재 위치의 값이 '.' 이라면 solve 함수에서 해당 위치에 들어갈 값을 찾도록 하였다.

[코드]

시간 : 0ms

#include <iostream>
#define MAX 26

using namespace std;

struct pos {
    int x,y;
};

char map[MAX][MAX]={0,};

int R,C;

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

pos start;

void solve(int x, int y)
{
    cout << x+1 << " " << y+1 << " ";
    bool dir[4] = {0,};
    
    for(int i=0;i<4;i++){
        
        int nx = x+dx[i];
        int ny = y+dy[i];
        
        if(nx<0 || ny< 0 || nx >= R || ny >= C )   continue;
        
        if(map[nx][ny] != '.'){
            if(i == 0 && (map[nx][ny] == '1' || map[nx][ny] == '4' || map[nx][ny] == '|' || map[nx][ny] =='+'))  dir[i]=true;
            else if(i == 1 && (map[nx][ny] == '3' || map[nx][ny] == '4' || map[nx][ny] == '-' || map[nx][ny] =='+'))  dir[i]=true;
            else if(i == 2 && (map[nx][ny] == '2' || map[nx][ny] == '3' || map[nx][ny] == '|' || map[nx][ny] =='+'))  dir[i]=true;
            else if(i == 3 && (map[nx][ny] == '1' || map[nx][ny] == '2' || map[nx][ny] == '-' || map[nx][ny] =='+'))  dir[i]=true;

        }
    }
    if(dir[0] && dir[1] && dir[2] && dir[3])    cout << "+";
    else if(dir[1] && dir[2])   cout << "1";
    else if(dir[0] && dir[1])   cout << "2";
    else if(dir[0] && dir[3])   cout << "3";
    else if(dir[2] && dir[3])   cout << "4";
    else if(dir[0] && dir[2])   cout << "|";
    else if(dir[1] && dir[3])   cout << "-";
    
    return ;
}

void DFS(int x, int y, int dir)
{
    if(map[x][y] == '.'){
        solve(x,y);
        return ;
    }
    
    int nx = x+dx[dir];
    int ny = y+dy[dir];
    
    if(dir ==0 ){
        if(map[nx][ny] == '|' || map[nx][ny] == '+')    dir = 0;
        else if(map[nx][ny] =='1')    dir= 1;
        else if(map[nx][ny] =='4') dir = 3;
    }
    else if(dir == 1 ){
        if(map[nx][ny] == '-' || map[nx][ny] == '+')    dir = 1;
        else if(map[nx][ny] =='3')    dir= 0;
        else if(map[nx][ny] =='4') dir = 2;
    }
    else if(dir == 2){
        if(map[nx][ny] == '|' || map[nx][ny] == '+')    dir = 2;
        else if(map[nx][ny] =='2')    dir= 1;
        else if(map[nx][ny] =='3') dir = 3;
    }
    else if(dir == 3){
        if(map[nx][ny] == '-' || map[nx][ny] == '+')    dir = 3;
        else if(map[nx][ny] =='1')    dir= 2;
        else if(map[nx][ny] =='2') dir = 0;
    }
    DFS(nx,ny,dir);
    return;
}

int main(void)
{

    cin >> R>>C;
    for (int i=0; i<R; i++){
        for(int j=0;j<C;j++){
            cin >> map[i][j];
            if(map[i][j]== 'M')  start = {i,j};
        }
    }
    
    int Direction =0;
    
    for (int i = 0; i < 4; i++) {
        int nx =start.x + dx[i];
        int ny =start.y + dy[i];

        if (nx < 0 || nx >= R || ny < 0 || ny >= C) continue;
        if (map[nx][ny] != '.') {
            if (nx ==start.x) {
                if (ny == start.y - 1)  Direction = 3;
                else if (ny == start.y+ 1)  Direction = 1;
            }
            else if (ny == start.y) {
                if (nx == start.x - 1)  Direction = 0;
                else if (nx ==start.x + 1)  Direction = 2;
            }
        }
    }

    DFS(start.x,start.y,Direction);
    return 0;
}

[문제]

www.acmicpc.net/problem/1756

[풀이]

오븐의 지름, 피자 반죽의 지름이 주어지고 마지막 피자 반죽의 위치를 출력하면 된다.

처음에는 완전 탐색으로 풀까 생각했는데 N,D의 최댓 값이 300,00이라서 시간초과가 나오게 된다.

따라서  dp 방법을 사용해 구현했다.

depth 라는 배열에 해당 깊이에 구워질 수 있는 피자 지름의 최댓값을 저장했다.

문제 예제로 보면 

7 3

5 6 4 3 6 2 3

3 2 5

depth 배열의 값은 5 5 4 3 3 2 2 가 된다.

이제 오븐의 뒤에서부터 피자를 구울 수 있는 곳을 찾아가면 된다.

3 2 5 로 보면 지름이 3인 피자는 뒤에서 3번째의 위치에서 ( 5 5 4 3 3 2 2 ) 구울 수 있다. 

그 다음으로 지름이 2인 피자는 뒤에서 3번째보다 더 앞 부분에서 구워야 하므로 

뒤에서 4번째 위치에서 ( 5 5 4 3 3 2 2 )  구울 수 있다.

마지막으로 지름이 5인 피자는 앞에서 2번째의 위치에서 ( 5 5 4 3 3 2 2 ) 구울 수 있다.

이런식으로 모든 피자에 대해 반복하고 오븐의 마지막 위치를 출력하면 된다.

[코드]

시간 : 264ms

#include <iostream>
#include <vector>

#define MAX 300001

using namespace std;

int D,N;
int depth[MAX]={0,};
int pizza[MAX]={0,};

int main(void)
{
    cin >> D >> N;
    for(int i=0;i<D;i++){
        cin >> depth[i];
        if( i>0 &&  depth[i-1] < depth[i])   depth[i] = depth[i-1];
    }
    
    for(int i=0;i<N;i++)    cin >> pizza[i];
    
    int idx = 0;
    for(int i=D-1 ; i>=0; i--){
        if(depth[i] >= pizza[idx])  idx++;
        if(idx==N){
            cout << i+1;
            break;
        }
        if(i==0){
            cout <<"0";
            break;
        }
    }
    return 0;
    
}