[백준 BOJ] 13909번 창문 닫기 (C++/cpp)

문제 설명

https://www.acmicpc.net/problem/13909

13909번: 창문 닫기

 

접근 방법 - 소인수분해의 기초 문제

백준의 13909번 문제는 소인수분해와 관련한 기초적인 원리를 다루고 있는 문제이다.

해당 문제는, 입력값만큼 창문이 있으며 특정 규칙에 따라 창문을 여닫을 때 열려있는 창문의 개수를 출력해야 하는 문제이다.

이때 특정 규칙이란, n번째 사람은 n의 배수인 번호의 창문을 열거나 닫아야 한다는 것이다.

문제에도 이미 예시가 하나 나와있지만, 조금 더 큰 수에 대한 예시를 들어보고자 한다.

(ex) 입력값이 8일 때,
(0: 닫혀있는 창문, 1: 열려있는 창문)

0000 0000 -> 처음 창문의 상태
1111 1111 -> 1번째 사람이 여닫은 뒤
1010 1010 -> 2번째 사람이 여닫은 뒤
1000 1110 -> 3번째 사람이 여닫은 뒤
1001 1111 -> 4번째 사람이 여닫은 뒤
1001 0111 -> 5번째 사람이 여닫은 뒤
1001 0011 -> 6번째 사람이 여닫은 뒤
1001 0001 -> 7번째 사람이 여닫은 뒤
1001 0000 -> 8번째 사람이 여닫은 뒤

=> 결괏값: 2

배수의 개념이 끼어있다는 것은 곧, 약수의 개념과도 연관이 있을 수 있다는 점을 뜻한다.

그리고 문제와 위 예시를 살펴보면, 창문이 위치한 번호의 약수 개수만큼 창문이 여닫히는 것을 볼 수 있을 것이다.

그 말은 즉, 약수의 개수가 홀수개인 위치의 창문만 열려있게 된다는 것을 의미하기도 하다.

필자는 이 점을 발견하여 코드를 작성해보았고, 이를 통해 문제를 해결할 수 있었다.

혹여나 해당 문제를 해결하는 데에 어려움을 겪고 있다면, 아래의 설명과 코드를 참고해보길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 값(n)을 입력받는다.

(이때 입력값의 최댓값이 int형의 범위를 넘어서기 때문에, long long int형으로 입력받도록 하였다.)

(만약, 여기서 1을 입력받았다면 굳이 연산을 할 필요가 없기 때문에, 1을 출력하고 즉시 종료하도록 한다.)

 

2) 열린 창문의 개수를 카운팅할 변수 count를 0으로 초기화하여 선언한다.

 

3) 반복문을 통해, 아래와 같은 연산을 수행하도록 한다.

필자는 위에서도 언급했다시피, 약수의 개수가 홀수개인 위치의 창문만 열려있게 된다는 점을 이용할 것이다.
이때, 약수의 개수가 홀수개인 것은 제곱수뿐이다.
따라서 필자는, 제어 변수 i에 대하여 i의 제곱이 n보다 작거나 같을 때까지 수행하도록 하였고, 이 조건만 만족한다면 count에 1씩 추가하도록 하였다.

 

4) 모든 연산이 완료되었다면, 최종적으로 저장된 count의 값을 출력한 뒤 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#define endl '\n'
using namespace std;

//백준 13909번 코드
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	long long int n;
	cin >> n;
	if (n == 1) {
		cout << 1 << endl;
		return 0;
	}

	int count = 0;
	for (int i = 1; i * i <= n; i++) {
		count++;
	}
	cout << count << endl;
}

 

제출 결과

(2022.09.28 백준 13909번 문제 제출 결과)