문제

https://www.acmicpc.net/problem/1904

풀이

1과 00만을 이용한 길이가 N인 이진 수열이 몇개인지 찾는 문제이다. 1과 00만을 사용해야 해야하므로 0이 혼자 쓰여서는 안된다. 이 문제는 직접 몇 개의 케이스를 손으로 적어서 풀었다.

DP[1] = 1

DP[2] = 11, 00

DP[3] = 111, 100, 001

DP[4] = 1111, 1100, 1001, 0011, 0000

DP[5] = 11111, 11001, 10011, 10000, 00001, 00100, 00111, 01001

...

길이가 N일때의 갯수를 세어보면 $ DP[N] = DP[N-1] + DP[N-2] $, 즉 이 문제는 단순한 N번째 피보나치 수를 구하는 문제와 같다.

#include <stdio.h>
int dp[1000001];
int solve(int x){
	if(dp[x]) return dp[x];
	return dp[x] = (solve(x-1) + solve(x-2)) % 15746;
}
int main() {
	int n;
	dp[1] = 1;
	dp[2] = 2;
	dp[3] = 3;
	scanf("%d",&n);
	printf("%d",solve(n));
}

문제

https://www.acmicpc.net/problem/9095

풀이

이제 막 알고리즘에 입문한 알린이 친구 김X를 위해 쓰는 풀이. 사실 나도 흐접인데 X호는 더 흐접이라 많이 도와줘야된다. 원래 못하는 애들끼리 도우면서 살랬음.

정수 N을 1,2,3의 합 조합으로 나타낼수 있는 모든 경우의 수를 구하는게 목적이다. 문제를 역으로 생각해보면 우리는 N에서 항상 1, 2, 3을 빼는 선택지밖에 없으므로 점화식은 $ f(n) = f(n-1) + f(n-2) + f(n-3) $이다.

여기서 우리는 이미 N이 1~3일때 경우의 어느정도 있는지 이미 알고있다.

• 1

• 1+1
• 2

• 1+1+1
• 1+2
• 2+1
• 3

Bottom-Up

#include <stdio.h>
int main() {
	int n,t,i,j;
	int arr[11]={0};
	arr[1]=1;
	arr[2]=2;
	arr[3]=4;
	scanf("%d",&t);
  	while(t--){
    	scanf("%d",&n);
    	for(i=4;i<=n;i++){
    		if(arr[i]) continue;
    		arr[i]=arr[i-1]+arr[i-2]+arr[i-3];
    	}
    	printf("%d\n",arr[n]);
  	}
}

Top-Down

#include <stdio.h>
#include <string.h>
int cache[11];
int solve(int i){
    if(!i) return 1;
    if(i<0) return 0;
    if(cache[i] != -1) return cache[i];
    	
    return cache[i] = solve(i-1) + solve(i-2) + solve(i-3);
}
int main(){
    int n,t;
    scanf("%d",&t);
    memset(cache,-1,sizeof(cache));
    while(t--)
    {
    	scanf("%d",&n);
        printf("%d\n",solve(n));
    }
}

문제

풀이

Coin Change라는 이름으로 유명한 DP 문제이다. 이 문제는 2차원 배열을 사용해서 해결할수도 있고 1차원 배열을 사용해서 해결할수도 있는데 2차원 배열 사용하면 6MB 정도의 메모리를 사용하게 되므로 문제의 메모리 제한을 초과하게 된다. 

일단 2차원 풀이법부터 설명해보자면, dp[n][k] = n 종류의 동전으로 k원을 만드는 경우의 수라고 정의할때 dp[n][k]를 구하는 방법은 두가지이다.

1. dp[n][k-coin[n]] = n번째 동전을 사용한 뒤 k원을 만들수 있는 경우의 수

2. dp[n-1][k] = n번째 동전을 사용하지 않고 k원을 만들수 있는 경우의 수

이렇게 되므로 점화식은 $ dp[n][k] = dp[n][k-coin[n]] + dp[n-1][k] $가 된다.

#include<stdio.h>
#include<string.h>
int coin[100]={0},cache[100][10001];
int solve(int n,int k){
	if(n<0||k<0)return 0;
	if(k==0) return 1;
	if(cache[n][k] != -1) return cache[n][k];
	return cache[n][k] = solve(n,k-coin[n]) + solve(n-1,k);
	
}
int main() {
	int n,k,i;
	scanf("%d%d",&n,&k);
	for(i=0;i<n;i++){
		memset(cache[i],-1,sizeof(cache[i]));
		scanf("%d",&coin[i]);
	}
	printf("%d",solve(n-1,k));
}

