[백준] 단계별로 풀어보기(단계:15,동적계획법1,JAVA)1463번, 1로 만들기

문제 링크

1463번: 1로 만들기

 

www.acmicpc.net

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

동적계획법이란 위 문제와 같이 동일한 연산을 계속 반복하여 비효율적으로 코드가 실행되어 그것을 향상시키기 위하여반복되는 연산의 결과를 따로 저장하여 적재적소에 코드가 더 효율적으로 만드는 방법입니다.

 

예제 2에 최소값일 때를 표현하면

10 ▶ 9 ▶ 3 ▶ 1 = 3번

(10-1)/3/3=1으로 최소 3번의 연산이라는 것을 알 수 있다. 

 

규칙은 문제에서 모두 알려주고 있습니다.

시작위치는 아무것도 없는 것으로 0으로 초기화 한 뒤 1칸으로 이동했을 때와 2칸으로 이동했을 때에 경우의 수를 구하여 최대값을 구하도록 하였습니다.

입력값에서 1이 될 수 있도록 입력값 이하의 경우의 수를 다 확인해야 하므로 [입력값 +1]으로 메모이제이션을 구성하였습니다.

연산 3가지 사용할 수 있는 환경은 정해져 있습니다.

 

1,2,3번 모두 사용할 수 있는 환경 : 2의 배수이면서 3의 배수인 수= 6의 배수

1,3번 모두 사용할 수 있는 환경 : 2의 배수이면서 3의 배수는 아닌 수

2,3번 모두 사용할 수 있는 환경 : 3의 배수이면서 2의 배수는 아닌 수

3번만 사용할 수 있는 환경 : 2의 배수도 아니고 3의 배수도 아닌 수

 

환경에 따라서 IF문을 사용하여 나누었고 그에 따른 재귀를 진행하여 Math.min을 사용하여 최소 연산 횟수를 구하였습니다.

 

• 함수 값 저장할 메모이제이션 배열 check를 만들었습니다.
• 정수 X를 저장하는 num을 만들었습니다.
• BufferedReader를 사용하여 입력 값을 받았습니다.
• 1을 만드는데 최소한의 연산 횟수를 함수 makeOne을 만들었습니다.

• check가 0이 아니면 메모이제이션에 저장된 값이 있기에 그 값을 가져온다.
• 0인 경우 재귀를 반복하여 결과값을 메모이제이션에 저장한 뒤 반환한다.
• 위에 알고리즘 설명을 토대로 재귀하도록 makeOne함수를 작성하였습니다.

결과 코드

import java.io.*;
public class Main{
	static int[] check;	//메모이제이션 배열
	static int num;		//입력 값
	public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //BufferedReader를 통해 입력 값 받기
        //-------------입력값 저장 및 배열 초기화----------
    	num = Integer.parseInt(br.readLine());
    	check = new int[num+1];
    	System.out.println(makeOne(num));	//결과 출력
    	br.close();
	}
    //----------최소 횟수 구하는 1 만들기 함수------------
	public static int makeOne(int current) {
		if(current==1)	//1을 만들었을 때
			return 0;
	
		if(check[current]!=0)	//메모이제이션에 값이 존재할 때
			return check[current];
		//----------------1을 만들기 위한 재귀-----------------
		if(current%6==0)	//2와 3의 공배수 6으로 나눠질 때
			check[current] = Math.min(makeOne(current/2), 
            Math.min(makeOne(current/3), makeOne(current-1))) + 1;
		else if(current%2==0)	//2의 배수일 때
			check[current] = Math.min(makeOne(current/2), makeOne(current-1)) + 1;
		else if(current%3==0)	//3의 배수일 때
			check[current] = Math.min(makeOne(current/3), makeOne(current-1)) + 1;
		else		//2와 3의 배수가 아닌 수일 경우
			check[current] = makeOne(current-1) + 1;

		return check[current];	결과 반환
		}
	}