개발자 김수진

[문제]

https://www.acmicpc.net/problem/20056

[풀이]

N*N 격자에 파이어볼 M개가 존재한다.

각 파이어볼은 질량(m), 속력(s), 방향(d)을 가지고 있다.

1. 모든 파이어볼이 d 방향으로 s만큼 움직인다,.

2. 2개 이상의 파이어볼이 있는 칸은 하나의 파이어볼로 합쳐진다.

 - 합쳐진 파이어볼은 4개의 파이어볼로 나뉘어진다.

- 각 파이어볼의 질량은 ( 합쳐진 파이어볼의 질량 합 / 5 )

- 각 파이어볼의 속력은 ( 합쳐진 파이어볼의 속력 합 / 파이어볼의 개수) 

- 모든 파이어볼의 방향이 홀수 또는 짝수로 일치할 경우 나뉘어진 파이어볼의 방향은 0,2,4,6이 되고 아닌 경우 1,3,5,7이 된다.

1번과 2번에 대해 각각의 api로 관리했다. 파이어볼이 이동하는 것은 moveBall에서 처리하고 파이어볼이 나뉘어 지는 것은 divideBall api에서 처리해주었다.

첫번째로 moveBall에서 파이어볼을 이동시켰다.

문제에서 주어진 조건으로 격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다. 

따라서 (1,1)을 기준으로 시작하여 s%N 만큼 이동하도록 해주었다. 또한 이동한 위치가 1보다 작거나 N보다 클 경우 N만큼 빼주거나 더해주어 이동위치를 계산했다.

그리고 두번째로 이동한 파이어볼에 대해 문제 조건에 맞게 divideBall에서 파이어볼을 나눠주도록 처리했다.

[코드]

#include <iostream>
#include <vector>
#include <cmath>
#define MAX 51

using namespace std;

struct Ball{
    int m,s,d;
};
int N,M,K;
int dx[8]={-1,-1,0,1,1,1,0,-1};
int dy[8]={0,1,1,1,0,-1,-1,-1};

vector<Ball> fireBall[MAX][MAX];

void moveBall()
{
    vector<Ball> tmpBall[MAX][MAX];
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            for(int k=0;k<fireBall[i][j].size();k++){
                int s= fireBall[i][j][k].s%N;
                int d= fireBall[i][j][k].d;
                
                int nx = i+dx[d]*s;
                int ny = j+dy[d]*s;
                
                
                if(nx < 1)   nx+=N;
                if(nx > N) nx -=N;
                
                if(ny < 1)   ny+=N;
                if(ny > N) ny-= N;
                
                tmpBall[nx][ny].push_back(fireBall[i][j][k]);
            }
        }
    }
    
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            fireBall[i][j].clear();
            fireBall[i][j] = tmpBall[i][j];
        }
    }
}

void divideBall()
{
    vector<Ball> tmpBall[MAX][MAX];

    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            if ( fireBall[i][j].size() == 1){
                tmpBall[i][j] = fireBall[i][j];
            }
            else if ( fireBall[i][j].size() >= 2){
                int totalS=0;
                int totalM=0;
                bool even=false;
                bool odd=false;
                
                for(int k=0;k<fireBall[i][j].size();k++){
                    int dir=fireBall[i][j][k].d;
                    if(dir % 2 == 0)    even = true;
                    else    odd = true;
                    
                    totalS+=fireBall[i][j][k].s;
                    totalM+=fireBall[i][j][k].m;
                }
                
                int m = totalM/5;
                int s = totalS/fireBall[i][j].size();
                int dir = even && odd ? 1 : 0;
                 if ( m > 0)
                 {
                     for(int d=dir;d<8;d+=2){
                        tmpBall[i][j].push_back({m,s,d});
                    }
                 }
            }
            fireBall[i][j].clear();
            fireBall[i][j] = tmpBall[i][j];
        }
    }
    
}

