목록백준 1로 만들기 (1)
공부하는 스누피
[Python] 1로 만들기 - DP
https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 생각과정 - n이 1일 경우 0, 2일 경우 1, 3일 경우 1번의 연산으로 1을 만들 수 있다. - 일차원 배열을 만들어 인덱스값에 대한 최소 연산 횟수를 저장한다. - 4부터 n까지 순회하면서 최솟값을 구한다. (Bottom-Up 방식) - 먼저 3이나 2로 나누어 떨어지는지 확인한다. 나누어 떨어진다면, n/3 또는 n/2의 값에서 1을 더한 값을 배열에 저장한다. 앞에서 n/3의 최솟값을 구해 놓았으니 1을 더하기만 하면 된다. - 1을 빼는 연산은 2나 3으로 나누어 떨어지지 않을 때 수행하거나, 앞의..
Algorithms/코딩테스트 문제풀이
2020. 8. 30. 00:46