침대 밖은 위험해!

문제출처 : https://www.acmicpc.net/problem/2225

1. 문제요약

- 0 부터 N까지의 정수 K개를 더해서 그 합이 N이 되는 경우의 수

- 1 + 2와 2 + 1은 다른 경우

- 숫자는 중복해서 사용 가능

- 1 <= N <= 200

- 1 <= K <= 200

2. 접근방법

- 숫자 N은 N-0 + 0

               N-1 + 1

               N-2 + 2

               N-3 + 3

               ...

               N-N + N

  으로 만들 수 있음

- d[n][k] : K번째 합이 N인 경우의 수라 하면

- d[n][k] = d[n-0][k-1] + d[n-1][k-1] + d[n-2][k-1] + ... + d[n-n][k-1]

3. 시간복잡도

- O(KN^2) = 8,000,000

4. 회고

- 합산 결과가 int를 넘는가?

- 재귀 리턴값이 옳바른가?

- mod 연산 할때

- <소스 2> 처럼 했었는데 틀리고 <소스 1>은 맞음

- <소스 2> : d[sum][cnt] = (A mod div + B mod div + ... N mod div) mod div 가 들어가고

  <소스 1> : d[sum][cnt] = (A mod div + B mod div + ... N mod div) mod div 가 들어가는데?

- 어라 근데 return d[sum][cnt] %= div 인데.. 연산자 우선순위 때문인가? 괄호 안쳐서 그런가?

  해봐야겠다

- <소스 1>은 맞고 <소스 2>가 틀린 이유는 '메모이제이션' 때문....

- <소스 1>의 d 배열에는 나머지 값이 들어가 있어서 line 6에서 정상적으로 나머지값이 반환됨.

- <소스 2>의 d 배열에는 나머지 값이 들어가 있지 않아서 line 6에서 나머지 연산 전의 값이 반환됨.

  <소스 2>의 line 6를 return d[sum][cnt] % div로 바꿔주면 정답

- <소스 2>의 line 11을 return d[sum][cnt] %= div로 바꿔주면 제일 빨리 수행됨

  나머지 연산이 덧셈 때 마다들어가지 않기 때문에

- 예를 들어 div = 5일 때,

  1 1 1   1 1 1   1 1 1

    3         3        3

              9 // <소스 1>은 9div5 = 4가 저장되고 / <소스 2>는 9가 저장됨

              ...

              12 // <소스 1>과 <소스 2> 모두 합은 4 + 4 + 4 이지만

                     <소스 1>은 12div5 = 2가 <소스 2>는 12가 저장됨

                      메모이제이션할때 저장된 값을 리턴하면

                     <소스 1>은 2를 <소스 2> 는 12를 리턴하므로 틀린 값이 나옴

                     그래서 <소스 2>의 line 6를 return d[sum][cnt] % div로 바꿔주면 정답이 됨.

long long dp(int sum, int cnt){
	if (cnt == 1)
		return 1;

	if (d[sum][cnt])
		return d[sum][cnt];

	for (int i = 0; i <= sum; i++){
		d[sum][cnt] += dp(sum - i, cnt - 1);
		d[sum][cnt] %= 1000000000;
	}

	return d[sum][cnt];
}

<소스 1>

long long dp(int sum, int cnt){
	if (cnt == 1)
		return 1;

	if (d[sum][cnt])
		return d[sum][cnt];

	for (int i = 0; i <= sum; i++)
		d[sum][cnt] += dp(sum - i, cnt - 1);

	return d[sum][cnt] % 1000000000;
}

<소스 2>

소스코드 : Top-Down

#include<iostream>
using namespace std;

int n, k;
long long d[201][201];

long long dp(int sum, int cnt){
	if (cnt == 1)
		return 1;

	if (d[sum][cnt])
		return d[sum][cnt];

	for (int i = 0; i <= sum; i++){
		d[sum][cnt] += dp(sum - i, cnt - 1);
		d[sum][cnt] %= 1000000000;
	}

	return d[sum][cnt];
}

int main(void){
	cin >> n >> k;
	cout << dp(n, k) << "\n";
	return 0;
}

소스코드 : Bottom-Up

