백준 21756(지우개)

문제 링크

21756번: 지우개 (acmicpc.net)

21756번: 지우개

---

문제

 N개의 칸에 1부터 N까지의 수들이 왼쪽부터 순서대로 저장되어 있다. 또, 각 칸은 왼쪽부터 1부터 N까지 순서대로 번호가 붙어 있다. 즉, 처음에는 각 칸의 번호와 각 칸에 저장된 수가 같다.

아래 그림은 N=7일 때의 예이다.

다음 작업을 수가 정확히 하나가 남을 때 까지 반복한다.

(A) 홀수번 칸의 수들을 모두 지운다 (B) 남은 수들을 왼쪽으로 모은다.

제일 첫 작업의 (A) 단계가 끝나면 칸들의 상태는 다음과 같을 것이다.

(B) 단계가 끝나면 다음과 같을 것이다.

두번째 작업이 진행되면 칸들은 아래 두 그림과 같이 바뀔 것이다.

이제 수가 하나 남았으므로 작업은 더 이상 진행되지 않는다.

 N을 입력으로 받아 위와 같이 작업을 진행했을 때 마지막으로 남는 수를 계산하는 프로그램을 작성하라.

---

입력

첫 번째 줄에 정수 N이 주어진다.

---

출력

마지막으로 남는 수를 한 줄에 출력한다.

---

제한

---

서브태스크

번호	배점	제한
1	5	입출력 예제만이 주어짐
2	15	N <= 8
3	30	N은  1,2,4,8,16,32,64 중 하나이다. 즉, N은 1이거나, 2이거나, 2를 여러 번 곱한 수 중 하나이다.
4	50	추가 제약 조건 없음

---

예제 입력 1                                                                                                  예제 출력 1

     1                                                                                                                1

---

예제 입력 2                                                                                                  예제 출력 2

     2                                                                                                               2

---

예제 입력 3                                                                                                  예제 출력 3

     5                                                                                                               4

---

소스 코드

#include <stdio.h>

int a[200], b[200];
int main()
{
	int n, i, j;
	scanf("%d", &n);
	for (i = 0; i < n; i++) //a배열에 1부터 n까지의 숫자로 채운다.
	{
		a[i] = i + 1;
	}

	// n = a 배열의 크기
	while(n > 1)
	{
		// 만약 i / 2를 했을 때 나머지가 1이라면 홀수이므로 b[j]번째에 a[i]번쨰 값을 넣는다.
		// n = a 배열의 크기
		// i = 배열 a의 현재 탐색 위치 (탐색)
		// j = 배열 b의 현재 저장 위치 (저장)
		j = 0;
		for (i = 0; i < n; i++)
		{
			if (i % 2 == 1)
			{
				b[j] = a[i];
				j++;
			}
		}

		// 해야할 일 : b 배열의 값을 a배열에 전부 복사한다.
		// i = b배열의 현재 탐색 위치
		// j = b배열의 크기
		for (i = 0; i < j; i++)
		{
			a[i] = b[i];
		}
		n = j;
	}
	
	for (int i = 0; i < n; i++) //a배열 값을 출력한다.
	{
		printf("%d ", a[i]);
	}
	printf("\n");
	return 0;
}