Notice
Recent Posts
Recent Comments
Link
«   2025/06   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30
Tags
more
Archives
Today
Total
관리 메뉴

빠똥빠똥

1463번 1로 만들기(DP) - ☆ 본문

백준

1463번 1로 만들기(DP) - ☆

조주똥 2020. 6. 17. 15:30

#문제링크 : https://www.acmicpc.net/problem/1463

<전략>

1. 수 N에서 한번 연산하고 다음수로 넘어간 수를 (1, N)수라 하면, M번 연산하고 넘어간 수는 (M, N)이다.

2. (M-1, N)의 연산횟수의 최소값은 (M, N)의 최소값 + 1 이다. M-1 -> M 연산 한번을 더 했기 때문.

3. N의 최소 연산 횟수를 num[N]에 저장하고, 이후에 N보다 큰 값이 나올때, 저장된 값을 사용한다.

Code