중급반 2주차 풀이 - 그리디, DP, 분할 정복

A. [1931] 회의실 배정 (Silver II)

가장 빨리 끝나는 회의를 진행하면 됩니다. 이러면 선택의 폭이 더 넓기 때문에, 최적해가 잘 구해집니다.

주의할 점은, 가장 빨리 끝나는 회의가 여러개라면, '시작 시간이 가장 빠른 회의'를 선택해야 합니다.

이는 [12, 12], [10, 12] 같은 경우를 잘 처리하기 위한 추가 작업입니다.

(만약 저 순서대로 저장되었다면 [12, 12]를 선택 → 12시 이후의 회의가 없음 → 종료 → 출력 = 1이 됩니다.)

 

시간복잡도는 \( O(N \log N) \)입니다.

pl2 arr[100020];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i].fr >> arr[i].sc; }
	sort(arr+1, arr+n+1, [](pl2 a, pl2 b){
		if (a.sc != b.sc){ return a.sc < b.sc; }
		return a.fr < b.fr;
	});
	int ans = 0; ll ptr = 0;
	for (int i = 1; i <= n; i++){
		if (ptr < arr[i].fr){ continue; }
		ans += 1; ptr = arr[i].fr;
	}
	cout << ans;
}

B. [1026] 보물 (Silver IV)

직관적으로도 구할 수 있습니다. B를 오름차순으로 만들면, A를 내림차순으로 맞춰주면 됩니다.

 

+ \( A_{0} < A_{1}, B_{0} < B_{1} \)이라면 \( (A_{1} - A_{0})(B_{1} - B_{0}) > 0 \)이고, 식을 풀어주고 이항하면 \( A_{1}B_{1} + A_{0}B_{0} > A_{1}B_{0} + A_{0}B_{1} \)입니다.

즉, 오름차순/내림차순이 안 맞는 두 원소가 있다면, 맞게 고쳐주는 게 최적입니다.

 

시간복잡도는 \( O(N \log N) \)입니다.

int arr[60], brr[60];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	for (int i = 1; i <= n; i++){ cin >> brr[i]; }
	sort(arr+1, arr+n+1); sort(brr+1, brr+n+1, [](int a, int b){ return a > b; });
	int ans = 0;
	for (int i = 1; i <= n; i++){ ans += arr[i]*brr[i]; }
	cout << ans;
}

C. [1463] 1로 만들기 (Silver III)

다음 DP를 정의해볼 수 있습니다.

\( DP_{i} := \) \( i \)를 \( 1 \)로 만드는 데 필요한 연산의 횟수

이제, 문제에서 정의한 3가지 연산을 식으로 만들어봅시다.

1. 3으로 나누어떨어진다면, 3으로 나눈다: \( DP_{i/3} + 1 \)

2. 2로 나누어떨어진다면, 2로 나눈다: \( DP_{i/2} + 1 \)

3. 1을 뺀다: \( DP_{i-1} + 1 \)

 

셋 중 가장 빠른 길을 선택해야 하니, 셋 중 최솟값을 구해주면 됩니다.

첫 2가지 연산은 조건이 달려있음에 주의하세요.

 

시간복잡도는 \( O(N) \)입니다.

int dp[1000020];

void Main(){
	int n; cin >> 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); }
	}
	cout << dp[n];
}

D. [1149] RGB거리 (Silver I)

DP같긴 한데, \( i \)번째 집까지의 최솟값만으로는 제대로 구할 수 없을 것 같습니다.

답을 구하기 위해서는 색깔의 정보가 추가적으로 필요할 것 같으니, 아래와 같이 DP를 정의해봅시다.

\( DP_{i, c} := \) \( i \)번째 집까지만 볼 때, 마지막 집을 \( c \)번 색으로 칠할 때의 최소 비용

 

그러면 점화식도 잘 세울 수 있게 됩니다. \( DP_{i, c} = \text{min}_{c \neq c'} DP_{i-1, c'} + A_{i, c} \)

즉, \( i-1 \)번 집을 \( c' \)번 색으로 칠한 뒤 \( i \)번 집을 \( c (\neq c') \)번 색으로 칠하는 것입니다.

 

초항은 \( DP_{1, c} = A_{1, c} \)이고, 답은 \( \min DP_{N, c} \)가 됩니다.

