오늘의 공부

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

다이나믹 프로그래밍으로 분류되어 있는 문제이며 재귀의 방식으로 문제를 해결하였다.

n에서 1을 뺐을 때 정수 N을 만드는 경우의 수 D[n]은 

D[n] = D[n-1] + 1 이다.

또한 n을 2로 나누었을 때 정수 N을 만드는 경우의 수 D[n]은

D[n/2] = D[n/2] + 1 이고

n을 3으로 나누었을 때 정수 N을 만드는 경우의 수 D[n]은

D[n/3] = D[n/3] + 1 이다. 

그러므로

n에서 1을 뺐을 때의 값을 먼저 저장해두고

n이 2로 나누어 떨어지면 2로 나누었을 때의 값을 계산하고

2로 나누었을 때의 값이 이미 저장된 d[n]보다 작을 때

현재 저장된 d[n]의 값을 2로 나누었을 때의 값과 바꾸어 준다.

3으로 나누어 떨어지면 위와 같은 방식으로 값을 비교한다. 

1을 먼저 빼고 2를 나누고 3을 나누는 순으로 구성한 이유는 N은 3으로 나누었을 때 가장 작은 수가 되기 때문이다. 

그래서 경우의 수가 더 작게 나올 확률이 크다.

#include <iostream>

using namespace std;
const int MAX_NUM = 1000000;

int d[MAX_NUM];

int cal(int n)
{

	if (n == 1)return 0;
	if (d[n] > 0) return d[n];

	d[n] = cal(n - 1) + 1;

	if (n % 2 == 0) {
		int temp = cal(n / 2) + 1;
		if (temp < d[n]) {
			d[n] = temp;
		}

	}

	if (n % 3 ==0) {
		int temp = cal(n / 3) + 1;
		if (temp < d[n]) {
			d[n] = temp;
		}
	}
	return d[n];
}
int main()
{
	int n;
	cin >> n;
	cout << cal(n) << endl;
}

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

팩토리얼은 자연수 n을 이용하여 기호로는 간단하게 n!로 나타내며 1부터 n까지의 자연수를 모두 곱하는 것을 의미한다. 

n! = n x (n-1) x (n-2) x .... x 3 x 2 x 1

이 정의를 이용해 재귀함수를 호출해주면서 구하면 된다. 

ex ) n = 5일 때

fac(5) => fac(4) * 5

fac(4) => fac(3) * 4

fac(3) => fac(2) * 3

fac(2) => (fac(1) == return 1) 1 * 2

그러면 5*4*3*2*1이 된다. 

여기서 헷갈릴 수 있는 부분은 0! 일 때이다.

0!은 0이 아닌 1이다. 

아무것도 안 더하면 0이듯이 아무것도 안 곱하면 1이기 때문이다. 

0!은 1부터 0까지 자연수를 곱하는 것이기 때문에 아무것도 곱하지 않아서 그대로 1이 나온다고 한다. 

#include <iostream>

using namespace std;


int fac(int n)
{
	if (n == 1 || n == 0) return 1;
	return fac(n - 1) * n;

}
int main()
{

	int T;
	cin >> T;

	cout << fac(T);

}

#include <iostream>

using namespace std;


int fac(int n)
{
	return n == 0 ? 1 : n*fac(n-1) ;
}
int main()
{

	int T;
	cin >> T;

	cout << fac(T);

}

예상치 못한 실수

출처 

팩토리얼 https://namu.wiki/w/%ED%8C%A9%ED%86%A0%EB%A6%AC%EC%96%BC

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

문제

이렇게 감옥이 n개가 있는데 

첫 번째 잔을 마신 후에는 다 열고

두 번째 잔을 마신 후에는 2의 배수번 째 방을 다 잠그고

세 번째 잔을 마신 후에는 3의 배수 번 째 방을 확인하는데 잠겨있으면 열고 열려 있으면 잠근다.

즉, 두 번째 잔을 마신 후 잠궈놓은 2,4,6... 2의 배수 번째 방은 세 번 째 잔을 마신 후에는 겹치는 방인 6,12,18,24... 번째 방은 다시 열고 3,9,15,21... 번째의 방은 다 잠근다.

이렇게 n번째(=감옥의 방 개수) 잔까지 마신 후 끝난다.

생각보다 간단했다. 

일단 처음에 모든 방을 true로 바꿔준 후(첫 번째 방은 모두 다 열었으므로)

두 번째, 세 번째,... n번 째까지 돌면서 n의 배수번째 방을 확인하며 true이면 false로 false이면 true로 바꿔준 후 마지막에 true인 방의 갯수를 세었다. 

조금 비효율적으로 푼 것 같긴한데 차차 생각해볼 문제인 것 같다. 

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

const int MAX_ROOM = 100;


int Escape(int room)
{
	bool r[MAX_ROOM + 2];
	memset(r, true, sizeof(bool)*(room+2));
	for (int i = 2; i <= room; i++)
	{
		for (int j = 1; j <= room; j++) {
			if (j % i == 0) {			
				r[j] = !r[j];
			}
		}
	}

	int count = 0;
	for (int i = 1; i <= room; i++) {
		if (r[i]) {
			count += 1;
		}
	}
	return count;
}


int main()
{
	int T = 0;
	cin >> T;

	vector<int> TestCase(T + 1);

	for (int i = 1; i <= T; i++) {
		cin >> TestCase[i];
	}

	for (int i = 1; i <= T; i++) {

		cout << Escape(TestCase[i]) << endl;
	}

}

내가 처음 문제를 읽고는 감옥의 갯수로 주어지는 n개와 상범이가 마시고 취하는 횟수인 n을 서로 다른 조건으로 보고 취하는 횟수는 언제 주는지 의아해했다.

(그럴 리가 없다고 생각했던 게 제일 컸던 것 같다. ;;) 

그리고 나는 visual studio 2017을 사용하는데 백준 문제를 제출할 때 memset을 쓰는 경우 헤더에

#include <memory.h>를 추가해야 컴파일 에러가 나지 않는다. 

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

이 문제는 다이나믹 프로그래밍 방식으로 풀면 되는 문제로

제일 마지막에 올 타일이

2x2 의 타일과 1x2 타일을 가로로 두 개 두는 경우, 그리고 2x1의 타일을 세로로 한 개 두는 경우.

이렇게 세 가지 방법이 있다고 가정하고 풀면 된다.

재귀 호출 방식으로

2x1와 2x2 타일이 제일 마지막에 위치하는 경우는 solution(n-2)를 두 번 호출 하고

1x2 타일이 제일 마지막에 위치하는 경우 solution(n-1)을 더해줬다. 

#include <iostream>

using namespace std;
int d[1001];

int solution(int n)
{
	if (d[n] > 0)return d[n];
	if (n == 1 || n == 0) return 1;

	d[n] = (2 * solution(n - 2) + solution(n - 1)) % 10007;

	return d[n];
}

int main()
{
	int n;
	cin >> n;
	cout << solution(n) << endl;
}