[BOJ] 백준 2635 수 이어가기 (Swift)

문제

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

2635번: 수 이어가기

풀이

문제에 제시된 규칙대로 구현하면 되는 문제

1. 첫 번째 수로 양의 정수가 주어진다.
   -> 이는 입력으로 주어지므로 입력을 받으면 됨
2. 두 번째 수는 양의 정수 중에서 하나를 선택한다.
   -> 1번에서 받은 수 보다는 작거나 같아야함 (이유는 4번을 보면 알 수 있음)
3. 세 번째부터 이후에 나오는 모든 수는 앞의 앞의 수에서 앞의 수를 빼서 만든다. 예를 들어, 세 번째 수는 첫 번째 수에서 두 번째 수를 뺀 것이고, 네 번째 수는 두 번째 수에서 세 번째 수를 뺀 것이다.
   -> 아하
4. 음의 정수가 만들어지면, 이 음의 정수를 버리고 더 이상 수를 만들지 않는다.
   -> 음의 정수가 만들어 지지 않을 때 까지 while문을 돌리자. 2번에서 입력보다 작거나 같아야 하는 이유는 입력보다 크다면 바로 음의 정수가 만들어지기 떄문

먼저, 입력을 받고 1부터 입력의 수까지 for문을 돌리면서 두번째 수를 1부터 입력받은 수 까지 넣어 array를 만들었음
해당 array의 크기를 저장할 프로퍼티와 가장 큰 array일 때 출력할 정답으로 쓰일 Int array를 프로퍼티로 선언해주었음

배열을 만들어보고, 비교하여 저장한 이후 1부터 입력의 수까지 돌려서 크기가 큰 array의 count와 array를 출력하여 풀이하였음

소스코드

	let n = Int(readLine()!)!
	var maxLength = 0
	var answerArray: [Int] = []
	for i in 1...n {
	var array = [n, i]
	var num = n - i
	while num >= 0 {
	let newNum = array.last! - num
	array.append(num)
	num = newNum
	}
	if maxLength < array.count {
	maxLength = array.count
	answerArray = array
	}
	}
	print(maxLength)
	print(answerArray.map { String($0) }.joined(separator: " "))

view raw 수 이어가기.swift hosted with ❤ by GitHub

후기

최대 입력의 크기가 30,000으로 작아서 완전탐색 알고리즘으로 풀 수 있을 것이라고 생각해서 풀이하였음
문제 규칙을 잘 따라가면 풀 수 있는 문제