글 읽기 - 이문제를 풀기위한 수학적 지식은 무엇인가요?

연산을 최소로 하기 위함이라면

첫번째로 큰수로 나누는게 연산횟수가 적어질거 같고

그다음 큰수로 나누고

그게 안된다면 빼는것밖에 없으니 빼고

그다음 위의 프로시저를 반복 으로 생각하는데

어떠신가요?

반례가 생깁니다.

10 -> 5 -> 4 -> 2-> 1

10 -> 9 -> 3 -> 1

이 문제는 다이나믹 프로그래밍으로 풀 수 있습니다.

지금 가지고 있는 숫자에서 모든 경우의 수를 계산하고 그 중 가장 연산 횟수가 적은 경우를 출력해야 합니다.

그런데 매번 다른 숫자로 넘어갈때마다 계산을 하면 시간이 너무 오래 걸려요.

그래서 한번 계산한 숫자를 저장하고 다음번에 그 숫자를 계산해야할때 미리 저장한 수를 받아오는거죠. 그게 다이나믹 프로그래밍이에요.

http://janghw.tistory.com/entr... 여기 들어가 보시면 나름 잘 설명하는 것 같아요.

그럼 화이팅!

댓글을 작성하려면 로그인해야 합니다.

Baekjoon Online Judge