알고리즘 문제
[C/C++ 백준 6359번] 만취한 상범 (Bronze 2)
새파란 공대생
2020. 5. 15. 18:28
https://www.acmicpc.net/problem/6359
6359번: 만취한 상범
문제 서강대학교 곤자가 기숙사의 지하에는 n개의 방이 일렬로 늘어선 감옥이 있다. 각 방에는 벌점을 많이 받은 학생이 구금되어있다. 그러던 어느 날, 감옥 간수인 상범이는 지루한 나머지 정�
www.acmicpc.net
dp배열을 방이 i개 있을시 탈출가능한 사람수로 하자. 새로운 방이 추가되는 말든 전에 빠져나갈 사람은 빠져나가니, dp[i+1]을 짤때는 i+1번째 사람이 탈출할지만 고려해 dp[i]+1아니면 dp[i]를 하면 된다. 탈출은 약수의 개수가 홀수일때 가능하다.
#include <cstdio>
int canyouescape(int n){
int cnt=0;
for(int i=1; i<=n; i++)
if(n%i==0)
cnt++;
return cnt;
}//걍 약수구하는 함수임
int main(void){
int T, room, dp[101]={0,1};
scanf("%d",&T);
for(int j=2; j<=100; j++){
if(canyouescape(j)%2!=0)//약수의 개수가 홀수일 경우
dp[j]=dp[j-1]+1;
else
dp[j]=dp[j-1];//짝수
}
for(int i=1; i<=T; i++){
scanf("%d",&room);
printf("%d\n",dp[room]);
}
}