초급반 4주차 풀이 - 함수, 재귀, DP

A. [10870] 피보나치 수 5 (Bronze II)

피보나치 수는 아래와 같이 구할 수 있습니다.

\[ F_{x} = \begin{cases} 0 & \text{if } x = 0 \\ 1 & \text{if }x = 1 \\ F_{x-1} + F_{x-2} & \text{otherwise} \end{cases} \]

 

이를 그대로 재귀함수로 옮겨주면 됩니다.

int f(int x){
	if (x <= 1){ return x; }
	return f(x-1) + f(x-2);
}

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

1. [11729] 하노이 탑 이동 순서 (Silver I)

\( f(st, ed, n) := \) \( st \)번 장대에서 \( ed \)번 장대로 \( n \)개의 원판을 옮기는 함수를 정의해봅시다.

 

자명하게, \( n = 1 \)이었다면 \( f(st, ed, 1) = \) \( (st \Rightarrow ed) \)로 끝내면 됩니다.

 

그렇지 않다면, 즉 \( n \ge 2 \)라면 어떻게 해야 할까요?

맨 밑의 \( n \)번째 원판은 어차피 위에 \( n-1 \)종류의 디스크를 다 놓을 수 있습니다.

그러나, \( n \)번째 원판을 \( ed \)로 옮기려면 위의 \( n-1 \)개의 원판이 \( st, ed \)에 없어야 합니다.

마침 장대가 정확히 3개가 있으니, 이 3번째 장대를 \( mid \)라고 부릅니다.

그러면 우리가 해야 하는 이동은 아래와 같이 쓸 수 있습니다.

1. \( st \)에서 \( mid \)로 \( n-1 \)개의 원판을 옮긴 뒤,
2. (\( n \)번째 원판을) \( st \)에서 \( ed \)로 옮기고,
3. 아까 \( mid \)에 놔뒀던 \( n-1 \)개의 원판을 \( ed \)로 옮긴다.

그런데 1번과 3번 단계는 재귀적으로 할 수 있습니다.

즉, \( f(st, ed, n) \)을 이렇게 계산할 수 있습니다,

\[ f(st, ed, n) = \begin{cases} (st \Rightarrow ed) & \text{if n = 1} \\ f(st, mid, n-1) \rightarrow (st \Rightarrow ed) \rightarrow f(mid, ed, n-1) & \text{otherwise} \end{cases} \]

 

그럼 옮긴 횟수 \( K_{i} \)는 몇 번일까요?

\[ K_{n} = \begin{cases} 1 & \text{if n = 1} \\ K_{n-1} + 1 + K_{n-1} = 2K_{n-1} + 1 & \text{otherwise} \end{cases} \]

 

+ 사실 여기서 한 발 더 나아가서 \( K_{n} = 2^{n} - 1 \)을 유도할 수 있습니다.

하지만 재귀로도 충분히 구할 수 있으니 굳이 증명은 하지 않겠습니다.

int k(int n){
	if (n == 1){ return 1; }
	return 2*k(n-1) + 1;
}
void f(int st, int ed, int n){ int mid = 6 - (st+ed);
	if (n == 1){ printf("%d %d\n", st, ed); return; }
	f(st, mid, n-1); printf("%d %d\n", st, ed); f(mid, ed, n-1);
}

void Main(){
	int n; scanf("%d", &n);
	printf("%d\n", k(n)); f(1, 3, n);
}

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

피보나치 수는 아래와 같이 구할 수 있습니다.

\[ F_{N} = \begin{cases} 0 & \text{if } N = 0 \\ 1 & \text{if } N = 1 \\ F_{N-1} + F_{N-2} & \text{otherwise} \end{cases} \]

 

하지만 이젠 \( N \le 90 \)이라서, 재귀를 저대로 내면 시간 초과를 받게 됩니다.

 

다행히도, 피보나치 수는 언제 계산해도 같은 값이 나옵니다.

그러니 계속 값을 계산하지 말고, 한 번 계산한 뒤 그 값을 저장하고

나중에 그 값이 다시 필요할 때 "재계산을 하는 대신" 그냥 바로 저장된 값을 반환해주면 됩니다.