int arr[1020][3], dp[1020][3];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i][0] >> arr[i][1] >> arr[i][2]; }
	dp[1][0] = arr[1][0]; dp[1][1] = arr[1][1]; dp[1][2] = arr[1][2];
	for (int i = 2; i <= n; i++){
		dp[i][0] = min(dp[i-1][1], dp[i-1][2]) + arr[i][0];
		dp[i][1] = min(dp[i-1][0], dp[i-1][2]) + arr[i][1];
		dp[i][2] = min(dp[i-1][0], dp[i-1][1]) + arr[i][2];
	}
	cout << min({ dp[n][0], dp[n][1], dp[n][2] });
}

E. [2096] 내려가기 (Gold IV)

RGB거리와 비슷한 방식으로 풀면 됩니다.

 

설명은 최대 점수만 하겠습니다. 최소 점수는 max 대신 min으로 구해주면 됩니다.

\( MX_{i, j} := \) \( i \)번 줄의 \( j \)번 위치에서 얻을 수 있는 최대 점수 로 정의한 뒤,

\( MX_{i, j} = \max_{|j-k| \le 1} MX_{i-1, k} + A_{i, j} \)로 값을 구해주면 됩니다.

그러니 이렇게 구현해서 내면 Memory Limit Exceeded (메모리 초과)가 뜹니다.

 

이 문제는 메모리 제한이 4MB밖에 안 되기 때문에, 저장하는 값을 줄여야 합니다.

여기서, DP 점화식을 보고 이런 생각을 해볼 수 있습니다.

'어차피 DP는 \( i-1 \)번 줄만 참조하는데, 그럼 그 이전 줄은 날려도 되지 않을까?'

결론부터 말하자면, 날릴 수 있습니다. 사실 이건 Sliding Window라는 이름도 붙어 있는 잘 알려진 테크닉입니다.

 

그러니 DP를 계산할 때 \( i-1 \)번째 줄에 있는 값만 저장하도록 바꿔주면 됩니다.

+ \( A_{i, j} \) 역시 \( i \)번째 줄만 남길 수 있습니다. 이는 입력과 DP 계산을 동시에 해주면 됩니다.

시간복잡도는 \( O(N) \)이고, 공간복잡도는 \( O(1) \)입니다.

int arr[3], mx[3], mn[3];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){
		for (int j = 0; j < 3; j++){ cin >> arr[j]; }
		int a = mx[0], b = mx[1], c = mx[2];
		mx[0] = max(a, b) + arr[0];
		mx[1] = max({a, b, c}) + arr[1];
		mx[2] = max(b, c) + arr[2];
		a = mn[0]; b = mn[1]; c = mn[2];
		mn[0] = min(a, b) + arr[0];
		mn[1] = min({a, b, c}) + arr[1];
		mn[2] = min(b, c) + arr[2];
	}
	cout << max({ mx[0], mx[1], mx[2] }) << ' ' << min({ mn[0], mn[1], mn[2] });
}

F. [1351] 무한 수열 (Gold IV)

점화식도 나와있으니, DP를 그대로 짜서 내면 Time Limit Exceeded (시간 초과)를 받습니다.

\( N \le 10^{12} \)라는 조건 때문인데, 점화식에 나눗셈이 들어가는 걸 보면 왠지 많은 값들이 \( A_{N} \)을 계산하는데 필요하지 않을 것 같은 느낌이 듭니다.

 

그러니, Top-Down 방식으로 재귀형 DP를 호출해주면 맞았습니다를 받을 수 있습니다.

메모이제이션은 treemap (예: std::map)이나 hashmap (예: Python dict) 중 편한 걸로 써주면 됩니다.

 

+ \( \lfloor \lfloor x/P \rfloor / Q \rfloor = \lfloor \lfloor x/Q \rfloor / P \rfloor \)임을 사용하면, 실제로 탐색하는 위치는 최대 \( O(\log^{2} N) \)개 정도임을 유추할 수 있으니, treemap을 사용한다면 \( O(\log^{2} N \log \log^{2} N) \)이라는 시간복잡도를 얻을 수 있습니다.

ll p, q;
map<ll, int> dp;
ll dpf(ll x){
	if (dp.count(x)){ return dp[x]; }
	return dpf(x/p) + dpf(x/q);
}

void Main(){
	dp[0] = 1;
	ll n; cin >> n >> p >> q;
	cout << dpf(n);
}

G. [1629] 곱셈 (Silver I)

\( A \)를 \( B \)번 곱하면 Time Limit Exceeded (시간 초과)입니다.

대신 "Exponentiation By Squaring (분할 정복을 이용한 거듭제곱)"이라는, 더 빠른 방식을 사용해야 합니다.

 