int main(void)
{
    ios::sync_with_stdio(false);
    
    cin >> N >> M >> K;
    
    for(int i=0;i<M;i++){
        int x,y,m,s,d;
        cin >> x >> y >> m >> s >> d;
        fireBall[x][y].push_back({m,s,d});
    }
    for(int i=0;i<K;i++){
        moveBall();
        divideBall();
    }
    
    long long totalM =0;
    
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            for(int k=0;k<fireBall[i][j].size();k++)    totalM+=fireBall[i][j][k].m;
        }
    }
    
    cout << totalM;
    return 0;
}

[문제]

https://www.acmicpc.net/problem/20058

[풀이]

파이어스톰은 먼저 격자를 2L × 2L 크기의 부분 격자로 나눈다. 그 후, 모든 부분 격자를 시계 방향으로 90도 회전시킨다.

격자별 회전을 처리해주기 위해 rotate api의 인자로 각 격자의 시작 점과 길이를 넘겨주도록 했다.

(0,0)을 기준으로 90도 시계 방향 회전하면 (x,y) -> (y, (N-1)-x)로 위치가 변한다.

그런데 해당 문제에서는 격자별로 90도 회전이므로 0부터 len 이전까지 반복하면서 tmp 배열에 (0,0)부터 회전한 값을 저장한다.

tmp[j][len-1-i] = map[x+i][y+j];

그리고 tmp (0,0)부터 (len-1,len-1) 까지 다시 map 배열로 옮겨준다.

map[x+i][y+i] = tmp[i][j];

이와 같은 방식으로 90도 회전을 구현했다.

회전 후 melt_ice api를 통해 얼음을 녹여준다.

그리고 find_max_lump api에서 남아있는 얼음의 합을 구하고 가장 큰 덩어리가 차지하는 칸의 개수를 출력해줬다. 

[코드]

#include <iostream>
#include <queue>

#define MAX 70

using namespace std;

struct pos {
    int x,y;
};

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

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

// 격자 시계방향 회전
void rotate(int x, int y, int len){
    int tmp[MAX][MAX]={0,};

    for(int i=0;i<len;i++)
        for(int j=0;j<len;j++)
            tmp[j][len-1-i]=map[x+i][y+j];
    for(int i=0;i<len;i++)
        for(int j=0;j<len;j++)
            map[x+i][y+j]=tmp[i][j];
}

void rotate_grid()
{
    int len = 1 << L;
    
    for(int i=0;i<N;i+=len){
        for(int j=0;j<N;j+=len){
            rotate(i,j,len);
        }
    }
}

void melt_ice()
{
    int tmp[MAX][MAX]={0,};
    
    for(int x=0;x<N;x++){
        for(int y=0;y<N;y++){
            int cnt =0;
            for(int k=0;k<4;k++){
                int nx = x+dx[k];
                int ny = y+dy[k];
                if( nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                if( map[nx][ny] != 0 )  cnt++;
            }
            if (cnt < 3) {
                if( map[x][y] != 0) tmp[x][y] = map[x][y] -1;
            }
            else tmp[x][y] = map[x][y];
        }
    }

    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            map[i][j] = tmp[i][j];
        }
    }

}

int find_max_lump()
{
    bool visited[MAX][MAX]={0,};
    int res =0;
    queue<pos> q;
    int sum=0;
    
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++){
            int cnt =0;
            sum += map[i][j];
            if(map[i][j] <= 0 || visited[i][j] )
                continue;
        
            q.push({i,j});
            visited[i][j]=1;
            
            while(!q.empty()){
                cnt++;
                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 >= N || ny >=N || visited[nx][ny] || map[nx][ny] <= 0)    continue;
                    visited[nx][ny] = 1;
                    q.push({nx,ny});
                }
            }
            if( res < cnt)  res = cnt;
        }
    }
    cout << sum << "\n";
    return res;
}

int main(void)
{
    std::ios::sync_with_stdio(false);

    cin >> N >> Q;
    N = 1 << N;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++)    cin >> map[i][j];
    }
    for(int i=0;i<Q;i++){
        cin >> L;
        rotate_grid();
        melt_ice();
    }
    cout << find_max_lump();
    return 0;
}

[문제]

https://www.acmicpc.net/problem/21611

[풀이]

