개발자 김수진

[문제]

www.acmicpc.net/problem/2193

[풀이]

N이 1인 경우부터 모든 경우의 수를 구하다 보면 규칙을 금방 발견할 수 있다.

규칙을 통해 아래와 같이 점화식을 세워서 DP를 사용해 풀었다.

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

[코드]

시간 : 0ms

#include <iostream>
#define MAX 90

using namespace std;

long long DP[MAX]={0,};
int N;

int main(void)
{
    cin >> N;
    DP[1] = 1;
    DP[2] = 1;
    
    for(int i=3;i<=N;i++)
    {
        DP[i] = DP[i-1]+DP[i-2];
    }
    cout << DP[N];
    return 0;
    
}

[문제]

www.acmicpc.net/problem/2096

[풀이]

DP를 사용해서 이전 경로까지의 최대, 최솟값을 저장해놓고

이전 경로와 현재 위치의 값을 더해서 최대, 최솟값을 구했다.

처음에는 N의 범위가 N(1 ≤ N ≤ 100,000)이므로 DP배열을 [100001][3]의 크기고 잡고 시작했는데 메모리 초과가 나왔다.

생각해보니 문제 조건에서 주어진 메모리 제한은 4MB인데 [100001][3]의 크기로 잡고 풀면

min, max 배열이 2개 이므로 4MB를 넘어버린다.

생각을 해보니 DP의 값을 계산할 때마다 필요한 값은 현재 위치의 값과 이전 위치의 값이므로

DP 배열의 크기를  [2][3]으로 바꾸고 아래와 같이 풀었다.

찾아보니 이러한 기법을 '슬라이딩 윈도우'라고 하는 것 같다.

[코드]

시간 : 24ms

#include <iostream>
#define _max(a,b) ((a) > (b) ? (a) : (b))
#define _min(a,b) ((a) < (b) ? (a) : (b))

using namespace std;

int N;
int map[3];
int DP_max[2][3]={0,};
int DP_min[2][3]={0,};

int main(void)
{
    scanf("%d",&N);
    
    for(int i=1;i<=N;i++)
    {
        scanf("%d %d %d",&map[0],&map[1],&map[2]);

        DP_max[1][0]=map[0] + _max(DP_max[0][0],DP_max[0][1]);
        DP_max[1][1]=map[1] + _max(DP_max[0][0],_max(DP_max[0][1],DP_max[0][2]));
        DP_max[1][2]=map[2] + _max(DP_max[0][1],DP_max[0][2]);
        
        DP_max[0][0]= DP_max[1][0];
        DP_max[0][1]= DP_max[1][1];
        DP_max[0][2]= DP_max[1][2];

        DP_min[1][0]=map[0] + _min(DP_min[0][0],DP_min[0][1]);
        DP_min[1][1]=map[1] + _min(DP_min[0][0],_min(DP_min[0][1],DP_min[0][2]));
        DP_min[1][2]=map[2] + _min(DP_min[0][1],DP_min[0][2]);

        DP_min[0][0]= DP_min[1][0];
        DP_min[0][1]= DP_min[1][1];
        DP_min[0][2]= DP_min[1][2];
    }
    
    cout << _max(DP_max[1][0],_max(DP_max[1][1],DP_max[1][2])) << " "<<_min(DP_min[1][0],_min(DP_min[1][1],DP_min[1][2]));
    
    return 0;
    
}

[문제]

www.acmicpc.net/problem/1946

[풀이]

처음에는 2중 for문 사용해서 하나를 기준으로 현재 지원자를 기준으로 서류 점수가 더 우수한 지원자가 있다면 면접 점수를 비교하는 방식으로 풀었다.

모든 면접자에 대해서 한번씩 모두 비교해야 하므로 당연히 시간초과가 나왔다.

따라서 두번째에는 서류 점수를 기준으로 오름차순으로 정렬하고 한명의 지원자를 기준으로 앞에 있는 지원자보다 면접 점수도 낮다면 제외하였다. 이렇게 풀었는데도 시간초과가 발생했다.

마지막으로는 서류 점수를 기준으로 정렬하고 현재 지원자보다 서류 점수가 우수한 지원자들 중에서 가장 낮은 면접 점수를 임의의 tmp 변수에 저장해두어 반복문을 한번만 사용해서 풀 수 있었다.

다행히 시간초과가 발생하지 않았다. 

[코드]