위 방식을 요약하면, \( A^B \)를 아래와 같은 방식으로 재귀적으로 구하는 방식입니다.

\[ A^{B} = \begin{cases} 1 & \text{if }B = 0 \\ A^{\lfloor B/2 \rfloor} \times A^{\lfloor B/2 \rfloor} & \text{if }B \text{ is even} \\ A^{\lfloor B/2 \rfloor} \times A^{\lfloor B/2 \rfloor} \times A & \text{if }B \text{ is odd} \end{cases} \]

 

+ 이 테크닉의 자세한 설명 (및 비트연산을 사용한 구현)은 https://blog.naver.com/hibye1217/222645003089에서 볼 수 있습니다.

 

그러니 위 방식을 사용해서 \( A^B \mod C \)를 빠르게 구해주면 됩니다.

시간복잡도는 \( O(\log B) \)입니다.

void Main(){
	ll a, b, c; cin >> a >> b >> c;
	ll res = 1, mul = a, bit = b;
	while (bit){
		if (bit & 1){ res = res*mul % c; }
		mul = mul*mul % c; bit >>= 1;
	}
	cout << res;
}

H. [1517] 버블 소트 (Platinum V)

뜬금없지만, Merge Sort를 들고 와봅시다.

Merge Sort에서 1회 Merge를 하는 과정을 잘 생각해보면, Bubble Sort의 swap이 여러 번 일어나는 것이랑 같음을 볼 수 있습니다.

그러니까 수열을 Merge Sort하면서 생기는 swap의 횟수를 세주면 됩니다.

시간복잡도는 \( O(N \log N) \)입니다.

ll arr[500020], tmp[500020];

ll ans = 0;
void f(int st, int ed){ int mid = st+ed >> 1;
	if (st == ed){ return; }
	f(st, mid); f(mid+1, ed);
	int p1 = st, p2 = mid+1, ptr = st;
	while (p1 <= mid || p2 <= ed){
		if (p1 > mid){ tmp[ptr] = arr[p2]; p2 += 1; ptr += 1; }
		else if (p2 > ed){ tmp[ptr] = arr[p1]; p1 += 1; ptr += 1; }
		else{
			if (arr[p1] <= arr[p2]){ tmp[ptr] = arr[p1]; p1 += 1; ptr += 1; }
			else{
				ans += mid-p1 + 1;
				tmp[ptr] = arr[p2]; p2 += 1; ptr += 1;
			}
		}
	}
	for (int i = st; i <= ed; i++){ arr[i] = tmp[i]; }
}

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	f(1, n);
	cout << ans;
}

+ 다른 풀이: Bubble Sort의 특성상, swap을 1번 하면 수열의 Inversion Count가 1 감소합니다.

그러니, 초기 상태의 수열의 Inversion Count = 필요한 swap 횟수 가 됩니다.

수열의 Inversion Count 구하기는 Well-known이니, 바로 구현해주면 됩니다.

시간복잡도는 \( O(N \log N) \)입니다.

ll arr[500020];
map<ll, int> cvt; set<ll> cs; int cc = 0;
const int N = 524288; int fen[524290];
void upd(int pos, int val){
	for (int i = pos; i < N; i += i&-i){ fen[i] += val; }
}
int qry(int pos){
	int res = 0;
	for (int i = pos; i > 0; i -= i&-i){ res += fen[i]; }
	return res;
}

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; cs.insert(arr[i]); }
	for (ll x : cs){ cc += 1; cvt[x] = cc; }
	for (int i = 1; i <= n; i++){ arr[i] = cvt[ arr[i] ]; }
	ll ans = 0;
	for (int i = n; i >= 1; i--){
		ans += qry(arr[i]-1); upd(arr[i], 1);
	}
	cout << ans;
}

1. [2630] 색종이 만들기 (Silver III)

\( N \times N \) 크기의 종이를 봅시다. 만약 이 종이가 하나의 색으로만 칠해져있다면, \( N \times N \) 크기의 종이 하나로 처리할 수 있습니다.

그렇지 않다면, 4개의 \( N/2 \times N/2 \) 크기의 종이로 나눠서 풀어야 합니다.

시간복잡도는 \( N^2 \log N \)입니다.

int arr[130][130];