1. 상어가 구슬 파괴
2. 구슬 이동
3. 구슬 폭발
   
   1. 4개 이상 연속하는 구슬
4. 구슬 이동
5. 구슬 변화
   1. 하나의 그룹 => 구슬 A,B (  A는 구슬의 개수 , B는 구슬 번호)

위와 같은 과정이 M번 반복해서 일어난다.

1번부터 5번까지의 각 과정을 api로 분리하여 구현했다.

상어가 구슬을 파괴하는 과정은 destruct_bead , 구슬이 이동하는 과정은 move_bead, 구슬이 폭발 후 이동하는 과정은  explode_bead, 구슬이 변화하는 과정은 change_bead에서 처리하도록 구현했다. 

또한 모든 과정이 달팽이 모양 회전을 기반으로 발생한다.

첫번째로 상어가 구슬을 파괴하는 과정은 현재 상어 위치를 기반으로 d 방향으로  s 거리만큼에 존재하는 구슬을 파괴하므로 for 문을 통해 간단하게 구할 수 있다. 

두번째로 구슬이 이동하는 과정을 달팽이 모양을 기반으로 회전한다. 또한 회전하는 길이가 1,1,2,2,3,3,4,4,5,5,... 이런식으로 2번씩 같은 길이를 반복하고 방향이 바뀌면서 길이가 +1이 되는 구조이다. 따라서 이중 for문의 바깥 for문에서는 2번을 count 해주고 내부 for문에서는 len 만큼 반복할 수 있도록 처리해줬다. 현재 길이를 두번 다 돌면 길이를 +1 해주도록 처리했고 영역을 벗어나는 경우에 while문을 빠져나오도록 조건을 걸었다. 달팽이 방향으로 한칸씩 다 돌면서 bead라는 일차원 배열을 선언하여 map에서 0이 아닌 값들에 대해서만 옮겨준다. 모든 map에 대해 한바퀴 다 돌고 나면 기존 map을 0으로 초기화 해주고 bead에 존재하는 값들을 복사해준다. 이때도 마찬가지로 달팽이 방향으로 회전하도록 했다.

세번째로 4개 이상 동일한 구슬이 반복되는 것에 대해 그룹화 하여 폭발시켜줬다. 이 때 문제에서 출력해야 되는 것은 폭발된 구슬의 개수이므로 explode_cnt라는 배열을 선언하여 각 구슬별 폭발된 개수를 저장해놨다. 구슬 이동과 마찬가지로 하나의 길이에 대해 두번씩 카운트 하면서 길이를 +1씩 해주었다. 이와 같이 달팽이 방향으로 돌면서 연속하는 구슬이 4개 이상인 경우 폭발 시켜줬다. bead 라는 벡터를 선언하여 폭발되지 않은 구슬만 담아줬다. 이런식으로 폭발할 구슬을 찾으면 한번 더 확인을 해줘야한다. 예를들어 구슬이 111222211111 이렇게 있으면 bead라는 벡터에 11111111이 존재하는데 이것도 연속된 구슬이 4개 이상이므로 폭발해야 하는 구슬이다. 따라서 bead에 대해서 한번 더 돌면서 연속되는 구슬이 있는지 확인해주고 update_bead 라는 벡터에 담아줬다.. 원래 구슬 폭발 후 바로 이동을 해야하는데 모든 그룹에 대해 폭발을 다 하고 이동하는식으로 구현해서 이렇게 된 것 같다. 이 부분에 대해서는 한번 더 고려해봐야겠다. 이렇게 구슬을 폭발하고  update_bead에 존재하는 구슬을 달팽이 방향으로 map에 옮겨줬다.

마지막으로 구슬을 그룹화하여 구슬 개수, 구슬 번호로 구슬을 change 해줬다. 여기서도 마찬가지로 달팽이 방향으로 돌면서 확인해줬다.

이와 같이 위의 방식을 M번 수행 후 각 구슬별 폭발된 구슬의 개수를  count 하여 출력해줬다.

유사 문제로는 

2022 상반기 오전 문제가 있는데 참고해보면 좋을 것 같다.

[코드]

