초급반 5주차 풀이 - DP, 시간복잡도

1. [2748] 피보나치 수 2 (Bronze I)

4주차에서 이미 풀어본 문제이지만, 다시 풀어보면서 시간복잡도를 분석해봅시다.

 

피보나치 수는 \( F_{N} = \begin{cases} 0 & \text{if } N = 0 \\ 1 & \text{if } N = 1 \\ F_{N-1} + F_{N-2} & \text{otherwise} \end{cases} \)입니다.

 

위 방식을 나이브한 재귀로 구현할 때의 시간복잡도는 어떻게 될까요?

결론만 말하자면, 나이브한 재귀로는 \( O(F_{N}) \)의 시간이 걸립니다.

\( F_{1} = 1 \)의 케이스까지 내려가야 답에 1이 더해지므로, 저 과정이 \( F_{N} \)번 반복되어야 우리가 원하는 답인 \( F_{N} \)이 나오겠죠.

그리고 위 시간복잡도에 문제의 최댓값인 \( N = 90 \)을 여기에 넣으면...

\( F_{90} = 2\,880\,067\,194\,370\,816\,120 \)라는, \( 10^8 \)회의 연산 = 1초 라는 관념에 들이밀지도 못할 정도의 큰 수가 나오게 됩니다.

 

그래서 위 과정을 '메모이제이션'을 사용해 최적화를 했습니다.

이제 메모이제이션을 했을 때의 시간을 보면, 각 항을 구할 때 이전 값을 1번씩 참조하게 됩니다.

그러니, \( N \)개의 항을 각각 \( O(1) \)의 시간에 참조 및 계산하므로 시간복잡도는 \( O(N) \)이 됩니다.

이제 여기에 \( N = 90 \)을 넣으면 \( N = 90 \)이므로 \( 10^8 \)회의 연산 = 1초 라는 관념에 잘 들어오는 값이 나오게 됩니다.

ll val[100];
ll f(int now){
	if (now <= 1){ return now; }
	if (val[now] != 0){ return val[now]; }
	return val[now] = f(now-1) + f(now-2);
}

void Main(){
	int n; scanf("%d", &n);
	printf("%lld", f(n));
}

2. [11051] 이항 계수 2 (Silver I)

이 문제도 4주차에서 풀어봤지만, 시간복잡도 분석을 위해 다시 풀어봅시다.

 

이 문제에서 나오는 상태는 \( {}_{n}C_{r} = DP_{n, r} = O(N^2) \)가지가 있습니다.

그리고 각 상태를 계산하는데 드는 비용은 \( O(1) \)개의 이전 상태 × \( O(1) \)회의 연산 = \( O(1) \)입니다.

즉, 시간복잡도는 \( O(N^2) \)이 됩니다.

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

void Main(){
	int n, r; scanf("%d %d", &n, &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]; }
			ncr[i][j] %= mod;
		}
	}
	printf("%d", ncr[n][r]);
}

3. [11053] 가장 긴 증가하는 부분 수열 (Silver II)

4주차의 [17626] Four Squares를 푸는 방식을 생각해봅시다.

이 때 저희는 \( DP_{N} := \) \( N \)을 만들기 위해 필요한 제곱수의 최소 개수 를 들고 왔습니다.

그러니, 이번에도 비슷한 방식으로

\( DP_{i} := \) \( i \)번째 수를 끝으로 하는 LIS의 최대 길이 를 정의해봅시다.

 

\( i \)번째 수를 끝으로 하는 LIS는, \( j \)번째 수를 끝으로 하는 LIS의 뒤에 \( i \)번째 수를 넣어서 만들 수 있습니다. 물론, LIS여야 하니 \( A_{j} < A_{i} \)여야 하죠.

그러니, 이 방식을 그대로 코드로 만들어주면 됩니다.

 

시간복잡도는 \( O(N) \)개의 상태 × \( O(N) \)개의 이전 상태 탐색 및 계산 = \( O(N^2) \)이므로, \( N = 1\,100 \rightarrow N^2 = 1\,000\,000 < 10^8 \)이니 충분히 빠르게 통과할 것이라고 생각할 수 있습니다.

#include <stdio.h>

int max(int a, int b){ return a>b ? a : b; }

int arr[1020], dp[1020];

void Main(){
	int n; scanf("%d", &n);
	for (int i = 1; i <= n; i++){ scanf("%d", &arr[i]); }
	for (int i = 1; i <= n; i++){
		dp[i] = 1;
		for (int j = 1; j < i; j++){
			if (arr[j] < arr[i]){ dp[i] = max(dp[i], dp[j] + 1); }
		}
		//printf("DP %d = %d\n", i, dp[i]);
	}
	int res = 0;
	for (int i = 1; i <= n; i++){ res = max(res, dp[i]); }
	printf("%d", res);
}

