[백준/파이썬] 1568번 새 풀이

---

• 백준 문제풀이 전체 목록 보기

---

문제 정보

• 문제 출처: 백준 온라인 저지
• 문제 링크: 1568번 새
• 문제풀이 코드 GitHub 링크
• 제출 언어: Python 3

풀이

문제

N마리의 새가 나무에 앉아있고, 자연수를 배우기 원한다. 새들은 1부터 모든 자연수를 오름차순으로 노래한다. 어떤 숫자 K를 노래할 때, K마리의 새가 나무에서 하늘을 향해 날아간다. 만약, 현재 나무에 앉아있는 새의 수가 지금 불러야 하는 수 보다 작을 때는, 1부터 게임을 다시 시작한다.

나무에 앉아 있는 새의 수 N이 주어질 때, 하나의 수를 노래하는데 1초가 걸린다고 하면, 모든 새가 날아가기까지 총 몇 초가 걸리는지 출력하는 프로그램을 작성하시오.

• 자세한 문제 및 입출력 예제는 상단의 문제 출처(백준 홈페이지)를 참조해주세요

코드

n=int(input())
s=0
while n > 0:
    k=int(((1+8*n)**.5-1))//2
    s+=k
    n-=k*(k+1)//2
print(s)

설명

간단한 문제입니다.

이중반복을 돌려도 풀 수는 있지만, n이 10^9일때 O(n^2)의 방식으로는 오래걸리기 때문에 O(n)인 방법을 사용하겠습니다.

고등학교 때 1~n까지의 합은 n(n+1)/2라는 공식을 배운 적이 있을 것입니다. 공식이 기억나지 않는다고 해도 수열의 합 공식을 이용하면 금방 구할 수 있는 식이죠.

이를 응용할 것입니다. 즉, 다시 1초가 걸리기 전까지 최대 몇초까지 노래를 부를수 있는지를 이 공식을 통해 구하는 것이죠. 해당 초를 편의상 k라고 하고, k(k+1)//2 <= n인 최대의 k 값을 구하면 됩니다.

이를 정리하면 k^2 + k - 2*n <= 0이죠.

근의 공식을 이용하되, k와 n은 모두 정수인 점을 감안하면, 최대의 k는 k=int(((1+8*n)**.5-1))//2가 됩니다.

반복문을 계속 돌리며 해당 값을 빼주고, 걸리는 초 만큼 계속 변수 s에 더해줍시다.

모든 과정이 끝나고 나면, s를 출력합니다.

---

• 백준 문제풀이 전체 목록 보기

---