코딩테스트(백준 구현(IMPLEMENTATION) (14920번: 3n +1 수열))
문제
다음의 점화식에 의해 정해지는 수열 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
예제 입력 1 복사
26
예제 출력 1 복사
11
예제 입력 2 복사
7
예제 출력 2 복사
17
나의 풀이:
num = int(input()) # 숫자 num 입력받음
num_list = [num] 수열에 결과값을 저장할 리스트
while num != 1: # 1이 되기 전에
if num % 2 == 0: # 짝수면
num = num / 2
num_list.append(num) # num_list 에 추가
else: # 홀수면
num = 3 * num + 1
num_list.append(num) # num_list 에 추가
if num == 1: # 1이 되면 while 문 탈출
break
num_list = [int(i) for i in num_list] # num_list 값을 정수로 변환.
print(num_list.index(1)+1)
OR (이건 실행 안됌...)
num = int(input())
num_list = []
def sequence(num):
if num % 2 == 0:
next_value = num / 2
num_list.append(next_value)
return sequence(next_value)
else:
next_value = 3 * num + 1
num_list.append(next_value)
return sequence(next_value)
print(sequence(num))
다른 사람 풀이:
cn = int(input())
n = 1
while cn != 1:
if cn % 2 == 0:
cn = int(cn // 2)
else:
cn = 3*cn+1
n += 1
print(n)
TAKEAWAY:
- 맞았다!
- 굳이 sequence 의 숫자들을 리스트에 다 저장할 필요 없이 1 나오는 그 순간에 순서를 출력하면 더 쉽게 풀 수 있었던 문제였다.
느낀점:
Author And Source
이 문제에 관하여(코딩테스트(백준 구현(IMPLEMENTATION) (14920번: 3n +1 수열))), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@oojjww1/코딩테스트백준-구현IMPLEMENTATION-14920번-3n-1-수열저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)