int main(){ Main(); }

4. [11727] 2×n 타일링 2 (Silver III)

\( DP_{N} := \) \( 2 \times N \)의 직사각형을 \( 1 \times 2 \), \( 2 \times 1 \), \( 2 \times 2 \)의 타일로 채우는 경우의 수 를 정의해봅시다.

이러면, \( 2 \times N \)을 채우는 경우는 아래 3가지 경우로 나눠볼 수 있습니다.

• \( 2 \times 1 \)의 타일을 쓰는 경우: 나머지 \( 2 \times (N-1) \) 크기의 직사각형을 추가로 채워야 합니다. \( DP_{N-1} \)가지의 경우가 있습니다.
• \( 1 \times 2 \)의 타일을 쓰는 경우: 이 타일을 위-아래로 2개 이어붙이는 경우밖에 없고, 나머지 \( 2 \ times (N-2) \)개의 직사각형을 추가로 채워야 합니다. \( DP_{N-2} \)가지 경우가 있습니다.
• \( 2 \times 2 \)의 타일을 쓰는 경우: 나머지 \( 2 \times (N-2) \) 크기의 직사각형을 추가로 채워야 합니다. \( DP_{N-2} \)가지의 경우가 있습니다.

위 경우들을 합해주면, 우리가 원하는 '모든 경우'들이 나오게 됩니다.

\( DP_{N} = \begin{cases} 1 & \text{if } N = 1 \\ 3 & \text{if } N = 2 \\ F_{N-1} + F_{N-2} + F_{N-2} = F_{N-1} + 2 F_{N-2} & \text{otherwise} \end{cases} \)

 

시간복잡도는 상태 개수 \( O(N) \) × 상태별 계산 횟수 \( O(1) \) = \( O(N) \)입니다.

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

void Main(){
	int n; scanf("%d", &n);
	dp[1] = 1; dp[2] = 3;
	for (int i = 3; i <= n; i++){ dp[i] = (dp[i-1] + 2*dp[i-2]) % mod; }
	printf("%d", dp[n]);
}

5. [9461] 파도반 수열 (Silver III)

도형을 주의깊게 보면 알겠지만, \( N \)번째 삼각형의 길이 = \( N-1 \)번째 삼각형의 길이 + \( N-5 \)번째 삼각형의 길이가 됨을 볼 수 있습니다.

그러니, \( DP_{N} := \) \( N \)번째 삼각형의 길이 로 정의하면

\( DP_{N} = DP_{N-1} + DP_{N-5} \)라는 점화식을 알아낼 수 있습니다.

\( DP_{1} = DP_{2} = DP_{3} = 1, DP_{4} = DP_{5} = 2 \)라는 초항도 문제에서 주니 그대로 써주면 됩니다.

 

시간복잡도는 \( O(N) \)개의 상태 × \( O(1) \)회의 계산 = \( O(N) \)입니다.

+ 100번째 삼각형의 길이 = \( DP_{N} = 888\,855\,064\,897 > 2^{31} - 1 \)입니다. 오버플로우에 조심하세요.

ll dp[120];

void Main(){
	dp[1] = 1; dp[2] = 1; dp[3] = 1; dp[4] = 2; dp[5] = 2;
	for (int i = 6; i <= 100; i++){ dp[i] = dp[i-1] + dp[i-5]; }
	int t; scanf("%d", &t);
	while (t--){
		int n; scanf("%d", &n);
		printf("%lld\n", dp[n]);
	}
}

수열을 분석해보면 알아차렸겠지만, \( DP_{N} = DP_{N-2} + DP_{N-3} \)이라는 점화식을 유도해낼 수 있습니다.

이거를 도형에서 어떻게 유도하는지는 모르겠으니 TODO로 놓겠습니다.

ll dp[120];

void Main(){
	dp[1] = 1; dp[2] = 1; dp[3] = 1;
	for (int i = 4; i <= 100; i++){ dp[i] = dp[i-2] + dp[i-3]; }
	int t; scanf("%d", &t);
	while (t--){
		int n; scanf("%d", &n);
		printf("%lld\n", dp[n]);
	}
}

6. [2302] 극장 좌석 (Silver I)

우선, VIP가 없다고 생각해봅시다. 이 때 가능한 배치는 뭐가 될까요?

결론부터 말하자면, '두 자리를 서로 바꾸는 경우' 또는 '내 자리에 그대로 앉는 경우'로만 이루어진 배치가 됩니다.

그렇지 않다면, 2칸 이상 떨어지는 사람이 발생하겠죠.

 

그럼 \( DP_{N} := \) \( N \)개의 자리가 있을 때, 이를 배치하는 경우의 수 라고 정의하면,

(VIP가 없을 때의) 이 문제의 점화식을 아래와 같이 생각해볼 수 있습니다.

