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

 

10872번: 팩토리얼

0보다 크거나 같은 정수 N이 주어진다. 이때, N!을 출력하는 프로그램을 작성하시오.

www.acmicpc.net

 

팩토리얼은 자연수 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);

}

 

예상치 못한 실수

더보기

간단하게 생각했던 문제에서 시간 초과 에러가 발생하여 당황했다.

찾아보니 n이 0일 때의 조건을 주지 않아서 시간초과가 발생했던 것이었다.

그러면서 0!이 1이라는 것도 알았다. 

당연히 당연히 0을 곱한다고 생각하고 있었던 것 같다. 

더 꼼꼼히 문제를 푸는 연습을 해야 할 것 같다. 

 

 

 

출처 

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

 

팩토리얼 - 나무위키

이 저작물은 CC BY-NC-SA 2.0 KR에 따라 이용할 수 있습니다. (단, 라이선스가 명시된 일부 문서 및 삽화 제외) 기여하신 문서의 저작권은 각 기여자에게 있으며, 각 기여자는 기여하신 부분의 저작권을 갖습니다. 나무위키는 백과사전이 아니며 검증되지 않았거나, 편향적이거나, 잘못된 서술이 있을 수 있습니다. 나무위키는 위키위키입니다. 여러분이 직접 문서를 고칠 수 있으며, 다른 사람의 의견을 원할 경우 직접 토론을 발제할 수 있습니다.

namu.wiki

 

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

 

6359번: 만취한 상범

문제 서강대학교 곤자가 기숙사의 지하에는 n개의 방이 일렬로 늘어선 감옥이 있다. 각 방에는 벌점을 많이 받은 학생이 구금되어있다. 그러던 어느 날, 감옥 간수인 상범이는 지루한 나머지 정신나간 게임을 하기로 결정했다. 게임의 첫 번째 라운드에서 상범이는 위스키를 한 잔 들이키고, 달려가며 감옥을 한 개씩 모두 연다. 그 다음 라운드에서는 2, 4, 6, ... 번 방을 다시 잠그고, 세 번째 라운드에서는 3, 6, 9, ... 번 방이 열려있으면 잠그고

www.acmicpc.net

 

 

문제

더보기

서강대학교 곤자가 기숙사의 지하에는 n개의 방이 일렬로 늘어선 감옥이 있다. 각 방에는 벌점을 많이 받은 학생이 구금되어있다.

그러던 어느 날, 감옥 간수인 상범이는 지루한 나머지 정신나간 게임을 하기로 결정했다. 게임의 첫 번째 라운드에서 상범이는 위스키를 한 잔 들이키고, 달려가며 감옥을 한 개씩 모두 연다. 그 다음 라운드에서는 2, 4, 6, ... 번 방을 다시 잠그고, 세 번째 라운드에서는 3, 6, 9, ... 번 방이 열려있으면 잠그고, 잠겨있다면 연다. k번째 라운드에서는 번호가 k의 배수인 방이 열려 있으면 잠그고, 잠겨 있다면 연다. 이렇게 n번째 라운드까지 진행한 이후, 상범이는 위스키의 마지막 병을 마시고 쓰러져 잠든다.

구금되어있는 몇 명(어쩌면 0명)의 학생들은 자신의 방을 잠그지 않은 채 상범이가 쓰러져버렸단 것을 깨닫고 즉시 도망친다.

방의 개수가 주어졌을 때, 몇 명의 학생들이 도주할 수 있는지 알아보자.

 

이렇게 감옥이 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

 

11727번: 2×n 타일링 2

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

www.acmicpc.net

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

 

제일 마지막에 올 타일이

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

 

더보기

시간 초과 발생

처음에 저장하는 부분을 따로 두지 않아서 return d[n]을 해주지 않고 제출 했더니 시간 초과가 떴다. 

 

+ Recent posts