int ans0 = 0, ans1 = 0;
void f(int sty, int edy, int stx, int edx){
	int midy = sty+edy >> 1, midx = stx+edx >> 1;
	bool chk0 = 0, chk1 = 0;
	for (int y = sty; y <= edy; y++){
		for (int x = stx; x <= edx; x++){
			if (arr[y][x] == 0){ chk0 = 1; }
			if (arr[y][x] == 1){ chk1 = 1; }
		}
	}
	if (chk0 && !chk1){ ans0 += 1; return; }
	if (chk1 && !chk0){ ans1 += 1; return; }
	f(sty, midy, stx, midx); f(sty, midy, midx+1, edx);
	f(midy+1, edy, stx, midx); f(midy+1, edy, midx+1, edx);
}

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){ cin >> arr[i][j]; }
	}
	f(1, n, 1, n);
	cout << ans0 << endl << ans1 << endl;
}

2. [10830] 행렬 제곱 (Gold IV)

아까 위에서 풀었던 G. [1629] 곱셈 문제를 기억하나요? 똑같이 하면 됩니다.

 

올리기 귀찮은 분들을 위해, \( A^B \)의 계산 방식은 다음과 같습니다.

\[ A^{B} = \begin{cases} 1 & \text{if }B = 0 \\ A^{\lfloor B/2 \rfloor} \times A^{\lfloor B/2 \rfloor} & \text{if }B \text{ is even} \\ A^{\lfloor B/2 \rfloor} \times A^{\lfloor B/2 \rfloor} \times A & \text{if }B \text{ is odd} \end{cases} \]

 

유일한 차이점은 A가 행렬이라는 점인데, 이 덕분에 행렬 곱셈을 구현해야 합니다.

행렬 곱셈은 \( O(N^3) \)에 구현할 수 있으므로, \( O(N^3 \log B) \)의 시간복잡도로 문제를 해결할 수 있습니다.

const int mod = 1000;

int arr[10][10];
int res[10][10], mul[10][10], tmp[10][10];

void Main(){
	int n; ll b; cin >> n >> b;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){ cin >> arr[i][j]; }
	}
	ll bit = b;
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){
			res[i][j] = i==j;
			mul[i][j] = arr[i][j];
		}
	}
	while (bit){
		if (bit & 1){
			memset(tmp, 0, sizeof(tmp));
			for (int i = 1; i <= n; i++){
				for (int j = 1; j <= n; j++){
					for (int k = 1; k <= n; k++){
						tmp[i][j] += res[i][k]*mul[k][j] % mod; tmp[i][j] %= mod;
					}
				}
			}
			for (int i = 1; i <= n; i++){
				for (int j = 1; j <= n; j++){ res[i][j] = tmp[i][j]; }
			}
		}
		memset(tmp, 0, sizeof(tmp));
		for (int i = 1; i <= n; i++){
			for (int j = 1; j <= n; j++){
				for (int k = 1; k <= n; k++){
					tmp[i][j] += mul[i][k]*mul[k][j] % mod; tmp[i][j] %= mod;
				}
			}
		}
		for (int i = 1; i <= n; i++){
			for (int j = 1; j <= n; j++){ mul[i][j] = tmp[i][j]; }
		}
		bit >>= 1;
	}
	for (int i = 1; i <= n; i++){
		for (int j = 1; j <= n; j++){ cout << res[i][j] << ' '; }
		cout << endl;
	}
}

3. [6549] 히스토그램에서 가장 큰 직사각형 (Platinum V)

\( [1, N] \) 구간에서 분할 정복으로 문제를 해결해봅시다.

 

편의상 중간점을 \( M = (N+1)/2 \)라고 하겠습니다.

그럼 문제의 답은 아래 3+1가지 경우 중 최솟값이 됩니다.

+. \( N = 1 \)이라면, \( A_{1} \)이 답이다.

1. \( [1, M] \) 구간에서의 답

2. \( (M+1, N] \) 구간에서의 답

3. \( A_{M} \)과 \( A_{M+1} \)을 지나는 답

 

1번과 2번 경우는 분할 정복이 알아서 처리해줄테니, 3번 경우를 생각해봅시다.

우선 어차피 답이 \( [M, M+1] \)를 포함해야 하니, \( [M, M+1] \) 구간에서 시작한 뒤, 다음을 분석해봅시다.

 

\( [st, ed] \) 구간을 답이라고 보고 있을 때, 다음 답의 후보는 \( [st-1, ed] \)와 \( [st, ed+1] \) 2가지 경우가 있습니다. 둘 중에 더 좋은 답은 무엇일까요?

