반응형
상향식
-
백준 1463 - 1로 만들기백준 algorithm 2020. 4. 6. 00:34
=> DP 문제이다. => 내가 구해야 하는 것을 우선적으로 문자로 써본다. 내가 구하고자 하는 것 : N 을 1로 만드는데 필요한 최소 연산 횟수 가능한 경우의 수 : 1. i 가 3으로 나누어 떨어질 때 - arr[ i/3 ] + 1 2. i 가 2로 나누어 떨어질 때 - arr[ i/2 ] + 1 3. i 에서 1을 뺄 때 - arr[ i - 1 ] + 1 => 위의 경우 세 가지가 있는 것을 알 수 있다. => DP에는 Top-down 방식과 Bottom-up 방식이 있다. => 본인은 Bottom-up 방식을 선호한다. (Top-down은 재귀를 쓰는데, 재귀를 쓰다 보면 헷갈린다....) *** 둘 중 어느것이 좋다는 것은 없다. 본인이 원하는 방식으로 사용하면 된다. #include #inc..