개발자의시작

문제링크 https://www.acmicpc.net/problem/1463 1463번: 1로 만들기 첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다. www.acmicpc.net 문제 풀이 가장 기본적인 DP 문제입니다. 조건 3가지 (1. X가 3으로 나누어 떨어지면, 3으로 나눈다. 2. X가 2로 나누어 떨어지면, 2로 나눈다. 3. 1을뺀다) 를 사용해서 1을 만들기 위한 가장 적은 연산 횟수를 찾는 문제입니다. bottom-up(반복)을 통해서 문제를 풀었습니다. DP의 기본인 점화식을 세우면 아래와 같이 나타낼 수 있습니다. 1. X가 3으로 나누어 떨어지면, 3으로 나눈다. -> D[N] = D[N/3]+1 2. X가 2로 나누어 떨어지면, 2로 나눈다. -> D[..