티스토리 뷰
반응형
문제 링크
문제
위 그림과 같이 삼각형이 나선 모양으로 놓여져 있다. 첫 삼각형은 정삼각형으로 변의 길이는 1이다. 그 다음에는 다음과 같은 과정으로 정삼각형을 계속 추가한다. 나선에서 가장 긴 변의 길이를 k라 했을 때, 그 변에 길이가 k인 정삼각형을 추가한다.
파도반 수열 P(N)은 나선에 있는 정삼각형의 변의 길이이다. P(1)부터 P(10)까지 첫 10개 숫자는 1, 1, 1, 2, 2, 3, 4, 5, 7, 9이다.
N이 주어졌을 때, P(N)을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. (1 ≤ N ≤ 100)
출력
각 테스트 케이스마다 P(N)을 출력한다.
문제 풀이
이런 문제들은 보통 어떤 규칙이 존재하기 때문에 규칙을 찾기 위해 그림을 그려보며 직접 답을 구해봤습니다.
규칙이 보이시나요??
6번째 수 부터 다음에 해당하는 답이 수열을 처음부터 차례대로 더해지는 형태입니다.
즉 6번째 수 = 5번째 수 + 1번째 수 인 것이죠!
이 규칙에 의하면 n번째 수 = n-1번째 수 + n-4번째 수 가 됩니다.
이 점화식을 가지고 문제를 풀어버리면 됩니다!
소스 코드
func solution() {
let t = Int(readLine()!)!
var testCase: [Int] = []
for _ in 0..<t {
testCase.append(Int(readLine()!)!)
}
var result = [1,1,1,2,2]
for i in 0..<95 {
result.append(result[i] + result[i+4])
}
for num in testCase {
print(result[num - 1])
}
}
solution()
반응형
'Algorithm > BaekJoon' 카테고리의 다른 글
[백준] 1463번 1로 만들기 [Swift] (3) | 2020.10.08 |
---|---|
[백준] 1967번 트리의 지름 [Swift] (0) | 2020.10.07 |
[백준] 1003번 피보나치 함수 [Swift] (0) | 2020.10.06 |
[백준] 1904번 01타일 [Swift] (0) | 2020.10.06 |
[백준] 2887번 행성 터널 [Swift] (0) | 2020.09.27 |
댓글
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- Apple
- document
- System
- Swift
- 코딩테스트
- IOS
- Combine
- dfs
- Xcode
- 프로그래밍
- OS
- operating
- 문법
- OSTEP
- DP
- 알고리즘
- 아이폰
- 스위프트
- 테이블뷰
- mac
- operator
- design
- 코테
- 앱개발
- 동시성
- BFS
- 백준
- 자료구조
- Publisher
- pattern
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | 5 | 6 | 7 |
8 | 9 | 10 | 11 | 12 | 13 | 14 |
15 | 16 | 17 | 18 | 19 | 20 | 21 |
22 | 23 | 24 | 25 | 26 | 27 | 28 |
29 | 30 | 31 |
글 보관함