두 경우 모두 가로의 길이가 동일하므로, 세로의 길이만으로 비교해야 한다는 건 자명합니다. 그러니, \( A_{st-1} \)와 \( A_{ed+1} \) 중 더 큰 쪽으로 구간을 늘려주면 됩니다.

 

[TODO: 구간 길이를 줄일 필요가 없는 이유 증명]

 

이렇게 하면 3번 경우는 \( O(N) \)에 계산할 수 있습니다.

 

그러므로, 연산 횟수를 계산해보면 \( T(N) = 2T(N/2) + O(N) \)이니 시간복잡도는 마스터 정리에 의해 \( O(N \log N) \)이 됩니다.

ll arr[100020];
ll f(int st, int ed){
	if (st == ed){ return arr[st]; }
	int mid = st+ed >> 1;
	ll ans = max( f(st, mid), f(mid+1, ed) );
	int p1 = mid-1, p2 = mid+2; ll res = min(arr[mid], arr[mid+1]);
	ans = max(ans, 2*res);
	while (st <= p1 || p2 <= ed){
		if (st > p1){ res = min(res, arr[p2]); p2 += 1; ans = max(ans, (p2-p1-1)*res); }
		else if (p2 > ed){ res = min(res, arr[p1]); p1 -= 1; ans = max(ans, (p2-p1-1)*res); }
		else{
			if (arr[p1] >= arr[p2]){ res = min(res, arr[p1]); p1 -= 1; ans = max(ans, (p2-p1-1)*res); }
			else{ res = min(res, arr[p2]); p2 += 1; ans = max(ans, (p2-p1-1)*res); }
		}
	}
	return ans;
}

void Main(){
	while (1){
		int n; cin >> n;
		if (n == 0){ return; }
		for (int i = 1; i <= n; i++){ cin >> arr[i]; }
		cout << f(1, n) << endl;
	}
}

4. [2839] 설탕 배달 (Bronze I)

사실 브루트 포스 문제입니다.

문제를 수학적으로 표현하자면, \( 3x + 5y = N \)를 만족하는 음이 아닌 정수쌍 \( (x, y) \) 중 \( x+y \)의 최솟값을 찾으면 되는데, 만약 \( x \)를 고정한다면 이에 따라 \( y \) 역시 고정이 되고, \( N \le 5000 \)이기 때문에 \( x \)를 다 돌려도 됩니다.

시간복잡도는 \( O(N) \)입니다.

 

+ 그리디하게 풀고 싶다면 아래와 같이 하면 됩니다.

\( 3x + 5y = N \)에서 \( x+y \)를 최소화하려면, \( y \)를 최대화하는 게 최적임은 자명합니다.

즉, 가능한 \( y \)값을 큰 값부터 돌리다가, 처음으로 가능한 \( x \)가 나오면 바로 합치고 출력하면 됩니다.

이렇게 해주면 최대 3번의 시도 이내에 답을 발견할 수 있으므로 시간복잡도가 \( O(1) \)이 됩니다. [TODO: 코드 작성 및 증명]

const int INF = 1e9;

void Main(){
	int n; cin >> n;
	int ans = INF;
	for (int x = 1; 3*x <= n; x++){
		int y = n - 3*x;
		if (y%5 != 0){ continue; } y /= 5;
		ans = min(ans, x+y);
	}
	if (ans == INF){ cout << -1; } else{ cout << ans; }
}

5. [11047] 동전 0 (Silver III)

이 문제가 쉬운 이유는, \( A_{i} \)는 \( A_{i-1} \)의 배수이기 때문입니다.

즉, \( K \)원을 \( A_{1} = 1 \)으로 나타낸 뒤, 되는대로 \( A_{2} \)로 환전하고, 그걸 되는대로 \( A_{3} \)로 환전하고, ..., 그걸 되는대로 \( A_{N} \)으로 환전하는 그리디를 사용할 수 있습니다.

이와 동일한 방식으로는, \( A_{N} \)으로 되는대로 채운 뒤, \( A_{N-1} \)으로 되는대로 채우고, ..., \( A_{1} = 1 \)로 되는대로 채우는 방식의 그리디를 사용할 수 있습니다.

시간복잡도는 \( O(N) \)입니다.

int arr[20];

void Main(){
	int n, k; cin >> n >> k;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; }
	int ans = 0;
	for (int i = n; i >= 1; i--){ ans += k/arr[i]; k %= arr[i]; }
	cout << ans;
}

6. [1541] 잃어버린 괄호 (Silver II)

