[백준 / Go] 13909번: 창문 닫기

문제

13909번: 창문 닫기

서강대학교 컴퓨터공학과 실습실 R912호에는 현재 N개의 창문이 있고 또 N명의 사람이 있다. 1번째 사람은 1의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다.  2번째 사람은 2의 배수 번째 창문을 열려 있으면 닫고 닫혀 있으면 연다. 이러한 행동을 N번째 사람까지 진행한 후 열려 있는 창문의 개수를 구하라. 단, 처음에 모든 창문은 닫혀 있다.

예를 들어 현재 3개의 창문이 있고 3명의 사람이 있을 때,

1. 1번째 사람은 1의 배수인 1,2,3번 창문을 연다. (1, 1, 1)
2. 2번째 사람은 2의 배수인 2번 창문을 닫는다. (1, 0, 1)
3. 3번째 사람은 3의 배수인 3번 창문을 닫는다. (1, 0, 0)

결과적으로 마지막에 열려 있는 창문의 개수는 1개 이다.

---

문제 이해하기

 처음에 모든 창문이 닫혀있으므로 i번째 창문이 열려있으려면, i번째 창문에 대한 행동을 홀수번 수행해야 합니다. i번째 창문을 열고 닫는 행동은 i보다 작거나 같은 자연수의 배수가 i인 경우에만 수행됩니다. 즉, i번째 창문의 약수의 개수가 홀수 개인 경우에 창문이 열려있게 됩니다. 

 

 약수의 개수가 홀수 개인 수는 제곱수입니다. 제곱근이 제곱수의 약수의 개수를 홀수로 만들어주죠. 따라서 N보다 작거나 같은 수 중에 제곱수의 개수를 세면 열려 있는 모든 창문의 개수를 구할 수 있습니다.

---

코드

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
)

var (
	scanner = bufio.NewScanner(os.Stdin)
	writer  = bufio.NewWriter(os.Stdout)

	N int
)

func main() {
	defer writer.Flush()
	scanner.Split(bufio.ScanWords)

	Setup()
	Solve()
}

func Setup() {
	N = scanInt()
}

func Solve() {
	// 1~N 중에 약수의 개수가 홀수인 수의 개수를 구해야 한다.
	// 약수의 개수가 홀수인 수는 제곱수이다.
	// 제곱수의 개수를 구하면 된다.
	ans := 0
	for i := 1; i*i <= N; i++ {
		ans++
	}

	fmt.Fprintln(writer, ans)
}

func scanString() string {
	scanner.Scan()
	return scanner.Text()
}

func mustParseInt(s string) int {
	n, _ := strconv.Atoi(s)
	return n
}

func scanInt() int {
	return mustParseInt(scanString())
}

시간: 4 ms

메모리: 856 KB

분류: 수학, 정수론

글에서 수정이 필요한 부분이나 설명이 부족한 부분이 있다면 댓글로 남겨주세요!