#include <iostream>
#include <vector>
#include<string.h>
#define MAX 50

using namespace std;

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

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

void destruct_bead(int d,int s)
{
    int x = (N+1)/2;
    int y = (N+1)/2;
    
    for(int i=1;i<=s;i++){
        int nx = x + dx[d]*i;
        int ny = y + dy[d]*i;
        
        if( nx <= 0 || ny <= 0 || nx > N || ny > N )    break;
        map[nx][ny] =0;
    }
}

void move_bead()
{
    int tmp[MAX][MAX]={0,};
    
    int bead[MAX*MAX]={0,};
    int x= (N+1)/2;
    int y= (N+1)/2;
    int dir =3;
    int len = 1;
    int idx =0;
    bool flag=true;
    
    
    while(flag){
        for(int j=0;j<2;j++){
            for(int i=0;i<len;i++){
                x+=dx[dir];
                y+=dy[dir];
                
                if ( x <= 0 || y<= 0 || x > N || y > N ){
                    flag=false;
                    break;
                }
                
                if(map[x][y] != 0){
                    bead[idx] = map[x][y];
                    idx++;
                }
            }
            if(!flag)   break;
            
            if(dir == 1)    dir = 3;
            else if ( dir == 2) dir = 4;
            else if ( dir == 3) dir = 2;
            else if ( dir == 4) dir = 1;
        }
        len++;
    }
    
    x= (N+1)/2;
    y= (N+1)/2;
    dir =3;
    len = 1;
    idx =0;
    flag=true;
    
    
    for(int i=1;i<=N;i++){
        for(int j=0;j<=N;j++)   map[i][j]=0;
    }
               
    while(flag){
        for(int j=0;j<2;j++){
            for(int i=0;i<len;i++){
                x+=dx[dir];
                y+=dy[dir];
                
                if ( bead[idx] == 0){
                    flag=false;
                    break;
                }
                map[x][y] = bead[idx];
                idx++;
            }
            if(!flag)   break;
            
            if(dir == 1)    dir = 3;
            else if ( dir == 2) dir = 4;
            else if ( dir == 3) dir = 2;
            else if ( dir == 4) dir = 1;
        }
        len++;
    }
    
}

void explode_bead()
{
    int tmp[MAX][MAX]={0,};
    
    vector<int> bead;
    
    int x = (N+1)/2;
    int y = (N+1)/2;
    int dir =3;
    int len = 1;
    int idx =0;
    bool flag=true;
    
    
    int cur = -1;
    int cnt = 0;
    
    while(flag){
        for(int j=0;j<2;j++){
            for(int i=0;i<len;i++){

                x+=dx[dir];
                y+=dy[dir];

                if ( x <= 0 || y<= 0 || x > N || y > N || cur == 0){
                    flag=false;
                    break;
                }
                

                if(map[x][y] == cur){
                    cnt++;
                } else {
                    if( cnt >= 4 ){
                        explode_cnt[cur] += cnt;
                        for(int k=0;k<cnt;k++)  bead.pop_back();
                    }
                    cur = map[x][y];
                    cnt = 1;
                }
                bead.push_back(map[x][y]);
            }
            if(!flag)   break;
            
            if(dir == 1)    dir = 3;
            else if ( dir == 2) dir = 4;
            else if ( dir == 3) dir = 2;
            else if ( dir == 4) dir = 1;
        }
        len++;
    }
    
    vector<int> update_bead;
    
    cnt=0;
    cur = -1;
    while(1){
        bool duplicate = false;
        for(int i=0;i<bead.size();i++){
            if(bead[i] == cur){
                cnt++;
            } else {

                if( cnt >= 4 ){
                    duplicate= true;
                    explode_cnt[cur] += cnt;
                    for(int k=0;k<cnt;k++)  update_bead.pop_back();
                }
                cur = bead[i];
                cnt = 1;
            }
            update_bead.push_back(cur);

        }
        if( !duplicate )    break;
        else{
            bead.clear();
            bead = update_bead;
            update_bead.clear();
        }
    }
    
    x= (N+1)/2;
    y= (N+1)/2;
    dir =3;
    len = 1;
    idx =0;
    flag=true;
    while(flag){
        for(int j=0;j<2;j++){
            for(int i=0;i<len;i++){
                x+=dx[dir];
                y+=dy[dir];
                
                if ( idx == update_bead.size()){
                    flag=false;
                    break;
                }
                tmp[x][y] = update_bead[idx];
                idx++;
            }
            if(!flag)   break;
            
            if(dir == 1)    dir = 3;
            else if ( dir == 2) dir = 4;
            else if ( dir == 3) dir = 2;
            else if ( dir == 4) dir = 1;
        }
        len++;
    }
    
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++)    map[i][j] = tmp[i][j];
    }
}

