[백준] 1463. 1로 만들기 (자바 JAVA)

[ 문제 ]  [백준] 1463. 1로 만들기 (자바 JAVA)

 

문제 링크 : https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

---

# 접근 방법 및 풀이 

 

• DP 기초 문제다.
• DP테이블을 만들어 값을 어떻게 저장하고 저장한 값을 어떻게 활용할지 생각해본다.
• 접근방식이 바로 생각 안날때는 N이 가장 작은값일때부터 구해보면 된다.

• N = 1	2	3	4	5	6	7	8	9	10
  0	1	1

• N이 1일때는 연산할 필요가 없으므로 0번, 2일때는 2로 나누어지는 연산을 통해 1이되므로 1번, 3도 마찬가지로 1번이다.
• 4부터 값을 천천히 살펴보면 주어진 연산 세가지로 떠올려보면 된다.
• 4에서 1을 뺀다면 3이되고 dp[3]일때 연산이 1번이므로 거기서 +1 해주면 4가된다. -> 총 연산 2번
• 4가 2로 나누어 떨어지므로 2로 나누면 dp[2]가되고 거기서 +1해주면 4가 된다. -> 총 연산 2번
• 4에서 3은 나누어 떨어지지않으므로 3으로 나눈 연산은 할 수 없다.
• 여기서 각각의 연산을 통해 구한 회수의 최솟값이 답이된다. 4는 2번이 된다.

• N = 1	2	3	4	5	6	7	8	9	10
  0	1	1	2	3	2	3	3	2	3

• 자세한건 코드참조

 

# 주의할 점 

 

• 없음

 

JAVA 코드

package Silver;

import java.util.Scanner;

public class bj1463_1로만들기 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int dp[] = new int[1000001];
		dp[2] = 1;
		dp[3] = 1;
		for(int i = 4; i <= N; i++) {
			int cnt = dp[i-1] + 1;
			if(i % 3 == 0)
				cnt = Math.min(cnt, dp[i/3]+1);
			if(i % 2 ==  0)
				cnt = Math.min(cnt, dp[i/2]+1);
			dp[i] = cnt;
				
		}
		System.out.println(dp[N]);
	}
}

 

 

 

REVIEW

DP문제 다양하게 풀어서 사고력을 길러봐야지!