4030 : 동전 뒤집기 게임
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 5
•통과: 3
•만든사람: suakii
문제 설명
$N$개의 동전이 일렬로 놓여 있다. 처음에는 모두 앞면이다.
$i = 1$부터 $N$까지, $i$번째 턴에는 $i$의 배수에 해당하는 위치의 동전을 뒤집는다.
예를 들어 $i=2$이면 2, 4, 6, 8...번 위치의 동전을 뒤집고, $i=3$이면 3, 6, 9...번 위치의 동전을 뒤집는다.
$N$번의 턴이 모두 끝난 후, 뒷면이 된 동전의 위치를 오름차순으로 출력하라.
뒷면인 동전이 없으면
[제약 조건]
• $1 \le N \le 100$
• $N$은 정수
$i = 1$부터 $N$까지, $i$번째 턴에는 $i$의 배수에 해당하는 위치의 동전을 뒤집는다.
예를 들어 $i=2$이면 2, 4, 6, 8...번 위치의 동전을 뒤집고, $i=3$이면 3, 6, 9...번 위치의 동전을 뒤집는다.
$N$번의 턴이 모두 끝난 후, 뒷면이 된 동전의 위치를 오름차순으로 출력하라.
뒷면인 동전이 없으면
없음을 출력하라.[제약 조건]
• $1 \le N \le 100$
• $N$은 정수
입력 설명
첫째 줄에 정수 $N$이 주어집니다.
출력 설명
뒷면인 동전의 위치를 오름차순으로 공백으로 구분하여 출력한다.
뒷면인 동전이 없으면
뒷면인 동전이 없으면
없음을 출력한다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
1
출력 예시
COPY
복사되었습니다!
복사되었습니다!
1도움
$k$번 위치의 동전은 $k$의 약수 개수만큼 뒤집힌다.
약수의 개수가 홀수인 수는 완전제곱수이다. (1, 4, 9, 16, 25, ...)
따라서 $N$ 이하의 완전제곱수 위치만 뒷면이 된다.
약수의 개수가 홀수인 수는 완전제곱수이다. (1, 4, 9, 16, 25, ...)
따라서 $N$ 이하의 완전제곱수 위치만 뒷면이 된다.