나보단 잘하자

문제 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 풀이 다이나믹 프로그래밍. 한국어로 동적 계획법을 이용해 풀어야 하는 문제이다. 동적 계획법은 상향식과 하향식이 있는데, 처음 두 수를 알기 때문에 상향식으로 문제를 풀었다. 상향식은 제일 작은 인덱스의 수 부터 목표하는 값으로 향하는 것이고, 하향식은 맨 위의 값에서 재귀로 제일 작은 인덱스를 향하는 것이다. 이 동적 계획법이 최솟값을 구하는 면에서 그리디 알고리즘이랑 뭐가 다른가 싶었는데, 그리디 알고리즘은 내가 생각한 처음 최적의 방법이 끝까지 반례 없이 적용이 되는 경우에 이용하고, 동적 계획법은 가능성을 모두 두고 그 안에 최솟값을 찾을 수 있기 때문에 뭔가 그..