시간 : 544ms 

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

#define MAX  100000

using namespace std;

int main(void)
{
    
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int T,N;
    
    cin >> T ;
    
    for(int i=0;i<T;i++){
        
        int res =1;
        
        vector <pair<int,int>> v;
        
        cin >> N;
        
        for(int j=0;j<N;j++){
            
            int a,b;
            cin >> a >> b;
            v.push_back({a,b});
        }
        
        sort(v.begin(),v.end());
        int tmp = v[0].second;
        
        for(int k=1;k<N;k++){
            if(v[k].second < tmp )  res++;
            if(tmp > v[k].second)   tmp = v[k].second;
        }
        cout << res <<"\n";
    }
    return 0;
}

[문제]

www.acmicpc.net/problem/1197

[풀이]

MST의 가중치를 구하는 문제로 Kruskal 알고리즘을 사용해서 풀었다.

정점간의 연결 정보를 입력 받고 벡터에 저장했다.

가중치를 기준으로 벡터를 정렬하고 , 가중치가 작은 것부터 Union-Find를 사용해 묶어줬다.

Union을 하기 전에 Find를 통해 부모가 같은지 미리 확인한다.

( 부모가 같은 상태에서 union을 해버리면 사이클이 발생하므로 )

[코드]

시간 : 48ms

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

#define MAX 10000

using namespace std;

int parent[MAX]={0,};

int Find(int idx)
{
    if(idx == parent[idx])  return idx;
    else{
        parent[idx] = Find(parent[idx]);
        return parent[idx];
    }
}

void Union(int idx1, int idx2)
{
    idx1 = Find(idx1);
    idx2= Find(idx2);
    if(idx1  != idx2)   parent[idx2] = idx1;
}

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    
    int V,E;
    cin >> V >> E;
    
    vector <pair<int, pair<int, int>>> v(E);

    for(int i=1;i<=V;i++)   parent[i] = i;
    
    for(int i=0;i<E;i++)
    {
        int a,b,c;
        cin >> a >> b >> c;
        
        v.push_back(make_pair(c, make_pair(a,b)));
    }
    
    sort(v.begin(),v.end());
    int ans=0;
    
    for(int i=0;i<v.size();i++){
        
        int tmp1 = v[i].second.first;
        int tmp2 = v[i].second.second;
        
        if(Find(tmp1) != Find(tmp2)){
            Union(tmp1,tmp2);
            ans+= v[i].first;
        }
    }
    
    cout << ans;
    
    return 0;
    
}

[문제]

www.acmicpc.net/problem/3020

[풀이]

처음에는 반복문을 사용해서 풀려고 했지만 N,H 범위를 생각해서 따지면

반복문 10억번에 1초라고 생각하면 20,000 * 50,000 이므로 1초를 훨씬 넘길 것이다. 

따라서 이분 탐색 방법으로 풀어야겠다고 생각했다.

 lower_bound는 x 이상인 값이 처음 나오는 index를 return하고

upper_bound는 x 이하인 값이 처음 나오는 index를 return 하므로 

전체 갯수에서 return 된 값을 빼면 파괴하는 장애물의 수를 구할 수 있다.

[코드]

시간 : 60ms

( 이분 탐색 직접 구현해서 다시  풀어봐야겠다.)

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

#define MAX 100000

using namespace std;

int N,H;

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int res = 1e9;
    cin >> N >> H;
    
    vector <int> up(N/2);
    vector <int> down(N/2);
    
    for(int i=0;i<N/2;i++)  cin >> down[i]>> up[i];

    int total=1;
       
    sort(down.begin(),down.end());
    sort(up.begin(),up.end());
    
    for(int i=1;i<=H;i++)
    {
        int cnt = down.size() - (lower_bound(down.begin(), down.end(),i)-down.begin());
        cnt += up.size() - (upper_bound(up.begin(), up.end(),H-i)-up.begin());
        
        
        if(res == cnt ) total++;
        else if(res > cnt ){
            res = cnt;
            total=1;
        }

    }

    cout << res << " " << total;
    return 0;
    
}

[문제]

www.acmicpc.net/problem/11660

[풀이]

표의 크기 N과 합을 구해야 하는 횟수 M이 입력으로 주어진다.

그 다음으로 표의 값이 주어지고 구간의 시작 좌표, 마지막 좌표가 주어진다.

이 구간의 합을 구해서 출력하면 된다.

