문제 개요
크기가 N인 배열이 주어지며, 처음에는 모든 요소가 0으로 초기화되어 있습니다. 이 배열에 총 N번의 이동(move)을 수행한 뒤, 최종 배열에 남아 있는 1의 개수를 구하는 것이 과제입니다. 각 i번째 이동에는 다음과 같은 규칙이 적용됩니다.
- 1번째 이동 – 위치 1, 2, 3, 4, … 에 있는 요소를 변경(토글)
- 2번째 이동 – 위치 2, 4, 6, 8, … 에 있는 요소를 변경(토글)
- 3번째 이동 – 위치 3, 6, 9, 12, … 에 있는 요소를 변경(토글)
즉, i번째 이동에서는 i의 배수에 해당하는 위치의 값을 뒤집습니다(0이면 1로, 1이면 0으로). 모든 이동이 끝난 후 배열에 남은 1의 개수를 세면 됩니다.
예제로 이해하기
입력
Arr[] = { 0, 0, 0, 0 }, N = 4출력
N번 이동 후 배열 내 1의 개수 − 2
설명 – 각 이동 후 배열의 상태는 다음과 같습니다.
Move 1: { 1, 1, 1, 1 }
Move 2: { 1, 0, 1, 0 }
Move 3: { 1, 0, 0, 0 }
Move 4: { 1, 0, 0, 1 }최종 배열의 1의 개수는 2입니다.
입력
Arr[] = { 0, 0, 0, 0, 0, 0 }, N = 6출력
N번 이동 후 배열 내 1의 개수 − 2
설명 – 각 이동 후 배열의 상태는 다음과 같습니다.
Move 1: { 1, 1, 1, 1, 1, 1 }
Move 2: { 1, 0, 1, 0, 1, 0 }
Move 3: { 1, 0, 0, 0, 1, 1 }
Move 4: { 1, 0, 0, 1, 1, 1 }
Move 5: { 1, 0, 0, 1, 0, 1 }
Move 6: { 1, 0, 0, 1, 0, 0 }최종 배열의 1의 개수는 역시 2입니다.
접근 방법
- 0으로 초기화된 정수 배열 Arr[]와 정수 N을 입력으로 받습니다.
- Onecount 함수는 배열과 크기 N을 매개변수로 받아, N번의 이동이 끝난 후 최종 배열에 남은 1의 개수를 반환합니다.
- 바깥쪽 for 루프는 i = 1부터 N까지 반복하며, 각 i는 i번째 이동을 나타냅니다.
- 안쪽 for 루프는 j = i부터 N까지 반복합니다.
- j가 i의 배수(j % i == 0)이면 해당 위치 arr[j-1]의 값을 토글합니다(0이면 1로, 1이면 0으로).
- 참고 – 이동의 기준 위치는 1부터 시작하지만 배열 인덱스는 0부터 N-1까지이므로 항상 arr[j-1]을 사용해야 합니다.
- 모든 이동이 끝나면 배열을 한 번 더 순회하며 1의 개수를 세어 count에 저장한 뒤 반환합니다.
C 언어 구현 예제
#include <stdio.h>
int Onecount(int arr[], int N){
for (int i = 1; i <= N; i++) {
for (int j = i; j <= N; j++) {
// j가 i로 나누어떨어지는 경우
if (j % i == 0) {
if (arr[j - 1] == 0)
arr[j - 1] = 1; // 0을 1로 변환
else
arr[j - 1] = 0; // 1을 0으로 변환
}
}
}
int count = 0;
for (int i = 0; i < N; i++)
if (arr[i] == 1)
count++; // 1의 개수 카운트
return count;
}
int main(){
int size = 6;
int Arr[6] = { 0 };
printf("N번 이동 후 배열 내 1의 개수: %d", Onecount(Arr, size));
return 0;
}실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
N번 이동 후 배열 내 1의 개수: 2
수학적 배경: 답은 왜 완전제곱수의 개수일까?
위치 k의 값은 k의 약수 개수만큼 토글됩니다. 예를 들어 위치 6은 1, 2, 3, 6번째 이동에서 총 4번 뒤집히므로 최종적으로 0이 됩니다. 약수가 홀수 개인 자연수는 오직 완전제곱수뿐이므로, N번의 이동 후 값이 1로 남는 위치는 1, 4, 9, 16, … 즉 N 이하의 완전제곱수뿐입니다. 따라서 정답은 ⌊√N⌋이며, 위 예제(N = 4, N = 6)에서 답이 모두 2였던 이유도 4 이하의 완전제곱수는 1, 4 / 6 이하의 완전제곱수는 1, 4이기 때문입니다.
시간 복잡도는 바깥 루프 i마다 안쪽 루프가 N/i번 실행되므로 조화급수에 따라 약 O(N log N)이며, 공간 복잡도는 O(N)입니다.