백준 6359번: 만취한 상범

[문제 링크]

6359번: 만취한 상범

---

k번째 방이 열려있거나 닫혀있는 경우는 k의 약수 갯수와 연관이 있다.

k의 약수 갯수가 홀수개라면 문이 열려있고, 짝수개라면 문이 닫혀있다는 것을 알 수 있다.

 

또한 n개의 방이 있을 때 n-1번째까지의 방은 방의 갯수가 늘어났다고하여 값이 변하는 것이 아닌 n-1개의 방이 있을 때 열려있는 문의 갯수와 동일하기 때문에 이를 메모이제이션하면 빠르게 정답을 구할 수 있다.

---

#include <iostream>
using namespace std;

int memo[101];

int Topdown(int N)
{
	if (N == 1) return 1;

	int& ret = memo[N];
	if (ret != 0) return ret;

	int cnt = 0;
	for (int i = 1; i <= N; i++)
		if (N % i == 0) cnt++;

	return ret = Topdown(N - 1) + (cnt % 2);
}

int Bottomup(int N)
{
	memo[1] = 1;

	for (int i = 2; i <= N; i++)
	{
		int cnt = 0;
		for (int j = 1; j <= i; j++)
			if (i % j == 0) cnt++;

		memo[i] = memo[i - 1] + (cnt % 2);
	}
    
	return memo[N];
}

int main(void)
{
	int tc;
	cin >> tc;

	while (tc--)
	{
		int N;
		cin >> N;

		cout << Topdown(N) << endl;

		cout << Bottomup(N) << endl;
	}

	return 0;
}

알고리즘 200일 프로젝트 - 92 day