<baekjoon> 수 이어가기

풀이

<문제>

1. 첫 번째 수로 양의 정수가 주어진다.

2. 두 번째 수는 양의 정수 중에서 하나를 선택한다.

3. 세 번째부터 이후에 나오는 모든 수는 앞의 앞의 수에서 앞의 수를 빼서 만든다. 예를 들어, 세 번째 수는 첫 번째 수에서 두 번째 수를 뺀 것이고, 네 번째 수는 두 번째 수에서 세 번째 수를 뺀 것이다.

4. 음의 정수가 만들어지면, 이 음의 정수를 버리고 더 이상 수를 만들지 않는다.

2번 조건을 잘 정하면 좀 더 탐색범위를 줄일 수 있다. 최대한 길게하기위해서는  2번째 수가 N보다 작으면작을수록 불리하다. 예를 들어 첫번째 수가 100, 두번째 수가 0 이면 3번째에 끝나버리게된다. 

 

그래서 범위를 N/2부터 탐색을 시작하도록 했다. 그러면 최소한의 길이도 3부터 시작하기 때문이다. while문을 통해 뺄셈에  사용되는 수를 차례대로 바꿔가면서 진행하고 그 길이의 최대값을 계속 갱신하면 된다.

 

코드