문제

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

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

입력받은 수를 3으로 나누거나 2로 나누거나 1을 빼가면서 1로 만드는데 최소 횟수를 구하는 문제이다.

나는 재귀 함수로 작성했는데 아마 2중 for문으로도 해결할수 있지 않을까 생각하지만 잘 모르겠다.

답은 항상 n을 3으로 나누고 시작할때, n을 2로 나누고 시작할때, n-1로 시작할때 이 세가지 경우중 하나이다

점화식 도출은 이렇게 했다.

n을 3으로 나누고 시작할때 횟수(3으로 나눌수 없다면 초기값)와 2로 나누고 시작할때의 횟수 중  적은 값을 선택하고 그 값과 n에서 1을빼고 시작할때의 횟수를 비교한다.

#=> $ f(n) = min( f(n-1), min( f(n/3), f(n/2) ) ) $

단, f(n) = n을 1로 만드는 최소 비용을 나타내는 함수이므로 항상 최소 값을 비교하기 위해서 초기값을 매우 큰 수로 설정하며, n이 1~3일때 최소 횟수를 이미 알고 있으므로 미리 값을 집어넣어줬다.

#include<iostream>
#include<string>
#define INT_MAX 987654321

using namespace std;

int* r = new int[1000001];

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

int solve(int x){
 	if(r[x] != INT_MAX) return r[x];
 	int& ret = r[x];
 	if(x%3==0) ret = solve(x/3);
 	if(x%2==0) ret = min(ret, solve(x/2));
 	ret = min(ret, solve(x-1))+1;
 	return ret;
}
int main(){
	int n,i;
	cin>>n;
	for(i=0;i<=n;i++)
        r[i] = INT_MAX;
	r[1] = 0;
	r[2] = 1;
	r[3] = 1;
	cout << solve(n);
}