Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 백준
- Python
- BubbleSort
- KAKAO
- Singleton Pattern
- Programmers
- Observer Pattern
- kubernetes
- Dynamic Programming
- docker
- GCP
- java
- Backjoon
- 파이썬
- GKE
- k8s
- mobaXTerm
- Top-down
- github
- 알고리즘
- 그리디
- go
- 피보나치
- golang
- easy
- Codility
- LeetCode
- Kotlin
- cpu scheduling
Archives
- Today
- Total
To Be Developer
[BackJoon] 9095번 : 1, 2, 3 더하기 (GoLang) 본문
https://www.acmicpc.net/problem/9095
[GoLang 풀이]
package main
import (
"fmt"
)
// 문제의 조건에서 정수가 최대 11 까지라고 제시
// 0 ~ 11 까지 1, 2, 3 으로 표시할 수 있는 경우를 저장하는 배열변수
var array [12]int
func main() {
var len int
fmt.Scanln(&len)
// 표현 할 수 있는 숫자가 1, 2, 3 뿐 이므로
// 점화식 dp[n] = dp[n-1] + dp[n-2] + dp[n-3]
/* 0~3 까지 표현할 수 있는 방법 수*/
array[0] = 0
array[1] = 1
array[2] = 2
array[3] = 4
// 콘솔 입력을 받기 위한 배열
var num []int = make([]int, len)
for i := 0; i < len; i++ {
fmt.Scanln(&num[i])
}
// num[0:len] 까지의 표현할 수 있는 경우를 출력한다.
for i := 0; i < len; i++ {
fmt.Println(sumOneTwoThree(num[i]))
}
}
// Top-Down 방식
func sumOneTwoThree(num int) int {
// 만약 array[num] 에 데이터가 존재한다면 바로 리턴
if array[num] != 0 {
return array[num]
}
// num 이 3보다 작으면 미리 등록해놓은 array에서 바로 리턴
if num <= 3 {
return array[num]
} else {
// 그렇지 않다면 점화식을 사용한 top-down 방식으로 구함
array[num] = sumOneTwoThree(num-1) + sumOneTwoThree(num-2) + sumOneTwoThree(num-3)
// 계산한 array[num] return
return array[num]
}
}
'알고리즘 > BackJoon' 카테고리의 다른 글
[BackJoon : 백준] 1037번 : 약수 (Python) (0) | 2019.04.16 |
---|---|
[BackJoon : 백준] 2579번 : 계단오르기 (Python) (0) | 2019.04.14 |
[BackJoon] 1463번 : 1로 만들기 (GoLang) (0) | 2019.04.12 |
[BackJoon] 2748. 피보나치 수 2 (0) | 2019.03.09 |
[BackJoon] 2577: 숫자의 개수 (0) | 2019.03.03 |