이러한 방식을 '메모이제이션 (Memoization)'이라고 합니다.

 

+ 피보나치 수는 생각보다 빠르게 커지니, long long 자료형을 사용해야 합니다.

실제로 94?번째 피보나치 수부터는 long long으로 표현할 수 있는 값도 벗어나게 됩니다.

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));
}

위에서 썼던 방식은 Top-Down이라고 해서, "위에서부터 밑으로 내려가는 방식"으로 문제를 풀어나갑니다.

이번에는 Bottom-Up, 즉 "밑에서부터 위로 올라가는 방식"으로 문제를 풀어보죠.

 

다시 피보나치 식을 불러옵시다.

\[ F_{N} = \begin{cases} 0 & \text{if } N = 0 \\ 1 & \text{if } N = 1 \\ F_{N-1} + F_{N-2} & \text{otherwise} \end{cases} \]

 

저희는 \( F_{0}, F_{1} \)을 알고 있으니, 이를 통해서 \( F_{2} \)를 계산할 수 있습니다.

이제, \( F_{1}, F_{2} \)를 알고 있으니, 이를 통해서 \( F_{3} \)을 계산할 수 있습니다.

이런 식으로 \( F_{N-2}, F_{N-1} \)을 알고 있으니, 이를 통해서 \( F_{N} \)를 차례차례 계산해나가는 방식입니다.

ll val[100];

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

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

이항 계수가 뭔지 모르는 분들을 위해: \( \binom{N}{K} = {}_{N}C_{K} \)입니다.

 

\( {}_{n}C_{r} = \frac{n!}{r!(n-r)!} \)는 정의상 팩토리얼이 쓰이고, 이는 재귀함수나 반복문으로 구해줄 수는 있지만, 팩토리얼의 값이 너무 커지게 됩니다. 나머지 연산을 써서 N! mod 10,007을 저장할 수도 있지만, 이러면 이유 모를 틀렸습니다를 받게 됩니다.

 

그러니, \( {}_{n}C_{r} = {}_{n-1}C_{r-1} + {}_{n-1}C_{r} \)이라는 식을 대신 써봅시다.

식 자체가 재귀적으로 정의되었으니, 이를 (메모이제이션을 동반한) Top-Down이나 Bottom-Up으로 돌리면 됩니다.

 

* 사실 팩토리얼을 계산하는 방식으로 풀 수 있긴 합니다. 하지만 이건 초급반의 범위를 벗어나니 논외로 하겠습니다.

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]);
}

4. [2193] 이친수 (Silver III)

길이가 0인 이친수는 1개 ("") 있습니다.

길이가 1인 이친수는 1개 (1) 있습니다.

이제 길이가 \( N \)인 이친수의 개수 \( F_{N} \)을 생각해보면,

• 길이가 \( N-1 \)인 이친수의 맨 뒤에 0을 붙이는 경우, \( F_{N-1} \)가지
• 길이가 \( N-2 \)인 이친수의 맨 뒤에 01을 붙이는 경우, \( F_{N-2} \)가지

 2가지밖에 나오지 않습니다.

그러니 이친수의 개수는 아래와 같이 구할 수 있습니다.

\[ F_{N} = \begin{cases} 0 & \text{if } N = 0 \\ 1 & \text{if } N = 1 \\ F_{N-1} + F_{N-2} & \text{otherwise} \end{cases} \]

ll val[100];

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

5. [9095] 1, 2, 3 더하기 (Silver III)

\( N \)을 만드는 경우의 수를 생각해봅시다.

\( N = 1: {1}, 1 \)

\( N = 2: {2, 1+1}, 2 \)

\( N = 3: {3, 1+2, 2+1, 1+1+1}, 4 \)

 

이제 \( N \ge 4 \)를 생각해봅시다.

\( N \)을 만드는 경우는 아래 3가지로 나눠볼 수 있습니다.

• \( N-1 \)을 만든 뒤 1을 더하기, \( F_{N-1} \)가지
• \( N-2 \)를 만든 뒤 2를 더하기, \( F_{N-2} \)가지
• \( N-3 \)을 만든 뒤 3을 더하기, \( F_{N-3} \)가지

세 경우를 더해주면 됩니다.