-를 기준으로 괄호를 묶어주면 됩니다.

즉, A+B - C+D+E+F - G+H - I - J+K 같은 식이 주어졌으면, (A+B) - (C+D+E+F) - (G+H) - (I) - (J+K)로 묶어줘야 합니다.

이게 최적임은 어렵지 않게 볼 수 있는데, 괄호를 풀어주면 A와 B 빼고 모두 -가 되는 걸 볼 수 있고, A와 B는 앞에 -가 없어서 괄호만으로 -를 만들어낼 수 없기 때문에 최소가 나오게 됩니다.

 

+ 보통 PS, CP에서는 속도가 빠른 C++을 주로 사용하지만, 구현량을 가늠할 수 없을 때 (또는 BigInt가 필요할 때)를 대비해 Python도 어느 정도 알아두는 걸 추천합니다.

inp = input().split('-')
arr = []
for s in inp:
    arr.append(0); val = 0
    for ch in s:
        if '0' <= ch <= '9':
            val *= 10; val += ord(ch)-48
        if ch == '+':
            arr[-1] += val; val = 0
    arr[-1] += val
ans = arr[0]
for i in range(1, len(arr)): ans -= arr[i]
print(ans)

7. [19539] 사과나무 (Silver I)

매일 모든 나무의 크기의 합은 3씩 증가합니다.

그러니, 최종 배치에서의 모든 나무의 크기의 합은 3의 배수여야 하겠죠.

 

이제부터는 위 조건이 만족된다고 하고, 이 때의 높이의 합을 \( H \)라고 합시다.

우리가 알고 싶은 건 \( H/3 \)개의 +2 물뿌리개를 적용시킬 수 있는가이고, 이는 크기가 2 이상인 아무 나무에 +2를 뿌리는 방식으로 확인할 수 있습니다.

나머지 \( H - 2H / 3 = H/3 \)개의 +1 물뿌리개는 남은 곳에 뿌려주면 됩니다.

 

위 두 조건을 식으로 쓰면 \( \sum_{i=1}^{N} h_{i} \equiv 0 \mod 3 \)과 \( \sum_{i=1}^{N} \lfloor h_{i}/2 \rfloor \ge H/3 \)이니, 이를 확인해주면 됩니다.

ll arr[100020];

void Main(){
	int n; cin >> n;
	ll sum = 0;
	for (int i = 1; i <= n; i++){ cin >> arr[i]; sum += arr[i]; }
	if (sum%3 != 0){ cout << "NO"; return; } sum /= 3;
	ll cnt = 0;
	for (int i = 1; i <= n; i++){ cnt += arr[i]/2; }
	cout << (cnt >= sum ? "YES" : "NO");
}

8. [17626] Four Squares (Silver IV)

간단한 DP를 세워봅시다.

\( DP_{i} := \) \( i \)를 나타내는데 필요한 제곱수의 최소 개수

점화식은 제곱수 하나를 더한 뒤 남은 건 DP에 맡기는 방식으로 구해줄 수 있습니다.

\( DP_{i} = \min_{k^2 \le i} DP_{i-k^2} + 1 \)

 

초항은 \( DP_{0} = 0 \)이고, 문제의 답은 \( DP_{N} \)입니다.

시간복잡도는 \( O(N \sqrt{N}) \)입니다.

int dp[50020];

void Main(){
	int n; cin >> n;
	dp[0] = 0;
	for (int i = 1; i <= n; i++){
		dp[i] = 4;
		for (int k = 1; k*k <= i; k++){ dp[i] = min(dp[i], dp[i-k*k] + 1); }
	}
	cout << dp[n];
}

9. [11726] 2×n 타일링 (Silver III)

간단한 DP를 세워봅시다.

\( DP_{i} := \) \( 2 \times i \) 크기의 직사각형을 채우는 경우의 수

 

이제 이 타일들을 채우는 방법을 생각해봅시다. 정확히는, 맨 오른쪽에 타일을 하나하나 놓아봅시다.

1. \( 2 \times 1 \) 타일로 채운다: 맨 오른쪽에 \( 2 \times 1 \) 타일을 하나 놓고, 나머지 \( 2 \times (i-1) \) 크기를 채우면 됩니다.

2. \( 1 \times 2 \) 타일로 채운다: 맨 오른쪽에 \( 1 \times 2 \) 타일을 놓아야 하는데, 2개를 위-아래로 같이 놓아야 \( 2 \times N \) 타일링이 가능해집니다. 그러니 타일을 2개 놓고 나머지 \( 2 \times (i-2) \) 크기를 채우면 됩니다.

