문제

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