BAEKJOON_1463) 1로 만들기

BAEKJOON 

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

# 다이나믹 프로그래밍 

1463) 1로 만들기 (19.03.19) (19.09.27)

* 전에 코드랑 생각한거는 같은거같다.
*



* 다이나믹 프로그래밍1 문제풀이1 에서 처음 나온 문제이다.
* 이전까지 나온 수를 arr에 넣어 사용했다.
* 1을 뺀 수 값에서 1을 더하기, 2를 나눈 수의 값에 1 더하기, 3으로 나눈 값에 1 더하기.
* 이렇게 세 가지를 비교해서 최소값을 그 칸에 넣는다.

* 채워야 하는 칸의 수는 num 까지 n개.
* 채우는데 1을 빼고, 2와 3을 나눈 값, 세 종류를 비교하는 것이기 때문에 1.
* 따라서 시간복잡도는 O(N) 이다.