BAEKJOON_9095) 1, 2, 3 더하기

BAEKJOON 

# 알고리즘 기초 # 2019 SW역량테스트준비-기초

# 다이나믹 프로그래밍 # 브루트 포스

9095) 1, 2, 3 더하기 (19.03.19) (19.09.03) (19.09.11) (19.09.27)

* 마지막에 1, 2, 3 중에 어떤 값을 더했냐를 기준으로 삼았다.
* 따라서 각각 n-1, n-2, n-3 의 합이 그 앞부분의 값이 되었고, 미리 저장해둔 값을 사용할 수 있었다.
* 이때, 모든 경우를 구하라고 했으니, 각 경우의 수를 모두 더한값을 출력했다.

* 이 문제 역시
* 채워야 하는 칸의 수는 n 개, 수식은 3개를 더하기 이기 때문에,
* 시간복잡도는 O(N) 으로 볼 수 있다.



* 브루트포스 강의에서 N중for문의 예제로, 10중 for문을 사용해서 문제를 풀었다.
* 3가지 수를 쓸 수 있고, 최대 10개의 수를 더할 수 있으므로, 경우의 수는 3^10.
* 따라서 10만보다 작기 때문에 10중 for문이 가능하다.
* 이 풀이의 시간복잡도는 3^n 으로,
* 재귀함수를 이용해도 같은 시간복잡도라고 한다.

!!!!! 2중 for문 이상에서는 재귀함수를 사용하는 것이 좋음. 실수 방지 등 !!!!!



* 재귀 함수 사용하기!!
* 와... n중 for문 코드 보고 보니까 길이 차이 무엇....
* 재귀 함수는 매번 잘 보고 해야겠다.
* cnt를 매개변수로 썼는데 강의에서처럼 필요 없는 거였다. go 함수에 처음 return 값을 잘 보기.
* 재귀 함수 연습 하기이



* 최대 10까지밖에 안되니까 그냥 배열 써서 푸는게 제일 먼저 떠올랐나보다.
* 다른 방법으로도 풀었었구ㅏㄴ.....ㅎㅎ