물론 위는 2차원 배열을 사용해서 메모리 초과가 발생한다. 1차원 풀이는 아무리 생각해도 모르겠어서 여러 문서를 뒤져보고 이해했다.

2차원 배열을 사용하는 점화식이 $ dp[n][k] = dp[n][k-coin[n]] + dp[n-1][k] $인데, 여기서 n이 1증가하면 결국은 $ dp[n][k] = dp[n][k-coin[n]] $이되므로 $ \sum\limits_{i=coin[n]}^k cache[i] = cache[i] + cache[i - coin[n]] $이 된다.

#include <stdio.h>
int main(void) {
	int i,j,n,k,coin[100]={0},cache[10001]={0};
	scanf("%d%d",&n,&k);
	cache[0]=1;
	for(i=0;i<n;i++){
		scanf("%d",&coin[i]);
		for(j=coin[i];j<=k;j++)
			cache[j] += cache[j-coin[i]];
	}
	printf("%d",cache[k]);
	return 0;
}

문제

https://www.acmicpc.net/problem/1149

전형적 DP 문제이지만 내가 너무 초보라 처음 풀었을때 엄청 헤맸다. 모든 집을 R,G,B 색 중 하나로 칠하는데 각 집들을 도색하는데 이웃과 색상이 같으면 안되는 조건 하에 도색 할수 있는 최소 비용을 구하는 문제이다.

풀이

각 집을 도색할때 이전 집과 색상이 같지않게 처리하면 모든 이웃이 색상이 같이 않게 되기 때문에 내가 R일때는 이전 집의 G or B의 비용 중 최소값, 내가 G일때는 R or B 중 최소값, 내가 B일때는 R or G 중의 최소값에 현재 집을 칠할 색의 비용을 계속 더해가주면 된다.

$ Cost[i][j] = min( Cost[i-1][(j+1)\%3], Cost[i-1][(j+2)\%3] ) + Home[j] $

Cost[i][j] = i번째집을 j색상으로 칠하려할때 i번째 집까지 도색할때 드는 최소 비용

Home[j] = 현재 집을 j색상으로 칠하려 할때 드는 비용

#include <stdio.h>

int cache[1001][3];

int min(int x, int y){ return (x>y)?y:x; }

int main(void) {
	int i,j,t,r[3];
	scanf("%d",&t);
	for(i=1;i<=t;i++){
		scanf("%d%d%d",&r[0],&r[1],&r[2]);
		for(j=0;j<3;j++)
			cache[i][j] = min(cache[i-1][(j+1)%3],cache[i-1][(j+2)%3])+r[j];
	}
	printf("%d",min(min(cache[t][0],cache[t][1]),cache[t][2]));
	return 0;
}

주의

% 연산자보다 + 연산자의 우선순위가 낮기 때문에 j + 2 % 3의 결과가 j + (2 % 3)가 되므로 직접 괄호로 (j + 2) % 3 이렇게 우선순위를 정해주어야 한다.

문제

https://www.acmicpc.net/problem/11057

수의 길이 N이 주어졌을때 0부터 N사이에서 첫번째 자리부터 마지막 자리까지 내림차순으로 진행되지 않는 수를 찾는것이다.

예를들어 2234, 2999는 오름차순으로 진행되는 수지만 2167은 중간 1이 왼쪽의 1보다 작으므로 해당되지 않는다.

규칙

$ dp[1][0]=dp[1][1]=...=dp[1][9]=1 $ 이고 $ 2 ≤ N $ 일때

dp[N] = $ \sum\limits_{i=0}^9 dp[N-1][i] + \sum\limits_{i=1}^9 dp[N-1][i] + ... + dp[N-1][9] $ 

단 문제에서 출력을 10007로 나눈 나머지를 출력하라 하였으니 매번 계산할때마다 10007로 나누어주어야 한다.

#include <stdio.h>
int main() {
	int n,i,j,k,cache[1001][101]={0},sum=0;
	scanf("%d",&n);
	for(i=0;i<10;i++)
		cache[1][i] = 1;
	for(i=2;i<=n;i++){
		for(j=0;j<10;j++){
			for(k=j;k<10;k++){
				cache[i][j] += cache[i-1][k];
				cache[i][j]%=10007;
			}
		}
	}
	for(i=0;i<10;i++){
		sum += cache[n][i];
		sum %= 10007;
	}
	printf("%d",sum);
}