두 경우를 합해서 점화식으로 표현하면 \( DP_{i} = DP_{i-1} + DP_{i-2} \)가 됩니다.

 

초항은 \( DP_{1} = 1 \), \( DP_{2} = 2 \)이고, 답은 \( DP_{N} \)입니다.

시간복잡도는 \( O(N) \)입니다.

const int mod = 10007;
int dp[1020];

void Main(){
	int n; cin >> n;
	dp[1] = 1; dp[2] = 2;
	for (int i = 3; i <= n; i++){ dp[i] = (dp[i-1] + dp[i-2]) % mod; }
	cout << dp[n];
}

10. [17404] RGB거리 2 (Gold IV)

RGB 거리에서 정의했던 DP는 \( DP_{i, c} := \) \( i \)번째 집까지만 볼 때, 마지막 집을 \( c \)번 색으로 칠할 때의 최소 비용 이었습니다.

이제는 원형이니, DP식에 하나의 인자를 더 추가해봅시다.

\( DP_{i, c, k} := \) \( i \)번째 집까지만 볼 때, 마지막 집을 \( c \)번 색으로 칠하고, 첫 번째 집을 \( k \)번 색으로 칠할 때의 최소 비용

 

점화식에서 달라지는 점은 없습니다. 다만 \( k \)가 같은 상태로만 전파시켜야 할 뿐입니다.

\( DP_{i, c, k} = \text{min}_{c \neq c'} DP_{i-1, c', k} + A_{i, c} \)

초항과 답은 많이 달라집니다.

초항은 \( DP_{1, c, k} = A_{1, c} \text{ if } c = k \text{ else } \infty \)가 되고, 답은 \( c \neq k \)인 \( DP_{N, c, k} \) 중 최솟값이 됩니다.

시간복잡도는 상수가 약간 큰 \( O(N) \)입니다.

const int INF = 1e9;
int arr[1020][3];
int dp[1020][3][3];

void Main(){
	int n; cin >> n;
	for (int i = 1; i <= n; i++){ cin >> arr[i][0] >> arr[i][1] >> arr[i][2]; }
	for (int k = 0; k < 3; k++){
		dp[1][0][k] = dp[1][1][k] = dp[1][2][k] = INF;
		dp[1][k][k] = arr[1][k];
		for (int i = 2; i <= n; i++){
			dp[i][0][k] = min(dp[i-1][1][k], dp[i-1][2][k]) + arr[i][0];
			dp[i][1][k] = min(dp[i-1][0][k], dp[i-1][2][k]) + arr[i][1];
			dp[i][2][k] = min(dp[i-1][0][k], dp[i-1][1][k]) + arr[i][2];
		}
	}
	int mn = INF;
	for (int c = 0; c < 3; c++){
		for (int k = 0; k < 3; k++){
			if (c == k){ continue; }
			mn = min(mn, dp[n][c][k]);
		}
	}
	cout << mn;
}

11. [9251] LCS (Gold V)

입력받은 두 문자열을 \( S \)와 \( T \)라고 한 뒤, 다음 DP를 정의해봅시다.

\( DP_{i, j} := \) \( S \)의 첫 \( i \)글자와 \( T \)의 첫 \( j \)글자로 만들 수 있는 LCS의 길이

 

DP의 점화식은 다음과 같이 구할 수 있습니다.

1. \( S \)의 \( i-1 \)글자만으로 LCS 만들기: \( DP_{i-1, j} \)

2. \( T \)의 \( j-1 \)글자만으로 LCS 만들기: \( DP_{i, j-1} \)

3. \( S_{i} = T_{j} \)일 때, \( S \)의 \( i-1 \)글자와 \( T \)의 \( j-1 \)글자로 LCS를 만든 뒤 맨 뒤에 \( S_{i} \)를 붙이기: \( DP_{i-1, j-1} + 1 \)

 

초항은 \( DP_{i, 0} = DP_{0, j} = 0 \)이고, 답은 \( DP_{ \text{len}(S), \text{len}(T) } \)입니다.

시간복잡도는 \( O(|S| \cdot |T|) \)입니다.

int dp[1020][1020];

void Main(){
	string s1, s2; cin >> s1 >> s2;
	int l1 = s1.size(), l2 = s2.size(); s1 += " "; s2 += " ";
	for (int i = 1; i <= l1; i++){
		for (int j = 1; j <= l2; j++){
			dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
			if (s1[i] == s2[j]){ dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1); }
		}
	}
	cout << dp[l1][l2];
}