즉, 아래 식을 구현해주면 됩니다.

\[ F_{N} = \begin{cases} 1 & \text{if } N = 1 \\ 2 & \text{if } N = 2 \\ 4 & \text{if } N = 3 \\ F_{N-1} + F_{N-2} + F_{N-3} & \text{otherwise} \end{cases} \]

int val[20];

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

6. [17626] Four Squares (Silver IV)

이번에는 경우의 수 같은 게 아니라, '최솟값'을 구해야 합니다.

그러니, \( DP_{N} = \) \( N \)을 만들기 위해 필요한 제곱수의 최소 개수를 정의해봅시다.

이제, \( N \)을 어떻게 만들지 생각해봅시다.

 

1, 2, 3 더하기처럼, 아래 방식으로 값을 계산해볼 수 있습니다.

• \( N-1 \)을 구한 뒤, \( 1 \)을 더합니다. \( DP_{N-1} + 1 \)개의 제곱수가 필요합니다.
• \( N-4 \)를 구한 뒤, \( 4 \)를 더합니다. \( DP_{N-4} + 1 \)개의 제곱수가 필요합니다.
• \( N-9 \)를 구한 뒤, \( 9 \)를 더합니다. \( DP_{N-9} + 1 \)개의 제곱수가 필요합니다.
• ...

이렇게 많은 걸 손으로 하기는 귀찮으니, 컴퓨터에게 맡깁시다.

• \( N - k^2 \)을 구한 뒤, \( k^2 \)을 더합니다. \( DP_{N-k^2} + 1 \)개의 제곱수가 필요합니다.

저렇게 구한 값들 중 '최솟값'을 골라주면 됩니다.

+ 문제 본문에도 나와있듯이, 라그랑주의 네 제곱수 정리에 의해, \( DP_{N} \le 4 \)임이 증명되었습니다.

그러니, 최솟값의 초깃값을 4로 잡아줘도 됩니다.

int min(int a, int b){ if (a < b){ return a; } return b; }

int dp[50020];

int main(){
	int n; scanf("%d", &n);
	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);
		}
	}
	printf("%d", dp[n]);
}

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

\( DP_{i} := \) \( i \)번째 집까지 색칠하는 데의 최솟값 으로 정의해봅시다.

 

그럼 아래 경우들로 문제를 나눌 수 있습니다.

• \( i \)번째 집을 R로 칠한다. "\( i-1 \)번 집이 R로 칠해지지 않은 상태여야 합니다."
• \( i \)번째 집을 G로 칠한다. "\( i-1 \)번 집이 G로 칠해지지 않은 상태여야 합니다."
• \( i \)번째 집을 B로 칠한다. "\( i-1 \)번 집이 B로 칠해지지 않은 상태여야 합니다."

하지만 아까 위에서 정의했던 DP로는 위 과정을 구현할 수 없습니다.

정확히는, "어떤 색으로 칠해져있는가"라는 정보가 추가적으로 필요합니다.

그러니 색깔의 정보를 추가해서 DP를 다시 세워봅시다.

\( DP_{i, c} := \( i \)번째 집까지 색칠하는 데의 최솟값. 단, \( i \)번째 집은 \( c \)로 칠한다.

 

이제 위의 경우들을 해결해줄 수 있습니다.

• \( i \)번째 집을 R로 칠한다. \( \min (DP_{i-1, \text{G}}, DP_{i-1, \text{B}}) \)
• \( i \)번째 집을 G로 칠한다. \( \min (DP_{i-1, \text{R}}, DP_{i-1, \text{B}}) \)
• \( i \)번째 집을 B로 칠한다. \( \min (DP_{i-1, \text{R}}, DP_{i-1, \text{G}}) \)

최종 답은 \( \min (DP_{N, \text{R}}, DP_{N, \text{G}}, DP_{N, \text{B}}) \)가 됩니다.

// R, G, B -> 0, 1, 2
int min(int a, int b){ if (a < b){ return a; } return b; }

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

int main(){
	int n; scanf("%d", &n);
	for (int i = 1; i <= n; i++){ scanf("%d %d %d", &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];
	}
	printf("%d", min(min(dp[n][0], dp[n][1]), dp[n][2]) );
}