백준) 2635 - 파이썬

https://www.acmicpc.net/problem/2635

(실버 5)

2635번: 수 이어가기

입력

100

출력

8
100 62 38 24 14 10 4 6

내 풀이

코드로는 작성하지 못했다.

2번째 수를 선정하는 방법이 핵심이라고 생각했고, 규칙성을 찾거나 모든 경우를 구하거나 둘 중 하나일 것이라고 생각했다.

몇가지 케이스를 직접 적어보고 규칙성은 구하기 힘들다는 것을 판단, 모든 경우를 구하되 n값의 절반 이하는 산정하지 말고 구해보자는 식으로 접근했다.

그러나 반복문, 계산식을 구현하지 못했고 그로 인해 코드로 작성하지 못했다.

풀이

import sys
input=sys.stdin.readline

n=int(input())
result=[]

for i in range(1,n+1):
    temp_list=[n,i]
    idx=1
    while True:
        next_num=temp_list[idx-1]-temp_list[idx]
        if next_num<0:
        	break
        temp_list.append(next_num)
        idx+=1
    if len(result)<len(temp_list):
    	result=temp_list
print(len(result))
for i in result:
	print(i, end=" ")

brute force 알고리즘을 이용하는 문제이다.

데이터 갯수를 통해서 짐작할 수 있어야 한다.

1부터 n까지의 수를 2번째 양수로 상정하고 모든 경우를 돌려보되, 음수가 나오는 순간 중지하며 길이에 따라 최종 결과를 계속해서 대입해서 최적의 수를 찾아내는 방식이다.

느낀 점

아무래도 사고 능력도 부족한 부분이 있지만 구현력이 특히 더 부족하다는 것을 깨달았다. 많은 문제를 풀어서 구현력을 길러야겠다.