문제:

다음과 같은 규칙에 따라 수들을 만들려고 한다.

  1. 첫 번째 수로 양의 정수가 주어진다.
  2. 두 번째 수는 양의 정수 중에서 하나를 선택한다.
  3. 세 번째부터 이후에 나오는 모든 수는 앞의 앞의 수에서 앞의 수를 빼서 만든다. 예를 들어, 세 번째 수는 첫 번째 수에서 두 번째 수를 뺀 것이고, 네 번째 수는 두 번째 수에서 세 번째 수를 뺀 것이다.
  4. 음의 정수가 만들어지면, 이 음의 정수를 버리고 더 이상 수를 만들지 않는다.

첫 번째 수로 100이 주어질 때, 두 번째 수로 60을 선택하여 위의 규칙으로 수들을 만들면 7개의 수들 100, 60, 40, 20, 20 , 0, 20이 만들어진다. 그리고 두 번째 수로 62를 선택하여 위의 규칙으로 수들을 만들면 8개의 수들 100, 62, 38, 24, 14, 10, 4, 6이 만들어진다. 위의 예에서 알 수 있듯이, 첫 번째 수가 같더라도 두 번째 수에 따라서 만들어지는 수들의 개수가 다를 수 있다.

입력으로 첫 번째 수가 주어질 때, 이 수에서 시작하여 위의 규칙으로 만들어지는 최대 개수의 수들을 구하는 프로그램을 작성하시오. 최대 개수의 수들이 여러 개일 때, 그중 하나의 수들만 출력하면 된다.

입력:

첫 번째 수가 주어진다. 이 수는 30,000 보다 같거나 작은 양의 정수이다.

출력:

첫 번째 줄에는 입력된 첫 번째 수로 시작하여 위의 규칙에 따라 만들 수 있는 수들의 최대 개수를 출력한다.

둘째 줄에 그 최대 개수의 수들을 차례대로 출력한다. 이들 수 사이에는 빈칸을 하나씩 둔다.

풀이방법:

 주어질 수 있는 첫 번째 수가 크지 않기 때문에 브루트 포스 방법으로 모든 케이스를 고려하여 해결하면 된다. 1부터 N까지 반복하여 두 번째 수를 결정하고 3번, 4번의 과정을 진행한다. 4번으로 인해 더 이상 수를 만들지 않을 때마다 생성한 수들의 갯수를 비교하여 이전 케이스보다 큰 경우에만 기록하도록 한다.

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
= int(input())
answer = []
# N=1 일 때
for i in range(1,N+1):
    first = N
    second = i
    tmp = [N, i]
    while True:
        next_ = first - second
        if next_ >= 0:
            tmp.append(next_)
            first, second = second, next_
        else:
            if len(tmp) > len(answer):
                answer = tmp
            break
print(len(answer))
print(*answer)
cs

문제링크:

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

 

2635번: 수 이어가기

첫 번째 수가 주어진다. 이 수는 30,000 보다 같거나 작은 양의 정수이다.

www.acmicpc.net

 

'Algorithm > Python' 카테고리의 다른 글

[BOJ]6976. 절사평균  (0) 2022.04.26
[BOJ] 2303. 숫자 게임  (0) 2022.04.21
[BOJ]2596. 비밀편지  (0) 2022.04.14
[BOJ]2615. 오목  (0) 2022.04.12
[BOJ]2628. 종이자르기  (0) 2022.04.07

+ Recent posts