<BOJ>1463번: 1로 만들기
문제
접근
- 문제에 제시된 3가지 연산 조건을 토대로 점화식을 짜면 된다.
dp[i] = dp[i-1] + 1
dp[i] = dp[i/2] + 1 (i % 2 == 0)
dp[i] = dp[i/3] + 1 (i % 3 == 0) - 위 점화식을 토대로 연산 횟수의 최솟값을 도출해야 한다.
내 코드
import java.io.*;
public class Main {
static int[] dp = new int[1000005];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int n = Integer.parseInt(br.readLine());
dp[1] = 0;
for (int i = 2; i <= n; i++) {
dp[i] = dp[i-1] + 1;
if (i % 2 == 0) dp[i] = Math.min(dp[i/2]+1, dp[i]);
if (i % 3 == 0) dp[i] = Math.min(dp[i/3]+1, dp[i]);
}
System.out.println(dp[n]);
}
}
Author And Source
이 문제에 관하여(<BOJ>1463번: 1로 만들기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@songs4805/BOJ1463번-1로-만들기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)