[코딩테스트][Dynamic Programming] 백준 1699, 2133, 9461

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

백준 1699, 2133, 9461

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

백준 1699 : 제곱수의 합

재귀함수는 신중하게 생각할 것.

#include <iostream>
#include <algorithm>
using namespace std;
int dps[100001];
int main() {
	int n;
	scanf_s("%d", &n);

	dps[1] = 1;
	dps[2] = 2;
	dps[3] = 3;
	for (int i = 4; i <= n; i++) {
		dps[i] = i; //초기화
		for (int j = 1; j * j <= i; j++) {
			dps[i] = min(dps[i], 1 + dps[i - (j * j)]);
		}
	}

	printf("%d", dps[n]);
	return 0;
}

// https://www.acmicpc.net/source/10500957
// 좀 야매방식.... 그런데 0ms....
#include <stdio.h>
#include <math.h>
using namespace std;

int sum[100004];
int main(){
	int N;
	scanf("%d", &N);
    //제곱수들을 먼저 초기화
	for (int i = 1; i*i <= N; i++){
		sum[i*i] = 1;
		for (int j = i; i*i + j*j <= N; j++){ //2개의 제곱수 합
			sum[i*i + j*j] = 2;
		}
	}
	if (sum[N]){
		printf("%d", sum[N]);
		return 0;
	}

    //없으면 정석대로 계산
	for (int i = 1; i*i <= N; i++){
		if (sum[N - i*i]){
			printf("3");
			return 0;
		}
	}
	printf("4");
	return 0;
}

백준 2133 : Tri Tiling

dp[n]=dp[n-2]x2 + dp[n-4]x4 로 생각했는데 내가 미쳐 생각하지 못한 부분이 더 있었다. 점화식을 유도할때는 신중할 것.

#include <iostream>
#include <algorithm>
using namespace std;
int dp[31];
int main() {
	int n;
	scanf_s("%d", &n);

	if (n % 2 == 1) { //홀수
		printf("0");
		return 0;
	}
	else { //짝수
		dp[0] = 1;
		dp[2] = 3;
		for (int i = 4; i <= n; i=i+2) {
			dp[i] = dp[i - 2] * 3;
			for (int j = i-4; j >=0; j=j-2) {
				dp[i] += dp[j] * 2;
			}
		}
		printf("%d", dp[n]);
	}
	return 0;
}

//https://www.acmicpc.net/source/4534163
//어짜피 배열이 0으로 초기화되서 홀수경우를 따로 빼줄 필요가 없다.
#include <cstdio>
int p[35],n;
int main(){
  p[0]=1;
  for(int i=2;i<35;i+=2){
    p[i]=p[i-2];
    for(int j=2;i>=j;j+=2)
      p[i]+=2*p[i-j];
  }
  scanf("%d",&n);
  printf("%d",p[n]);
}

백준 9461 : Padovan Sequence

일단 손으로 계산해볼 것. 의외로 규칙이 쉬울 때도 있다.

줄바꿈…… 빠뜨리지말것.

#include <iostream>
#include <algorithm>
long long dp[101] = { 0,1,1,1,2,2,3,4,5,7,9 };
using namespace std;
int main() {
	int t;
	scanf_s("%d",&t);
	for (int i = 11; i < 101; i++) {
		dp[i] = dp[i - 1] + dp[i - 5];
	}
	while (t--) {
		int n;
		scanf_s("%d", &n);
		printf("%lli\n", dp[n]);
	}
	return 0;
}