• (맨 뒤의) 2명이 서로 자리를 바꾸는 경우: 나머지 \( N-2 \)명을 잘 배치해주면 됩니다. \( DP_{N-2} \)가지가 있습니다.
• (맨 뒤에) 1명이 그대로 앉는 경우: 나머지 \( N-1 \)명을 잘 배치해주면 됩니다. \( DP_{N-1} \)가지가 있습니다.

즉, \( DP_{N} = DP_{N-1} + DP_{N-2} \)가 됩니다.

이제 VIP를 넣어서 생각해보죠.

VIP가 있는 자리는 강제적으로 고정이 됩니다. 그러니, 위 경우에서 '2명이 자리를 바꾸는 경우'가 제한되겠죠.

다르게 말하자면, 점화식을 아래와 같이 세울 수 있게 됩니다.

• 현재 자리 또는 이전 자리가 VIP석인 경우: 맨 뒤의 1명이 그대로 앉는 경우밖에 없습니다. \( DP_{N-1} \)가지가 있습니다.
• 그렇지 않은 경우: 아까 구한 경우와 동일합니다. \( DP_{N-1} + DP_{N-2} \)가지가 있습니다.

이거를 그대로 구현해주면 됩니다.

시간복잡도는 \( O(N) \)개의 상태 × \( O(1) \)회의 연산 = \( O(N) \)입니다.

int chk[50], dp[50];

void Main(){
	int n, m; scanf("%d %d", &n, &m);
	while (m--){ int x; scanf("%d", &x); chk[x] = 1; }
	dp[0] = 1; dp[1] = 1;
	for (int i = 2; i <= n; i++){
		if (chk[i-1] || chk[i]){ dp[i] = dp[i-1]; }
		else{ dp[i] = dp[i-1] + dp[i-2]; }
	}
	printf("%d", dp[n]);
}

위에서 했던 풀이에서 한 발 더 나가봅시다.

VIP를 사이에 두고 자리를 바꿀 수 없기 때문에, 각 VIP로 나눠진 부분 배열에서의 답을 구해줄 수 있습니다.

즉, 좌석이 9개인데 VIP가 4, 7번에 있다면, [1, 3] 구간과 [5, 6] 구간, [8, 9] 구간의 경우를 따로 구해준 뒤 이를 곱해주면 됩니다.

 

각 구간별로 가능한 경우의 수를 구하는 방식은 위에서 "VIP가 없을 때"를 참고하세요.

const int N = 40;
ll dp[50];

void Main(){
	dp[0] = 1; dp[1] = 1;
	for (int i = 2; i <= N; i++){ dp[i] = dp[i-1] + dp[i-2]; }
	int n, m; scanf("%d %d", &n, &m);
	int x1 = 0; int ans = 1;
	for (int i = 0; i <= m; i++){
		int x2 = n+1; if (i != m){ scanf("%d", &x2); }
		int l = x2-x1 - 1;
		ans *= dp[l];
		x1 = x2;
	}
	printf("%d", ans);
}

7. [16456] 하와와 대학생쨩 하와이로 가는 거시와요~ (Silver I)

\( DP_{i} := \) 첫 \( i \)개의 섬을 탐색하는 방법의 수 를 정의한 뒤, 작은 수에 대해 시뮬레이션을 돌려봅시다.

• \( N = 1 \Rightarrow 1, \{ 1 \} \)
• \( N = 2 \Rightarrow 1, \{ 1 \rightarrow 2 \} \)
• \( N = 3 \Rightarrow 2, \{ 1 \rightarrow 2 \rightarrow 3, 1 \rightarrow 3 \rightarrow 2 \} \)
• \( N = 4 \Rightarrow 3, \{ 1 \rightarrow 2 \rightarrow 3 \rightarrow 4, 1 \rightarrow 2 \rightarrow 4 \rightarrow 3, 1 \rightarrow 3 \rightarrow 2 \rightarrow 4 \} \)

아무래도 \( i \)라는 인자만으로는 식을 세우기 어려울 것 같습니다.
첫 \( i \)개의 섬을 탐색하지만, 그렇다고 탐색이 항상 \( i \)번 섬에서 끝나지는 않기 때문이죠.

하지만, 우리는 탐색이 끝나는 섬이 어디일지 예측해볼 수는 있습니다.

그 이유는, 이동 방식의 특성상 연속으로 2번 뒤로 갈 수 없기 때문입니다.

(만약 그랬다면, 2개 이상의 섬을 건너뛰었다는 소리가 됩니다. 즉, 불가능하죠.)

 

그러니, 마지막으로 탐색한 섬을 따로 넣고 DP를 돌려봅시다.

\( DP_{i, j} := \) 첫 \( i \)개의 섬을 탐색하되, \( i-j \)번 섬을 마지막으로 탐색하는 경우의 수

