[코딩테스트][Dynamic Programming] 백준 1463, 11726, 11727

04 Dec 2019 in Algorithm & Language on Coding Test 백준

백준 1463, 11726, 11727

여담

동적계획(Dynamic Programming) 을 고안한 Richard E.Bellman은 dynamic이란 단어가 멋있어서 선택했다고 한다….

https://github.com/h-dyeon/Algorithm

백준 1463 1로만들기

//내코드
#include<iostream>
using namespace std;
int x;//(1<=X<=1000000)
int answer[1000002];
int main() {
	scanf_s("%d", &x);

	answer[1] = 0;
	answer[2] = 1;
	answer[3] = 1;
	for (int i=4; i <= x; i++) {
		answer[i] = answer[i - 1] + 1;
		if (i % 2 == 0 && answer[i / 2] + 1 < answer[i])
			answer[i] = answer[i / 2] + 1;
		if (i % 3 == 0 && answer[i / 3] + 1 < answer[i])
			answer[i] = answer[i / 3] + 1;
	}

	cout << answer[x];
	return 0;
}

//참고 코드 ==> https://www.acmicpc.net/source/16250222
//재귀함수 사용, 
#include <cstdio>
using namespace std;
int i;
int solve(int num) {
	if (num < 2) return 0;
	int a1 = solve(num / 3) + num % 3 + 1;
	int a2 = solve(num / 2) + num % 2 + 1;

	return a1 < a2 ? a1 : a2;
}
int main() {
	int num;
	scanf("%d", &num);
	printf("%d", solve(num));
}

백준 11726 2xn타일링

이번엔 재귀함수로 해볼까 하다가 시간초과가 떴다. 그래서 값을 저장해두는 방식으로 바꿨다.

#include <iostream>
using namespace std;
int x;//(1<=X<=1000)
int t[1001];

int answer(int tmp) {
	if (t[tmp] != 0)
		return t[tmp];
	else
		t[tmp]= (answer(tmp - 1) + answer(tmp - 2))%10007;
	return t[tmp];
}
int main() {
	scanf_s("%d", &x);
	t[1] = 1;
	t[2] = 2;
	cout << answer(x) % 10007;
	return 0;
}

//참고코드 https://www.acmicpc.net/source/2737958
#include<stdio.h>
int main()
{
	int n,dp[1001]={0,1,2};
	scanf("%d",&n);
	for(int i=3;i<=n;++i)
		dp[i]=(dp[i-1]+dp[i-2])%10007;
	printf("%d",dp[n]);
}

백준 11727 2xn타일링2

타일링1번에서 규칙을 살짝만 바꾸면됨!

#include <iostream>
using namespace std;
int x;//(1<=X<=1000)
int t[1001];

int main() {
	scanf_s("%d", &x);
	int t[1001] = {0, 1,3,5 };
	for (int i = 4; i <= x; i++) {
		t[i] =( t[i - 1] + t[i - 2] * 2)%10007;
	}
	cout << t[x];
	return 0;
}