오늘의 문제 2020.5.17

 

이 그룹 에서 매일 문제를 푼다.

2020.5.17

 

A - 수빈이와 수열

10539번: 수빈이와 수열

말 안해도 푸실 수 있죠?

 

B - 더하기 사이클

1110번: 더하기 사이클

시.뮬.레.이.션

 

C - 나무 자르기

2805번: 나무 자르기

 

$f(x)$를 정의하자.

 

$f(x)$ : 높이가 $x$일때 잘라지는 나무의 길이

 

 

 

이제 이걸 가지고 이분탐색을 돌려줄 수 있다.

 

만약 $f(x)$가 $M$보다 크거나 같다면 상한선을 줄여주면 되고 $M$보다 작은 경우에는 하한선을 늘려주면 된다.

시간복잡도는 $O(NlogN)$이다.

 

D - 정수 삼각형

1932번: 정수 삼각형

다이나믹 배열의 정의를 내려보자.

$DP[i][j]$ : $i$층의 $j$번째 칸에 왔을때 오는 경로의 최댓값

이제 우리는 점화식을 세워줄 수 있다.

$DP[i][j] = max(DP[i-1][j],DP[i-1][j+1])+a[i][j]$

 

우리가 구하고자 하는 답은 $ \max(DP[n][i])$ $(1 \leq i \leq n)$ 이다.

 

점화식은 완성되었다. 이제 문제를 풀어보자!

 

#include <bits/stdc++.h>
using namespace std;

int main() {
    int n,d[501][501],a[501][501];
    cin >> n;
    for(int i = 1;i <= n;i++) {
        for(int j = 1;j <= i;j++) {
            cin >> a[i][j];
        }
    }
    d[1][1] = a[1][1];
    for(int i = 2;i <= n;i++) {
        for(int j = 1;j <= i;j++) {
            if(j == 1) d[i][j] = d[i-1][j] + a[i][j];
            else if(j == i) d[i][j] = d[i-1][j-1] + a[i][j];
            else d[i][j] = max(d[i-1][j],d[i-1][j-1]) + a[i][j];
        }
    }
    int ans = d[n][1];
    for(int i = 2;i <= n;i++) {
        ans = max(ans,d[n][i]);
    }
    cout << ans;
}

 

E - 사회망 서비스(SNS)

2533번: 사회망 서비스(SNS)

다이나믹으로도 풀 수 있지만 여기서는 그리디 풀이를 소개하려 한다.

몇가지 생각을 해볼 수 가 있다.

1. 리프 노드는 고를 필요가 없다.

2. 나의 자식중 한명이라도 안골랐으면 자신은 골라야 한다.

이 2개를 가지고 문제를 풀 수 있다.

 

증명은 스스로 생각해 보시기 바란다.

 

#include <bits/stdc++.h>
using namespace std;
int c[1000005],n,ans;
vector <int> v[1000005];
 
int dfs(int x) {
    c[x] = 1;
    int rv;
    int ea = 0;
    for(int i = 0;i < v[x].size();i++) {
        if(c[v[x][i]]) continue;
        rv = dfs(v[x][i]);
        if(rv == 0) ea = 1;
    }
    ans += ea;
    return ea;
}
 
int main() {
    scanf("%d",&n);
    for(int i = 1;i <= n-1;i++) {
        int x,y;
        scanf("%d %d", &x, &y);
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dfs(1);
    printf("%d",ans);
    return 0;
}

 

F - 연세워터파크

15678번: 연세워터파크

이 문제를 풀려면 $deque$를 이용하는 동적 계획법을 알아야 한다.

모른다면 이 글을 읽고 오기 바란다.

 

왔다갔다 하는것 보다는 1번부터 그냥 오른쪽으로 가면 되기 때문에 우리는 문제를 변형할 수 있다.

이제 $DP$ 테이블의 정의를 내려보자.

$DP[i]$ : $i$번째 징검다리에서 끝났을때의 최대 점수

그러면 점화식은 이렇게 나온다.

$DP[i] = max(DP[j])+a[i]$ $(i-D \leq j < i)$

 

길이가 $D$인것만 보면 되기 때문에

우리는 최근 $D$개의 $DP$ 테이블의 값을 알고 있으면 된다.

이제 그걸 빨리 처리하는게 $deque$를 이용한 동적계획법 이다.

 

최근에 나온게 나중에 나온것 보다 더 $DP$ 값이 크다면 나중의 것은 필요가 없어진다.

그래서 이 $deque$가 필요한 것이다.

그런건 $pop$_$front$를 해주면 된다. 

 

우리가 구해야 할 답은 $max(DP[i])$ $(1 \leq i \leq n)$ 이다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,D;
ll ans,d[100005],a[100005];
deque <pair<ll,ll>> dq;

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> D;
	for(int i = 1;i <= n;i++) cin >> a[i];
	d[1] = a[1];
	dq.push_back({1,d[1]});
	ans = d[1];
	for(int i = 2;i <= n;i++) {
		while(!dq.empty()&&dq.front().first < i-D) dq.pop_front();
		d[i] = max(a[i],dq.front().second+a[i]);
		ans = max(ans,d[i]);
		while(!dq.empty()&&dq.back().second < d[i]) dq.pop_back();
		dq.push_back({i,d[i]});
	}
	cout << ans;
}

 

G - 트리와 색깔

15899번: 트리와 색깔

알고리즘 : $Euler$ $Tour$ $Trick$, $Merge$ $Sort$ $Tree$

