반응형
알고리즘 분류에는 DP라고 나와있는데 왜 DP인지 모르겠음! 규칙성 찾는 문제 같음
나중에 DP로 다시 풀어보기!!!!!!!!!!!!**
문제풀이 - 알고리즘(규칙성)
1. 홀수번 열고닫고 할 경우 마지막에 열려있음! (탈출 가능)
ex) 열고닫고 7번
열 닫 열 닫 열 닫 열 : 결과적으로 열려있음
2. 방 번호의 약수번째 라운드마다 문을 열어줌
ex) 방번호 6
라운드 1: 열고
라운드 2: 열고
라운드 3: 열고
라운드 6: 열고
두 가지 규칙을 기반으로 n의 약수의 개수가 홀수개일 경우 최종적으로(n번째 라운드에서) 문이 열려있게 된다.
그렇다면 약수의 개수가 홀수개인 경우는? => 어떤 수의 제곱 수
ex) 2의 약수 : 1, 2 => 2개
3의 약수 : 1, 3 => 2개
4의 약수 : 1, 2, 4 => 3개
5의 약수 : 1, 5 => 2개
....
9의 약수 : 1, 3, 9 => 3개
....
16의 약수 : 1, 2, 4, 8, 16 => 5개
#include <iostream>
using namespace std;
int main() {
int tc;
cin >> tc;
for (int i = 0; i < tc; i++) {
int temp;
cin >> temp;
int answer = 1;
while (temp>=answer*answer) {
answer++;
}
cout << answer - 1 << endl;
}
return 0;
}
반응형