#include<iostream>
using namespace std;

int n, k;
long long d[201][201];

int main(void){
	cin >> n >> k;
	d[0][0] = 1;

	for (int i = 1; i <= k; i++){
		for (int j = 0; j <= n; j++){
			for (int k = 0; k <= j; k++){
				d[j][i] += d[j - k][i - 1];
				d[j][i] %= 1000000000;
			}
		}
	}

	cout << d[n][k] << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]

문제출처 : https://www.acmicpc.net/problem/9461

1. 문제요약

- 아래 그림처럼 정삼각형을 이어붙임

- 해당 나선 그림에서 가장 긴 변의 길이를 k라 했을 떄, 그 변에 길이가 k인 정삼각형을 추가

- 파도반 수열 p[n]은 나선에 있는 정삼각형의 한 변의 길이

  p[1] ~ p[10]까지 1, 1, 1, 2, 2, 3, 4, 5, 7, 9

- 1 <= n <= 100일때 p[n]의 값은?

2. 접근방법

- 수열의 규칙 찾기

- p[n] = p[n-1] + p[n-5]

3. 시간복잡도

- n

4. 회고

- p[n]의 값이 int 범위를 넘어감.

- 가장 작은 입력, 가장 큰 입력에 대해 테스트 필요함

소스코드

#include<iostream>
using namespace std;

int t, n;
long long p[101] = { 0, 1, 1, 1, 2, 2 };

int main(void){
	for (int i = 6; i < 101; i++)
		p[i] = p[i - 1] + p[i - 5];
	cin >> t;
	while (t--){
		cin >> n;
		cout << p[n] << "\n";
	}
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]

문제출처 : https://www.acmicpc.net/problem/1699

1. 문제요약

- 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있음

- 11 = 3^2 + 1^2 + 1^2(3개항)

  11 = 2^2 + 2^2 + 1^2 + 1^2 + 1^2(5개항)

- 11의 최소 제곱수 항의 갯수는 3개

- 자연수 N의 최소 제곱수 항의 갯수는?

- 1 <= N <= 100,000

2. 접근방법

- 임의의 정수 N에서

  1^2을 빼면 N-1

  2^2을 빼면 N-4

  ...

- d[n] 을 n의 최소 제곱수 갯수 라고 하면

  d[n] = min(d[0] + 1, d[1] + 1, d[2] + 1, d[3] + 1 ..., d[i <= j * j] + 1)

3. 시간복잡도

- 1 ~ 3 : 1 = 3

  4 ~ 8 : 2 = 2 * 5

  9 ~ 16 : 3 = 3 * 7

  17 ~ 25 : 4 = 4 * 9

  ...

- ∑(k = 1, 300)(2k + 1) * k = 2∑(k = 1, 300)k^2 + ∑(k = 1, 300)k

4. 회고

- 처음에 무조건 임의의 자연수 n에 가까운 제곱수를 구하면 되는 줄 알았는데

- 12 = 3^2 + 1^2 + 1^2 + 1^2 = 4개항

  12 = 2^2 + 2^2 + 2^2 = 3개항

※ 근데 맞은 소스랑 틀린 소스랑 차이가 없는데 왜 맞고 틀리지??????

채점 서버 문제였음..

소스코드 : 맞은 소스

#include <stdio.h>
#include <algorithm>
 
using namespace std;
 
int dp[100003];
 
int main() {
 
    int n;
    scanf("%d", &n);
    
    for (int i = 1; i <= n; i++) {
        dp[i] = 100000;
        for (int j = 1; j*j <= i; j++) {
            dp[i] = min(dp[i], dp[i - j*j] + 1);
        }
    }
 
    printf("%d\n", dp[n]);
 
}

소스 코드 : 틀린 소스 맞음

#include<iostream>
#include<algorithm>
using namespace std;

int n, d[100001];

int main(void){
	cin >> n;
	for (int i = 1; i <= n; i++){
		d[i] = 100000;
		for (int j = 1; j * j <= i; j++){
			d[i] = min(d[i], d[i - j * j] + 1);
		}
	}
	cout << d[n] << "\n";
	return 0;
}

[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]