[6359] 만취한 성범

• 분류: 동적계획
• 난이도: 하
• 입력: 테스트 케이스 T, 문의 개수 N
• 출력: 열려있는 문의 총 개수
• 소스

#include <iostream>
using namespace std;

int main(){
	int testcase;
	cin >> testcase;
	for (int i = 0; i < testcase; i++){
		int n, squre = 1;
		cin >> n;
		for (; squre*squre <= n;squre++);
		cout << squre - 1 << endl;
	}
	return 0;
}

• 소스 설명: 원래 동적계획을 사용해서 풀어야하지만, 직접 해본 결과 약수의 개수가 홀수여야 open이 된다. 약수가 홀수개이려면 제곱수여야 하므로 n까지의 제곱의 수를 세는 방법으로 했다. 동적계획으로는 했을때, 좀 더 생각을 해봐야겠다.
• 참고사이트: https://www.acmicpc.net/problem/6359