BaekJoon
[BaekJoon] 12852번 1로 만들기 2 (Kotlin) 문제 풀이 [Silver 1]
문제 https://www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net 어떻게 풀 것인가? 처음에는 단순 그리디 방식으로 접근했다. 하지만 그렇게 했다가는 시간초과가 발생한다. 문제를 보자. 시간 제한은 0.5초이다. 자 이렇게 시간제한이 빡빡하다는 것은 DP로 접근해야함이다. 그렇다면 DP 배열에 무엇을 넣어야할까? 점화식 수식을 넣어야한다. 그렇다면 점화식은 무엇을 넣어야 하는가? 이 문제에서 원하는 것은 가장 적게 연산하여 1을 도출하는 것이다. 그렇다. 점화식을 생각해본다면 dp[i] = min(dp[i / 3], dp[i / 2], dp[i - 1]) (i ..