void bead_change()
{
    
    int tmp[MAX][MAX]={0,};
    
    vector<int> bead;
    
    int x = (N+1)/2;
    int y = (N+1)/2;
    int dir = 3;
    int len = 1;
    int idx = 0;
    bool flag=true;
    
    
    int cur = -1;
    int cnt = 0;
    
    while(flag){
        for(int j=0;j<2;j++){
            for(int i=0;i<len;i++){

                x+=dx[dir];
                y+=dy[dir];

                if ( x <= 0 || y<= 0 || x > N || y > N || cur == 0){
                    flag=false;
                    break;
                }

                if(map[x][y] == cur){
                    cnt++;
                } else {
                    if(cnt>0){
                        bead.push_back(cnt);
                        bead.push_back(cur);
                    }
                    cur = map[x][y];
                    cnt = 1;
                }
            }
            if(!flag)   break;
            
            if(dir == 1)    dir = 3;
            else if ( dir == 2) dir = 4;
            else if ( dir == 3) dir = 2;
            else if ( dir == 4) dir = 1;
        }
        len++;
    }
    
    x= (N+1)/2;
    y= (N+1)/2;
    dir =3;
    len = 1;
    idx =0;
    flag=true;
    while(flag){
        for(int j=0;j<2;j++){
            for(int i=0;i<len;i++){
                x+=dx[dir];
                y+=dy[dir];
                
                if (x <= 0 || y<= 0 || x > N || y > N || idx == bead.size()){
                    flag=false;
                    break;
                }
                tmp[x][y] = bead[idx];
                idx++;
            }
            if(!flag)   break;
            
            if(dir == 1)    dir = 3;
            else if ( dir == 2) dir = 4;
            else if ( dir == 3) dir = 2;
            else if ( dir == 4) dir = 1;
        }
        len++;
    }
    
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++)    map[i][j] = tmp[i][j];
    }
    
}


int main(void)
{
    cin >> N >> M;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++)    cin >> map[i][j];
    }
    
    for(int i=0;i<M;i++){
        int d,s;
        cin >> d >> s;
        destruct_bead(d,s);
        move_bead();
        explode_bead();
        bead_change();
    }
    
    cout << explode_cnt[1] * 1 + explode_cnt[2] * 2 + explode_cnt[3] * 3;
    return 0;
}

[문제]

www.acmicpc.net/problem/1806

[풀이]

연속된 구간의 부분합을 구하는 문제이므로 투포인터 알고리즘을 사용해서 풀었다.

