[백준, BOJ 1463] 1로 만들기 (java)

출처-https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

---

728x90

 

내가 푼 방식

:1에서 n에 접근하기 위한 최단거리를 구해준다.
 dp[1]~dp[n]인 배열을 생성한다.
 i가 1부터 시작해서 n까지 i (+1 or *2 or *3) 해서
 최단 루트로 n에 도달할 수 있는 경우의 수를 찾는다.

 

DP 관련 문제 중 첫번째로 풀었던 문제.

이 문제를 풀 때까지만 해도 DP 개념이 이해가 잘 안 됐었다.

그래서 보기 편하게 표로 과정을 나타내 봤다.

이렇게 한번 그려보고 나니까 머릿속이 정리가 됐다.

다음 DP 풀 때부터는 이걸 바탕으로 머리로 그려보며 풀어서 좀 더 수월했다.

 

import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub

		Scanner scan=new Scanner(System.in);
		
		int n=scan.nextInt();
		int dp[]=new int[n+1]; //index 1~n까지 사용 (index 0은 무시)
		
		for (int i=1;i<=n;i++) { //i가 1부터 n까지 1씩 증가하며 반복
			if (i+1<=n) { // +1을 하는 경우 (n을 넘어가면 안된다.)
				if (dp[i+1]==0) //i+1한 곳에 아직 한 번도 접근하지 않았다면
					dp[i+1]=dp[i]+1; //dp[i]에서 +1
				else //이미 이곳에 접근한 적이 있다면
					if (dp[i+1]>=dp[i]+1) //더 최단거리로 접근했을 때의 수를 저장
						dp[i+1]=dp[i]+1;
			}
			if (i*2<=n) { //*2를 하는 경우 (n을 넘어가면 안된다.)
				if (dp[i*2]==0)
					dp[i*2]=dp[i]+1;
				else
					if (dp[i*2]>=dp[i]+1)
						dp[i*2]=dp[i]+1;
			}
			if (i*3<=n) { //*3을 하는 경우 (n을 넘어가면 안된다.)
				if (dp[i*3]==0)
					dp[i*3]=dp[i]+1;
				else
					if (dp[i*3]>=dp[i]+1)
						dp[i*3]=dp[i]+1;
			}
		}
		System.out.println(dp[n]);
	}

}