이렇게 정의하면, \( j \lt 2 \)임을 (방금 봤으니) 알 수 있습니다.

 

이제 \( DP_{i, j} \)는 아래와 같이 구해주면 됩니다.

• \( DP_{i, 0} \): \( i-1 \)개의 섬을 탐색한 뒤 \( i \)번째 섬으로 오기. \( i-1 \)번째와 \( i-2 \)번째 섬에 있는 경우 모두 가능함. \( DP_{i-1, 0} + DP_{i-1, 1} \)
• \( DP_{i, 1} \): \( i-2 \)개의 섬을 탐색하고 \( i-2 \)번째 섬으로 간 뒤, \( i \)번째 섬을 갔다가 \( i-1 \)번째 섬으로 돌아가기. \( DP_{i-2, 0} \)

문제의 답은 \( DP_{N, 0} + DP_{N, 1} \)이 되고, 시간복잡도는 \( O(N) \times O(1) = O(N) \)입니다.

const ll mod = 1000000009;
ll dp[50020][2];

void Main(){
	int n; scanf("%d", &n);
	dp[1][0] = 1; dp[1][1] = 0;
	dp[2][0] = 1; dp[2][1] = 0;
	for (int i = 3; i <= n; i++){
		dp[i][0] = (dp[i-1][0] + dp[i-1][1]) % mod;
		dp[i][1] = dp[i-2][0];
	}
	printf("%d", (dp[n][0] + dp[n][1]) % mod);
}

원래 이 코드로 풀이를 쓰려 했는데, 풀이 도중 '제가 생각한 게 잘못되었음'을 알아차렸습니다.

그런데 왜 맞는 건지는 모르겠으니 TODO로 놓겠습니다.

 

- Update on 2022.05.10. 18:03

잠시 \( DP_{i, j} \)와 \( DP_{i} \)를 섞어봅시다. 정의 및 점화식은 1번 풀이에서 볼 수 있습니다.

이제 식을 하나씩 풀어봅시다.

• \( DP_{N-1, 0} + DP_{N-1, 1} \): 정의에 의해 \( DP_{N-1} \)입니다.
• \( DP_{N-2, 0} \): 점화식을 여기에 한 번 더 넣으면, \( DP_{N-3, 0} + DP_{N-3, 1} = DP_{N-3} \)이 됩니다.

즉, 점화식이 \( DP_{N} = DP_{N-1} + DP_{N-3} \)이 됩니다.

초항은 \( DP_{1} = DP_{2} = 1, DP_{3} = 2 \)니 이대로 구현해주면 됩니다.

const ll mod = 1000000009;
ll dp[50020];

void Main(){
	int n; scanf("%d", &n);
	dp[1] = 1; dp[2] = 1; dp[3] = 2;
	for (int i = 4; i <= n; i++){ dp[i] = (dp[i-1] + dp[i-3]) % mod; }
	printf("%d", dp[n]);
}

8. [2631] 줄세우기 (Gold V)

위치를 옮기는 아이들의 수를 최소로 한다 = 위치를 옮기지 않는 아이들의 수를 최대로 한다 입니다.

그럼, 위치를 옮기지 않고도 순서를 유지하려면 어떻게 해야 할까요?

움직이지 않는 아이들끼리는 순서가 이미 정렬된 상태여야 합니다.

 

그럼, 움직이지 않는 아이들끼리 순서가 정렬되었다면, 반드시 모두를 정렬시킬 수 있을까요?

움직이는 아이들을 사이에 잘 끼워넣으면 항상 가능합니다.

 

즉, 움직이지 않는 아이들끼리 순서가 유지되기만 한다면, 언제든 정렬을 할 수 있게 됩니다.

그러니, 이제 이 길이의 최댓값을 구해봅시다.

 

이 문제에서 순서가 유지된다는 건 '값이 오름차순으로 정렬되어있다'는 것이고, 이 길이가 최대화되어야 하니

아까 위에서 푼 "[11053] 가장 긴 증가하는 부분 수열"과 동일함을 알 수 있습니다.

차이점은, 움직이는 아이들의 수를 구해야 하니 LIS의 길이를 구해준 뒤 이를 N에서 빼주면 됩니다.

시간복잡도는 3번 문제와 동일한 이유로 \( O(N^2) \)입니다.

int max(int a, int b){ return a>b ? a : b; }

int arr[220], dp[220];

void Main(){
	int n; scanf("%d", &n);
	for (int i = 1; i <= n; i++){ scanf("%d", &arr[i]); }
	for (int i = 1; i <= n; i++){
		dp[i] = 1;
		for (int j = 1; j < i; j++){
			if (arr[j] < arr[i]){ dp[i] = max(dp[i], dp[j] + 1); }
		}
	}
	int res = 0;
	for (int i = 1; i <= n; i++){ res = max(res, dp[i]); }
	printf("%d", n-res);
}