(투포인터 알고리즘 : https://tnwlswkd.tistory.com/44 )

start부터 end까지의 부분합이 S 이상인 경우 구간의 길이를 구하고 start를 한 칸 뒤로 움직여서 구간의 길이를 좁힌다.

이 때 start와 end가 같다면 최소 구간이 되므로 1을 출력하고 끝낸다.

부분합이 S 미만인 경우 end를 한 칸 뒤로 움직여서 구간의 길이를 넓힌다.

[코드]

시간 : 32ms

#include <iostream>
#include <vector>
#define MAX 100000

using namespace std;

int N,S;
int res = 1e9;
int sequence[MAX] = { 0, };

int main(void)
{
	cin >> N >> S;
	for (int i = 0; i < N; i++)		cin >> sequence[i];

	int start = 0;
	int end = 0;
	int total = sequence[0];

	while (end < N) {
		if (total < S)
		{
			end++;
			total += sequence[end];
		}
		else {
			if (start == end)
			{
				cout << "1";
				return 0;
			}
			int len = end - start + 1;
			if (len < res)		res = len;
			total -= sequence[start];
			start++;
		}
	}
	if (res == 1e9)	cout << "0";
	else    cout << res;
	return 0;
}

[문제]

www.acmicpc.net/problem/1202

[풀이]

보석의 무게, 가격과 가방의 무게가 주어지고 가방에 담을 수 있는 보석 가격 합의 최댓 값을 구하는 문제

무게를 기준으로 보석과 가방을 오름차순으로 정렬하여 , 가방의 무게를 기준으로 담을 수 있는 보석 무게 중 가격이 가장 높은 것을 선택하는 방식으로 풀었다. 원래는 보석 가격이 가장 높은 것을 선택하기 위해 vector를 사용해  43번째 줄의 while문이 끝날 때마다 vector를 오름차순으로 정렬하여 가장 높은 가격의 보석을 알아냈다. 하지만 시간 초과가 발생하여 priority_queue (우선순위 큐)를 사용해 queue에 push 할 때마다 정렬하도록 하여 시간초과 문제를 해결할 수 있었다.

[코드]

시간 : 572ms

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

#define MAX 300001

using namespace std;

struct diamond{
    int weight, value;
};

int bag[MAX]={0,};
int N,K;

bool comp(diamond & a, diamond & b)
{
    return a.weight < b.weight;
}

int main(void)
{
    vector <diamond> v;
    priority_queue <int> q;
    
    cin >> N >> K;
    for(int i=0;i<N;i++){
        int a,b;
        cin >> a>>b;
        v.push_back({a,b});
    }
    for(int i=0;i<K;i++)    cin >> bag[i];
    
    sort(v.begin(),v.end(),comp);
    sort(bag,bag+K);
    
    int idx =0;
    long long int res=0;

    for(int i=0;i<K;i++){
        int weight = bag[i];
        while(idx < N ){
            if(v[idx].weight <= weight){
                q.push(v[idx].value);
                idx++;
            }
            else    break;
        }
        if(q.size()==0 )  continue;
        res+=q.top();
        q.pop();
    }
    cout << res;
    return 0;
}

[문제]

www.acmicpc.net/problem/10800

[풀이]

각 플레이어가 사로잡을 수 있는 모든 공들의 크기의 합을 구하는 문제이다.

단 공의 색깔이 같거나 공의 크기가  같다면 잡을 수 없다.

처음에 단순 이중 for문을 사용해서 풀려고 했다. 그러면 시간 복잡도가 O(N^2)이 된다.

하지만 N의 범위가 1 ≤ N ≤ 200,000 이므로 최악의 경우 시간초과가 발생한다.

따라서 다른 방법을 생각했다.

먼저 공의 크기를 기준으로 오름차순 정렬을 하고 , 현재까지의 모든 공의 크기 합에서 색깔이 같거나 크기가 같은 공의 무게를 빼준다.

(idx)번째 공이 사로잡을 수 있는 공의 크기

= 현재까지 공 크기의 합 - (idx)번째 공과 색깔이 같은 공들의 무게 합 - (idx)번째 공과 크기가 같은 공들의 무게 합 + (idx)번째 공의 무게

단 , 위의 식에서 크기와 색깔이 모두 같은 경우 이전 index의 공이 사로잡을 수 있는 값과 같도록 하였다.  

또한 오름차순 정렬을 할 때 , 공의 크기가 같다면 색깔을 기준으로 정렬하도록 하였다.

색깔을 신경쓰지 않으면 아래와 같은 문제가 발생한다.

Ex)

3

1 4

2 4

1 4

출력 : -4

정답 : 4 

[코드]

시간 : 208ms

#include <iostream>
#include <vector>
#include <algorithm>
#define MAX 200020

using namespace std;

struct ball{
    int weight, color, idx;
};