오일러 투어 트릭으로 트리를 일자로 펴줄 수 있다.

이제 펴진 트리를 가지고 머지 소트 트리에 색깔을 $insert$ 해줄 수 있다.

구간에 포함됬을때, $lower$_$bound$로 색깔이 $c$이하인 수의 개수를 구할 수 있다.

솔직히 이게 끝이다.

 

딱히 아이디어같은게 필요없는 문제다.

그냥 알고리즘을 알아야 하는 문제다.

 

머지 소트 트리를 짤때 그냥 $std::sort$ 를 쓰면 $O(Nlog^{2}N)$인데

머지 소트 할때 처럼 소팅을 하면 $O(NlogN)$의 시간으로 줄일 수 있다.

쿼리 부분에는 구간 찾기 : $logN$, $lower$_$bound$ : $logN$ 으로

총 시간 복잡도는 $O(NlogN+Qlog^{2}N)$이 된다.

 

#include <bits/stdc++.h>
using namespace std;
int n,q,m,go;
int a[200005],co[200005],in[200005],out[200005],c[200005];
vector <int> v[200005];
vector <int> t[800005];

void dfs(int x) {
	if(c[x]) return;
	c[x] = 1;
	in[x] = ++go;
	a[go] = co[x];
	for(int i : v[x]) dfs(i);
	out[x] = go;
}

void build(int x,int l,int r) {
	if(l == r) {
		t[x].push_back(a[l]);
		return;
	}
	int mid = (l+r) >> 1;
	build(x*2,l,mid),build(x*2+1,mid+1,r);
    int lg = 0,rg = 0;
    while(lg < t[x*2].size()&&rg < t[x*2+1].size()) {
        if(t[x*2][lg] < t[x*2+1][rg]) t[x].push_back(t[x*2][lg++]);
        else t[x].push_back(t[x*2+1][rg++]);
    }
    while(lg < t[x*2].size()) t[x].push_back(t[x*2][lg++]);
    while(rg < t[x*2+1].size()) t[x].push_back(t[x*2+1][rg++]);
}

int query(int x,int l,int r,int rl,int rr,int val) {
	if(rl <= l&&r <= rr) return upper_bound(t[x].begin(),t[x].end(),val)-t[x].begin();
	if(l > rr||r < rl) return 0;
	int mid = (l + r) >> 1;
	return query(x*2,l,mid,rl,rr,val)+query(x*2+1,mid+1,r,rl,rr,val);
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n >> q >> m;
	for(int i = 1;i <= n;i++) cin >> co[i];
	int x,y;
	for(int i = 1;i <= n-1;i++) {
		cin >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1);
	build(1,1,n);
	int ans = 0;
	while(q--) {
		cin >> x >> y;
		ans += query(1,1,n,in[x],out[x],y);
		ans %= 1000000007;
	}
	cout << ans;
	return 0;
}

 

H - 라면 사기 (Small)

18185번: 라면 사기 (Small)

알고리즘 : 그리디

1개짜리 2개 사는 것보단 2개짜리 1개 사는 것이 났고

1개짜리 3개 사는 것보다 1개짜리 1개+2개짜리 1개 사는것이 났고

1개짜리 1개+2개짜리 1개 사는 것보다 3개짜리 1개 사는것이 났다.

 

우리는 라면이 남을때마다 최대한 높은 묶음으로 올리면 된다는 것을 알 수 있다.

배열을 3개 잡아준다.

$g1[i]$ : 1개짜리를 $i$에 놓을때 남는 라면 개수

$g2[i]$ : 2개짜리를 $i$, $i+1$에 놓을때 남는 라면 개수

$g3[i]$ : 3개짜리를 $i$, $i+1$, $i+2$에 놓을때 남는 라면 개수

그러면 $g1[i]$에서 1개, $g1[i-1]$에서 1개를 가지고 $g2[i-1]$에 한개를 만들 수 있다.

$g1[i]$에서 1개, $g2[i-2]$에서 1개를 가지고 $g3[i-2]$ 한개를 만들 수 있다.

우리는 이짓거리를 $N$번 반복하면 답을 구할 수 있다.

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,b,c;
ll a[10005];
ll g1[10005],g2[10005],g3[10005];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	cin >> n;
	b = 3, c = 2;
	ll ans = 0,sum = 0;
	for(int i = 1;i <= n;i++) {
		cin >> a[i];
	}
	ll sum1 = 0,sum2 = 0,sum3 = 0;
	for(int i = 1;i <= n;i++) {
		g1[i] = a[i];
		if(g1[i-1] > 0) {
			ll tmp = min(g1[i],g1[i-1]);
			g2[i-1] += tmp;
			g1[i] -= tmp;
			g1[i-1] -= tmp;
		}
		if(g2[i-2] > 0) {
			ll tmp = min(g1[i],g2[i-2]);
			g3[i-2] += tmp;
			g1[i] -= tmp;
			g2[i-2] -= tmp;
		}
	}
	for(int i = 1;i <= n;i++) {
		sum1 += g1[i];
		sum2 += g2[i];
		sum3 += g3[i];
	}
	cout << sum1*b+sum2*(b+c)+sum3*(b+2*c);
	return 0;
}

 

I - 라면 사기 (Large)

18186번: 라면 사기 (Large)

라면 사기 (Small)이랑 비슷하지만 케이스 분류를 해야 한다.

이건 독자들에게 숙제로 남긴다.