BOJ 15667 - 2018 연세대학교 프로그래밍 경진대회 (Python3)

A528에서 수업을 들어 본 적은 없지만, 연세대학교 공학관에서 수업을 들어 본 적 있는 사람이라면 저 호수만 보고 찾아갈 수 있을 테다.

그런데 공학관은 6층까지 있다. A628은 무슨 죄지?

실제로 저 계획이 실행된다면 사비만 털릴 것 같지는 않다. 고맙다, 폭죽 판매처!

 

그럼 본격적으로 풀이에 돌입해 보자.

---

문제

2015, 2016, 2017년에 이어 올해도 연세대학교 컴퓨터과학과 프로그래밍 경진대회가 열린다.

도현이는 4년 연속 교내대회가 개최된다는 것에 감격하여, 사비를 털 각오로 화려한 개막식을 준비했다.

도현이가 원하는 것은 폭죽으로, 강의실 A528에서 천장을 다 뚫어버리며 터지는 화려한 폭죽을 모두가 좋아할 것이라 생각했다. 도현이는 아래와 같이 터지는 폭죽을 주문하려 한다.

 

1. 처음 발사된 폭죽이 만든 하나의 대형 불꽃은 적당한 높이에 도달하면 화려한 폭발과 함께 K개의 중형 불꽃으로 갈라진다.
2. 각 K개의 중형 불꽃은 다시 각각 K개의 소형 불꽃으로 갈라지며 터진다.
3. 그 이후 모든 불꽃은 소멸한다.

도현이는 적당한 폭죽을 찾아보려 했지만, 폭죽 판매처에서는 K의 값을 알려주지 않았고,

대신 폭죽 하나당 만들어지는 총 불꽃의 수(처음 터진 대형 불꽃을 포함해, 중형 불꽃과 소형 불꽃을 모두 포함한 수)만을 알려줬다. 결국 도현이는 어떤 폭죽이 적당할지 알아내지 못해 폭죽을 구매하지 못했다.

이에 도현이는 이 난제를 해결해주는 학생에게 이번 대회에서 맞은 문제 수를 하나 늘려주기로 하였다. 여러분은 대회에서 우승하기 위해, 폭죽이 만들 모든 불꽃의 개수가 주어지면 K의 값을 찾아보도록 하자.

 

입력

총 불꽃의 수 N이 주어진다. (3 ≤ N ≤ 10101)

 

예제 입력)

21

 

출력

K의 값을 출력한다. 이 값은 정수임이 보장되며, 불가능한 경우는 입력으로 주어지지 않는다.

 

예제 출력)

4

 

---

내 코드

# Ver 1.
from math import sqrt
n = int(input())
print(int(sqrt(4*n-3))//2)

# Ver 2.
print(int(int(input())**0.5))

 

처음 제출했던 코드는 Ver 1.

이 쪽은 \(4n-3=4k^2+4k+1=(2k+1)^2\)을 이용한 코드였는데, 생각해 보니 그것보다 더 간단한 게 실존했다.

\(k^2<k^2+k+1=n<(k+1)^2\)이니, 인풋받은 값에 루트를 씌우면 그 정수 부분이 바로 k가 될 것이다.

그대로 코드를 짜 주면 끝.

 

이로서 15667번의 풀이를 마친다.

그럼, 오늘도 당신의 코딩 실력이 상승하기를.