[알고리즘][Java] 백준(BOJ) 1463 1로 만들기_자바

 

DP

1463 1로 만들기    https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

 

문제 풀기 전 공부할 것 : 다이나믹 프로그래밍

 

 

 

 

 

 

 

풀이

<내용>

• n을 Scanner를 이용하여 입력받는다.
• 배열의 크기가 n+1인(인덱스가 0 ~ n 까지) 배열을 선언한다.
• 1 - n 까지 반복문을 돌면서 i가 1, 2, 3 일 때는 해당 결괏값을 배열에 넣어주고
• 이외의 경우는 연산에 따라 3으로 나눠질 때, 2로 나눠질 때, 1을 뺄 때 각각의 경우에 해당하는 연산 횟수에 1을 더한 값 중 최솟값을 구하여 해당 배열에 값을 넣는다.
• 배열의 각 값은 해당 인덱스를 1로 만드는데 필요한 연산 횟수가 된다.

 

 

<코드>

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		sc.close();
		
		int[] nums = new int[n+1];
		for(int i=1; i<=n; i++) {
			if (i == 1) {
				nums[i] = 0;
			}else if (i == 2 || i == 3) {
				nums[i] = 1;
			}else {
				int m = i-1;
				if (i % 3 == 0) {
					m = Math.min(m, nums[i/3]+1);
				}
				if (i % 2 == 0) {
					m = Math.min(m, nums[i/2]+1);
				}
				m = Math.min(m, nums[i-1]+1);
				nums[i] = m;
			}
		}
		System.out.println(nums[n]);
		

	}

}

 

 

 

 

 

 

 

 

같은 문제 파이썬으로 푸는 방법

2020.03.18 - [Algorithm/백준 알고리즘_Python] - [알고리즘][Python] 백준(BOJ) 1463 1로 만들기_파이썬

[알고리즘][Python] 백준(BOJ) 1463 1로 만들기_파이썬