개발자 김수진

[문제]

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;
}

[문제]

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;
}