12. [1328] 고층 빌딩 (Platinum V)

편의상 높이가 \( h \)인 빌딩을 \( h \)번 빌딩이라고 하겠습니다.

우선 관측이 하나 필요합니다. "어느 방향에서 보든, 보이는 마지막 빌딩은 높이가 N인 빌딩이다."

이 관측을 토대로 하면, \( N \)번 빌딩을 기준으로 문제를 나눠볼 수 있습니다.

즉, \( N \)번 빌딩이 왼쪽에서부터 \( x \)번째에 존재할 때, (왼쪽에서 \( [1, x] \)번째 빌딩 중 \( L \)개를 보는 경우의 수) × (오른쪽에서 \( [x, N] \)번째 빌딩 중 \( R \)개를 보는 경우의 수)를 구하면 됩니다.

 

이제 DP를 세워봅시다.

\( DP_{i, j} := \) \( j \)개의 빌딩이 보이도록 \( i \)개의 빌딩을 세우는 경우의 수 라고 정의한 뒤, \( DP_{i, j} \)가 \ ( DP_{i+1, k} \)에 어떤 영향을 끼치는지 봅시다.

여기서 이런 생각을 해볼 수 있습니다. \( i+1 \)번 빌딩을 세우는 대신, \( 0 \)번 빌딩을 세운다면?

\( 0 \)번 빌딩이 보이기 위해서는 그 빌딩이 맨 앞에 존재해야 합니다. 그러므로 \( DP_{i+1, j+1} += DP_{i, j} \)가 됩니다.

다른 경우는, 맨 앞을 제외하고 \( i \)칸 중 한 곳에 빌딩을 넣는 경우로, 빌딩이 하나 추가되었지만 보이는 빌딩의 수는 변하지 않으니 \( DP_{i+1, j} = i \times DP_{i, j} \)가 됩니다.

이 점화식을 그대로 구현해주면 됩니다.

 

+ 겹치는 경우는 안 나오나요?
두 배열이 겹친다는 건, 0의 위치가 같고 다른 것도 같다는 것입니다.

즉, 원래 겹치는 상태가 있어야 새로 겹치는 상태가 만들어지는데, 초기 상태에 겹치는 상태가 없으니 나중 상태에도 겹치는 상태가 없게 됩니다.

 

초항은 \( DP_{0, 0} = 0 \)과 \( DP_{1, 1} = 1 \)이고, 문제의 답은 아래와 같습니다.

\( N \)번 빌딩을 위치 \( x \)에 설치할 때, (\( x-1 \)개의 빌딩 중 \( L-1 \)개의 빌딩을 보는 경우의 수) × (\( N-x \)개의 빌딩 중 \( R-1 \)개의 빌딩을 보는 경우의 수) × (왼쪽에 놓을 빌딩을 선택하는 경우의 수) = \( \sum_{x=L}^{N-R+1} DP_{x-1, L-1} \times DP_{N-x, R-1} \times {}_{N-1}C_{x-1} \)

 

시간복잡도는 \( O(N^2) \)으로, 제한으로 추정할 때 점화식에서 \( i+1 \)번 빌딩을 설치하면서 \( O(N^3) \)으로 푸는 게 정해인 것으로 추정됩니다.

const ll mod = 1e9 + 7;
ll dp[120][120], ncr[120][120];

void Main(){
	int n, l, r; cin >> n >> l >> r;
	for (int i = 0; i <= n; i++){
		for (int j = 0; j <= i; j++){
			if (j==0 || j==i){ ncr[i][j] = 1; }
			else{ ncr[i][j] = (ncr[i-1][j-1] + ncr[i-1][j]) % mod; }
		}
	}
	dp[0][0] = 1; dp[1][1] = 1;
	for (int i = 1; i < n; i++){
		for (int j = 1; j <= i; j++){
			dp[i+1][j+1] += dp[i][j]; dp[i+1][j+1] %= mod;
			dp[i+1][j] += dp[i][j]*i % mod; dp[i+1][j] %= mod;
		}
	}
	ll ans = 0;
	for (int x = l; x <= n-r+1; x++){
		ll res = ncr[n-1][x-1] * dp[x-1][l-1] % mod * dp[n-x][r-1] % mod;
		ans += res; ans %= mod;
	}
	cout << ans;
}