백준 1463: 1로 만들기(Swift)

전형적인 다이나믹 프로그래밍 문제이다.

이 문제를 처음 접했던 시절에는 그리디 알고리즘으로 접근했다가 풀지 못했던 기억이 있다.

28 -> 27 -> 9 -> 3 -> 1과 같이 언제 어디서 최단 경로가 생길지 모른다. 우리는 물론 컴퓨터도..

따라서 dp로 bottom-up 방식으로 1번 index부터 n번 index까지 최소 횟수를 구해나가면 된다.

 

먼저 dp = Array(repeating: 0, count: n+1)로 0번 ~ n번 인덱스까지 모두 0으로 초기화해주었다.

 

1번 index, 즉 숫자 1은 1까지 도달하려면 

-3으로 나누기

-2로 나누기

-1을 빼기

이 세가지 연산을 총 0번 수행하면 되므로 dp[1] = 0,

같은 이유로 dp[2] = 1, dp[3] = 1

그 위로의 숫자들은 컴퓨터가 알아서 반복문 돌면서 dp배열에 저장해나가라!

 

중요한 것은 저와 같이 dp를 구현하는 경우, 반복문을 돌기 전, 반복문에 포함되지 않는 인덱스, 즉 이 문제에서는 1,2,3의 경우에 대하여

반복문보다 앞에서 print()해주고 프로그램을 종료해야 out of index오류가 뜨지 않습니다!