처음에는 이중 for문을 사용해서 시작점인 (x1,y1)부터 구간의 마지막 부분인 (x2,y2) 까지의 합을 구했다.

당연히 시간초과가 나왔고 다른 방법을 찾아봤다.

찾아보니 DP를 사용해서 구간 합을 구할 수 있었다. 

(1,1)부터 (x,y)까지의 구간 합을 배열 DP[x][y]에 저장한다.

DP[N][N]까지 구하고 M번만큼 반복문 하여 각 구간에 대해 구간 합을 출력하면 된다.

위의 그림에서 우리가 구하고 싶은 구간 합의 영역이 4번 영역이라면

4번 영역의 구간 합은 4 = 3+2-1이 된다.

각 영역의 오른쪽 아래 부분이 (그림 2에서 진하게 표시된 부분)

해당 영역의 구간 합이므로 아래와 같이 구할 수 있다.

 DP[x2][y2]-DP[x2][y1-1]-DP[x1-1][y2] + DP[x1-1][y1-1]

[코드]

시간 : 228 ms

#include <iostream>
#define MAX 1025


int map[MAX][MAX]={0,};
long long int DP[MAX][MAX]={0,};

int N,M;


int main(void)
{
    scanf("%d %d",&N,&M);
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            scanf("%d",&map[i][j]);
            DP[i][j] = DP[i-1][j] + DP[i][j-1] - DP[i-1][j-1] + map[i][j];
        }
    }
    
    DP[1][1]=map[1][1];
     
    for(int i=0;i<M;i++)    {
        
        int x1,y1,x2,y2;
        scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
        std::cout << DP[x2][y2]-DP[x2][y1-1]-DP[x1-1][y2] + DP[x1-1][y1-1] << "\n";
    }
    
    return 0;
    
}

[문제]

www.acmicpc.net/problem/2252

[코드]

N 명의 학생들을 M번 비교하고 그 결과가 입력으로 주어진다.

이를 통해 학생들을 줄을 세우는 결과를 출력하면 된다.

학생들의 키가 모두 주어진 것이 아니고 일부만 주어졌으므로 '위상 정렬'을 사용해서 풀었다.

Degree에 각 노드에 대한 연결 차수를 저장하고

연결 차수가 0인 노드만 queue에 push 하여 순서대로 출력했다.

[풀이]

시간 : 44ms

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

#define MAX 32001

using namespace std;

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

vector <int> v[MAX];


int main(void)
{
    queue <int> q;
    
    scanf("%d %d",&N,&M);
    for(int i=0;i<M;i++)
    {
        int x1,x2;
        scanf("%d %d",&x1,&x2);
        
        Degree[x2]++;
        v[x1].push_back(x2);
    }
    
    for(int i=1;i<=N;i++)    if(Degree[i]==0)    q.push(i);
    
    while(!q.empty())
    {
        int x = q.front();
        q.pop();
        
        printf("%d ",x);
        
        for(int i=0;i<v[x].size();i++){
            int tmp = v[x][i];
            Degree[tmp]--;
            if(Degree[tmp]==0)  q.push(tmp);
        }
    }
    return 0;
}

[문제]

www.acmicpc.net/problem/1463

[풀이]

DP를 사용해서 2부터 N까지의 1을 만들 때 필요한 연산의 최소 횟수를 구했다.

bottom-up 방식을 사용해 2부터 N까지의 최솟 값을 구했다.

연산은 아래와 같이 3가지 연산이 있다.

1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

따라서 1을 빼는 연산은 모든 숫자에 대해 가능하므로 구하고 

X가 2로 나눠지는 경우, 3으로 나눠지는 경우에는 이에 대한 경우도 구해서 최솟 값을 구했다.

[코드]

시간 : 4ms

#include <stdio.h>
#define MAX 1000001


int MIN(int a, int b)
{
    if(a>b )    return b;
    else    return a;
}

int main(void)
{
    int N;
    int DP[MAX]={0,};
    
    scanf("%d",&N);
    
    for(int i=2;i<=N;i++)
    {
        DP[i] = DP[i-1]+1;
        if(i%2 == 0)    DP[i] = MIN(DP[i], DP[i/2]+1);
        if(i%3 == 0)    DP[i] = MIN(DP[i], DP[i/3]+1);
    }
    printf("%d",DP[N]);
    return 0;
    
}