[백준/파이썬] 14920번 풀이
업데이트:
문제 정보
- 문제 출처: 백준 온라인 저지
- 문제 링크: 14920번 문제
- 문제풀이 코드 GitHub 링크
- 제출 언어: Python 3
풀이
문제
다음의 점화식에 의해 정해지는 수열 C(n)을 생각하자:
C(n+1) = C(n)/2 (C(n)이 짝수일 때) = 3*C(n)+1 (C(n)이 홀수일 때)
초항 C(1)이 자연수로 주어지면, 이 점화식은 자연수로 이루어지는 수열을 정한다. 예를 들어, C(1)=26이면, 다음의 수열이 된다.
26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, 4, 2, 1, 4, 2, 1, …
이 경우, 수열의 뒷부분은 4, 2, 1 이 끝없이 반복된다. 실제로 C(1)이 5×260보다 작은 자연수인 모든 수열은 언젠가는 4, 2, 1로 끝나게 된다는 것이 알려져 있다.
주어진 입력 C(1)에 대하여 C(n)이 처음으로 1이 되는 n을 출력하시오.
입력 요약
C(1); 1 ≤ C(1) ≤ 100000
출력 요약
C(n)이 처음으로 1이 되는 n
코드
l=[int(input())]
while l[-1]!=1:l.append(l[-1]//2if l[-1]%2==0else l[-1]*3+1)
print(len(l))
설명
핵심은 구현 관점에서 다음의 점화식에 의해 정해지는 수열 C(n)을 생각하자:
C(n+1) = C(n)/2 (C(n)이 짝수일 때) = 3*C(n)+1 (C(n)이 홀수일 때) …를 만족하도록 로직을 구성하는 것입니다.
코드는 입력을 파싱한 뒤 조건 분기와 계산을 순서대로 수행하고, 문제에서 요구한 형식으로 결과를 출력합니다.
경계값과 예외 케이스도 함께 고려해 오답이 나기 쉬운 상황을 방지합니다.
댓글남기기