2024-03-13

-2의 멱수의 합(2410, 백준)

 간단한 Dp문제였다. 2의 제곱수를 모두 구해준 뒤, 이를 이용해 수를 만들면 된다. Dp[i][j] = i개의 멱수를 사용해 j를 만들때의 경우의 수로 두고 풀었다.

>점화식<

if(i > 0) dp[j][i] = (dp[j][i] + dp[j][i - 1])

if (j >= vec[i]) dp[j][i] = (dp[j][i] + dp[j - vec[i]][i])

<소스 코드>

#include <stdio.h>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

int n;
int dp[1000010][20];
vector <int> vec;

int main()
{
	int i, j;
	scanf("%d", &n);
	for (i = 0;; i++) {
		int x = pow(2, i);
		if (n < x) break;
		vec.push_back(x);
	}
	for (i = 0; i < vec.size(); i++) {
		dp[vec[i]][i] = 1;
		for (j = 1; j <= n; j++) {
			if(i > 0) dp[j][i] = (dp[j][i] + dp[j][i - 1]) % 1000000000;
			if (j >= vec[i]) dp[j][i] = (dp[j][i] + dp[j - vec[i]][i]) % 1000000000;
		}
	}
	printf("%d", dp[n][vec.size() - 1]);
	return 0;
}

-강의실 배정(11000, 백준)

 우선순위 큐를 이용하는 그리디 문제였다. 우선순위큐를 생각하기까지의 과정이 어려울 수 있다. 강의의 시작시간을 기준으로 정렬한 후, 우선순위큐의 가장 위의 값보다 현재 시작값이 더 작다면, 우선순위큐에 강의의 끝 시간을 집어넣어가며 구해나가면 된다.

<소스 코드>

#include <stdio.h>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

int n;
priority_queue <int> pq;
vector <pair<int, int>> vec;

int main()
{
    int i, j;
    scanf("%d", &n);
    for(i=0;i<n;i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        vec.push_back({x, y});
    }
    sort(vec.begin(), vec.end());
    pq.push(-vec[0].second);
    for(i=1;i<n;i++) {
        int x = -pq.top();
        if(vec[i].first < x) {
            pq.push(-vec[i].second);
        }
        else {
            pq.pop();
            pq.push(-vec[i].second);
        }
    }
    printf("%d", pq.size());
}

-환승(5214, 백준)

 BFS문제였다. 모든노드를 연결하는 순간 메모리초과의 늪에 빠져버린다. 이를 해결하기 위해 나는 한 하이퍼큐브가 연결하는 노드들을 모두 하나의 그룹으로 묶어, BFS를 돌려주었다.

#include <stdio.h>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

int n, m, k;
vector<int> group[1010], vec[100010];
int dis[100010];
int ch[100010];
int gr_ch[1010];

void BFS(int x)
{
    int i, j;
    queue <int> q;
    q.push(x);
    dis[x] = 0;
    ch[x] = 1;
    while(!q.empty()) {
        int now = q.front();
        q.pop();
        for(i=0;i<vec[now].size();i++) {
            int nw = vec[now][i];
            if(gr_ch[nw] == 1) continue;
            gr_ch[nw] = 1;
            for(j=0;j<group[nw].size();j++) {
                int nnw = group[nw][j];
                if(ch[nnw] == 1) continue;
                ch[nnw] = 1;
                dis[nnw] = dis[now] + 1;
                q.push(nnw);
            }
        }
    }
}

int main()
{
    int i, j;
    scanf("%d %d %d", &n, &k, &m);
    for(i=0;i<m;i++) {
        for(j=0;j<k;j++) {
            int x;
            scanf("%d", &x);
            vec[x].push_back(i);
            group[i].push_back(x);
        }
    }
    BFS(1);
    if(ch[n] == 0) printf("-1");
    else printf("%d", dis[n] + 1);
    return 0;
}