백준 12852 검색 결과
1 개의 검색 결과가 있습니다.
카테고리 없음

백준 12852번 : 1로 만들기 2 풀이 (Java)

www.acmicpc.net/problem/12852 12852번: 1로 만들기 2 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 자연수 N이 주어진다. www.acmicpc.net Solution 1. 이 문제는 다이나믹 프로그래밍, DP 로 풀어야 하는 문제이다. 최대 인풋이 10의 6승이고, 그렇기에 최대 O(n) 으로 풀어야 할 것이다. 2. N 을 1로 만드는 것이라서 top-down 방식으로 풀까 하다가 웬지 어려울 것 같아서 bottom-up 으로 풀었는데, 출력을 위해서 반복문을 한번 더 돌려야했다. 푼 뒤에 top-down 을 시도해봤는데 이 편이 더 어려운 것 같다.. 3. N+1 크기의 dp 배열을 만들고, dp[i] 에는 i 를 1로 만드는 데 필요한 연산 횟수를 담는다. ..

2021. 3. 11. 18:48