[알고리즘][다이나믹(동적 계획법)] 1로 만들기 (백준)

동적 계획법 (다이나믹) 알고리즘 문제 : 1로 만들기 (백준)

동적 계획법에도 어느정도 익숙해져 가는 것 같다.

매번 강조하는 내용이지만 그 전에 찾아 놓은 답을 활용할 것!

그리고 그 전에 찾아 놓은 답을 저장할 DP배열을 꼭 만들 것!

이 둘만 기억한다면 동적 계획법 알고리즘은 쉽게 풀 수 있을 것이다.

늘 그렇듯 이번 문제에도 함정이 있었는데.. 나만 그렇게 생각하는 것일 수 있지만

2로 나누어 떨어지는 숫자라도 -1을 해준 뒤 계산할 경우 더 작은 숫자가 나올 수 있다는 것이다.

(3으로 나누어 떨어지는 숫자는 무조건 가장 작은 수이기 때문에 -1한 값과 비교할 필요가 없다.)

10을 예로 들어보자.

2로 나눈다면 5가될 것이고 DP[5]에는 3이 저장되어 있을 것이다.

따라서 총 연산 횟수는 4번.

하지만 -1을 해주고 시작한다면 9가되고 DP[9]에는 2가 저장되어 있을 것이다.

따라서 총 연산 횟수는 3번.

이 부분을 생각하는 데 시간이 좀 걸렸으나, 전체적으로 쉬운 동적 계획법(다이나믹) 문제이다.

01. 변수 선언 그리고 초기화

02. 동적 계획법(다이나믹) 알고리즘을 수행할 함수

03. 메인 함수

동적 계획법(다이나믹) 알고리즘의 기본 문제를 풀어 보았다.

요즘 동적 계획법 문제만 풀어보는 것 같은데 다음 포스팅에서는 DFS, BFS문제를 풀어보도록 하겠다.