171016_6359_만취한 상범

#include <iostream> using namespace std; int nod(int n) //number of divisor= 약수의 개수 {     int num=0;     for(int i=2;i<=n;i++) if(n%i==0) num++;     return num%2 == 1 ? 0:1; } int main() {     int T=0;     cin >> T;     for(int j=0; j<T; j++)     {         int n;         int dp[101]={0};         cin >> n;              dp[5]=2;         for(int i=6; i<=n; i++)         {             dp[i]=dp[i-1]+nod(i);         }     cout << dp[n] << endl;     } }

nod 이름은 약수의 개수로 지었지만

사실상 1을 제외한 약수의 개수가 홀수면(num%2 == 1 이면) 0반환, 짝수면(num%2 != 1, 즉 0이면) 1반환

n=5일 때 5라운드까지 실행한 결과는 다음과 같다. (1 열림, 0 닫힘)

1라운드	1	1	1	1	1
2라운드	1	0	1	0	1
3라운드	1	0	0	0	1
4라운드	1	0	0	1	1
5라운드	1	0	0	1	0

1,2,3,,,,n회차까지 살펴보면, 

1회 이 후에는 1을 건들지 않음. 즉 dp[2]=dp[1]+a;

2회 이 후에는 1,2를 건들지 않음, 즉 dp[3]= dp[2]+a;

.

.

.

n-1회 이 후에는 1,2,3,...,n-1을 건들지 않음, 즉, dp[n]=dp[n-1]+a;

n= 6일 때를 보자 

1라운드	1	1	1	1	1	1
2라운드	1	0	1	0	1	0
3라운드	1	0	0	0	1	1
4라운드	1	0	0	1	1	1
5라운드	1	0	0	1	0	1
6라운드	1	0	0	1	0	0

6번째 감옥 문의 상태가 변하는 지점을 보면

1->2, 2->3, 5->6

즉, 2,3,6이 될 때이다. 2, 3, 6은 6의 1을 제외한 약수이다.

즉, 1을 제외한 약수의 수가 홀수 개라면, 1->0->1->0->,,,->0 결과는 0이되고

1을 제외한 약수의 수가 짝수 개라면,  1->0->1->0->,,,->1 결과는 1이 된다.

dp[i]값은 dp[i-1]+(약수의 개수가짝수면1, 홀수면 0) (nod 함수)

이 된다.