[BOJ]1463:1로 만들기

1. DP

1부터 시작해서 N까지 배열을 채워나갔다.

이전 배열의 값(즉 1만큼 작은 값) + 1로 현재 i번째 값을 채우고 2또는 3으로 나누어 덜어지는 경우 i/2 또는 i/3 인덱스의 값과 비교해서 더 작은 값으로 업데이트했다.

 

나머지 두개의 경우는 숫자 N부터 시작했다.

 

2. BFS

visited배열과 큐를 사용해서 3으로 나누었을때, 2로 나누었을때, 1을 뺐을때 0보다 크고 가능한 경우를 완전탐색하는 방식으로 해결

 

3. DFS

큐대신 재귀를 사용하였다.

재귀함수의 매개변수로 깊이를 줘서 가지치기를 해야 시간초과가 나지 않는다.

 

 

위에서부터 dfs, bfs, dp로 푼 결과

dp로 풀었을때가 제일 빠르게 나올줄 알았는데 bfs로 푼게 더 빨리 통과되었다.