백준 1463, 2579
1) 백준 1463 : 1로 만들기 (https://www.acmicpc.net/problem/1463)
처음에는 소인수분해 해서 가능한 큰 수로 나누도록 하는 문제인줄 알고 있다가,
예제 생각하면서 반례를 찾아서 벙쪄있었음.
포인트가 가장 큰 수로 나눈다고 항상 가장 적은 횟수로 1을 만들 수 있는게 아니더라.
(뻘짓 오짐...)
1을 만들기 위해서 1은 0번, 2는 1번, 3은 1번의 회수로 1을 만들 수 있다.
그럼 4는?
4는 4 > 3 > 1 을가거나 4 > 2 > 1 을가거나 4 > 1.3333 > 1 을가거나 인데
마지막 1.33 은 말이 안되니까 재낀다.
그럼 저 성질들로 보아 2에서 1로가는 최소회수, 3에서 1로가는 최소회수가 다시 사용되는 것을 알 수 있다.
그럼 5는? 5 > 4 > ... > 1
(4에서 1을 가는 최단 회수는 이미 전에 구했기 때문에 저것만 보면 된다.)
6은? 6 > 5 > ... > 1 | 6 > 3 > ... > 1 | 6 > 2 > ... > 1
중에서 최단회수를 찾으면 된다.
n을 찾는 문제니까 n까지만 반복하면 될듯.
https://github.com/JangJuMan/2019-winter-PS/blob/master/DP/4_1463.cpp
2) 백준 2579 : 계단 오르기 (https://www.acmicpc.net/problem/2579)
아아 이거도 시간 많이 썼는데.. (실력부족...)
아무리 해도 점화식 생각이 안나서 쩔뚝이다가.. ㅠㅠ
포인트 캐치는 했는데 활용을 못한 케이스;;
일단 포인트는 n번째 DP값을 알기 위해서는 n-1번째를 경유할지, n-2번째를 경유할지 결정해야 한다는 것.(두개 다 경유할 수는 없음 _ 문제조건)
이거를 점화식으로 나타내면 문제가 풀림
1. n-1 번째를 경유하는 방법: (n-2번째를 경유 안하는 방법)
DP[n] = DP[n-3] + arr[n-1] + arr[n];
이러면 n-2를 경유하지 않고 n까지 오는 방법
- n-2번째를 경유하는 방법: (n-1번째를 경유 안하는 방법)
DP[n] = DP[n-2] + arr[n]
이러면 n-1번째 안지나고 n 까지 오겠지
둘이 합쳐서 최대값 계산하면 된다.
=> DP[n] = max(DP[n-2] + arr[n] , DP[n-3] + arr[n-1] + arr[n]);
https://github.com/JangJuMan/2019-winter-PS/blob/master/DP/4_2579.cpp
끗
