BOJ 1463 1로만들기

 

www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

 

문제 분석

- 저장한 배열의 값과 새로 계산한 값(3으로 나누었을 때의 값 & 2로 나누었을 때 값)을 비교하여 계속 최소값으로 업데이트한다. 

- 배열의 범위를 N의 최대값으로 잡으니 런타임에러가 난다. 주의해서 코딩하자!

 

 

문제 풀이

 

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class Main {

	private static long[] map;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		map = new long[N+1];

		map[0] = map[1] = 0;
		for (int i = 2; i <= N; i++) { 
			map[i] = map[i - 1] + 1;
			if (i % 2 == 0) //2로 나눠지는 경우
				map[i] = Math.min(map[i], map[i / 2] + 1);
			if (i % 3 == 0) //3으로 나눠지는 경우
				map[i] = Math.min(map[i], map[i / 3] + 1);
		}

		System.out.println(map[N]);

	}// main

}// class-end