int ans[MAX]={0,};
int C[MAX]={0,};
int S[MAX]={0,};
int N;
bool comp(ball &a, ball &b) {

    if (a.weight==b.weight) return a.color < b.color;

    return a.weight < b.weight;
}
int main(void)
{
    vector <ball> v;

    cin >> N;
    for(int i=0;i<N;i++){
        int weight,color;
        cin >> color >> weight;
        v.push_back({weight,color,i});
    }
    sort(v.begin(),v.end(),comp);
    
    int sum=0;
    
    for(int i=0;i<N;i++){
        
        int weight = v[i].weight;
        int color = v[i].color;
        int idx = v[i].idx;
        
        C[color]+=weight;
        S[weight]+=weight;
        sum+=weight;
        
        ans[idx]= sum - C[color] - S[weight] +weight;
        if(i!=0 && (v[i-1].color == color) && (v[i-1].weight == weight))    ans[idx] = ans[v[i-1].idx];
    }
    
    for(int i=0;i<N;i++)    cout << ans[i] <<"\n";
    return 0;
}

[문제]

www.acmicpc.net/problem/13549

[풀이]

언니의 위치 N, 동생의 위치 K가 입력으로 주어지고 언니가 동생을 찾는데 걸리는 최소 시간을 구하는 문제이다.

숨바꼭질4( www.acmicpc.net/problem/13913) 와 굉장히 유사한 문제이다.

BFS를 사용해서 풀었다. 

원래 BFS는 방문 체크를 하여 이미 방문한 곳이라면 다시 방문하지 않는다.

하지만 이 문제에서는 순간이동이 있으므로 이미 방문했더라도 최솟값을 가질 수 있다.

ex) 5 --> 8

1. 5-> 6-> 7-> 8  : 3초

2. 5-> 10-> 9-> 8  : 2초

따라서 이미 방문했더라도 현재 이동 횟수가 더 작다면 재방문 할 수 있도록 하였다.

이와 같은 방식으로 while문을 반복하여 K에 도착하면 map의 값을 return 하면서 BFS 함수를 끝내도록 하였다.

[코드]

시간 : 0ms

#include <iostream>
#include <queue>

#define MAX 200001

using namespace std;

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

int dx[2]={-1,1};

int BFS()
{
    queue <int> q;
    q.push(N);
    map[N]=1;
    
    while(!q.empty()){
        
        int x = q.front();
        q.pop();
        
        if(x == K)  return map[x]-1;
        
        for(int i=0;i<3;i++){
            int npos = x;
            if(i==2)    npos = x*2;
            else    npos= x+dx[i];
            
            if(npos <0 || npos >= MAX)  continue;
            if(i!=2 &&  (map[npos]!=0 && map[npos] <= map[x]+1))    continue;
            if(i==2 &&  (map[npos]!=0 && map[npos] <= map[x]))  continue;
            
            q.push(npos);
            
            if(i==2)    map[npos] = map[x];
            else    map[npos]= map[x]+1;
        }
    }
    
    return 0;
}
int main(void)
{
    cin >> N>> K;
    cout << BFS();
}

[문제]

www.acmicpc.net/problem/2437

[풀이]

추의 무게가 주어지고 추를 사용해서 측정할 수 없는 무게의 최솟값을 구하는 문제이다.

아무리 생각해도 다 더하는 방법 말고는 생각이 안나서 풀이를 봤다.

풀이는 그리디 알고리즘으로 구현했다. 

주어진 추의 무게를 오름차순으로 정렬하고 현재까지의 합을 sum이라고 할 때,

더하려는 추의 무게가 sum+2보다 크거나 같다면

sum+1의 무게는 측정할 수 없다.

풀이를 보니 이해는 되지만 문제를 풀면서 어떻게 이런 방식을 생각해내는지 모르겠다. 

[코드]

시간 : 0ms

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

using namespace std;

int arr[MAX]={0,};
int N;

int main(void)
{
    cin >> N;
    for(int i=0;i<N;i++)    cin >> arr[i];
    sort(arr,arr+N);
    
    int sum=0;
    
    for(int i=0;i<N;i++){
        if(sum+2<=arr[i]){
            cout << sum+1;
            return 0;
        }
        sum+=arr[i];
    }
    cout << sum+1;
    return 0;
}