[백준] 단계별로 풀어보기(단계:27, 동적 계획법과 최단거리 역추적,JAVA)12852번, 1로 만들기 2

문제 링크

12852번: 1로 만들기 2

---

주의사항

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

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

---

문제 설명

---

접근 방법

동적 계획법

모든 연산을 수행하면 똑같은 연산을 중복되게 수행하게 되는데 다이나믹 프로그램은 연산한 내용을 따로 저장하여 효율적으로 작성한 프로그램입니다.

 

더 자세한 내용은 링크를 남겨두겠습니다.

동적 계획법 - 위키백과, 우리 모두의 백과사전

 

 

이 문제에 핵심은

1. 문제에서 설명한 3가지 규칙을 적용하여 최소의 연산 횟수를 출력해야 합니다.

2. 정답이 여러 개인 경우 아무거나 출력하면 됩니다.

 

배열

 

count[i] : i의 값을 만드는 데 사용하는 최소 연산 횟수 

 

process[i] : i의 값을 만드는데 바로 전 연산값

 

저는 입력값에서 N/2까지 수에서 나올 수 있는 경우의 수 배열과 N/2부터 N까지 수에서 나올 수 있는 경우의 수의 배열을 2가지 만들어 두 배열을 조합하여 모든 경우의 수를 구하였습니다.

 

예제입력 2에 count와 process의 값을 표로 살펴보면

Count

1	2	3	4	5	6	7	8	9	10
0	1	1	2	3	2	3	3	3	4

Process

1	2	3	4	5	6	7	8	9	10
0	1	1	2	4	2	6	4	3	5

 

count의 값을 구할 때에는 문제에서 설명한 내용을 그대로 사용하시면 됩니다.

1. i가 3으로 나누어 떨어지면 count[i/3]의 값 + 1

2. i가 2으로 나누어 떨어지면 count[i/2]의 값 + 1

3. i-1이 0보다 크면 count[i-1] + 1

 

위 3가지 조건이 중복되면 중복되는 값들 중 최소값에서 + 1을 해주면 됩니다.

 

Count[8]을 구할 때

8은 규칙 2와 규칙 3을 만족합니다.

규칙 2 : count[8/2] + 1 = count[4] + 1 = 2 + 1 = 3

규칙 3 : count[8-1] + 1 = count[7] + 1 = 3 + 1 = 4

규칙 2를 적용했을 때가 더 작기 때문에 3이 저장됩니다.

 

process의 값을 구할 떄에는 count값을 구할 때에 규칙에 최소값에 해당하는 i의 값을 저장하면 됩니다.

process[8]을 구할 때

규칙2와 규칙3을 적용하여 더 작은 연산 횟수를 구하는데

규칙2을 적용했을 때 더 작기 때문에 해당 연산 전 i인 4가 저장됩니다.

process[8] = 4

 

문제를 해결한 알고리즘의 과정입니다.

1. 입력값 N을 저장합니다.

2. 규칙을 통해 count와 process을 구성합니다.

3. count[N]의 값과 prcess의 값이 1이 될 때까지의 값의 과정을 출력합니다.

 

• BufferedReader를 사용하여 입력 값을 받았습니다.
• 규칙을 적용하여 count와 process을 구성하는 cal함수를 만들었습니다.
• BufferedWriter에 최소 연산 횟수와 process에 저장된 과정을 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

• cal은 반복문과 규칙을 통해 count와 process을 구성하였습니다.

import java.io.*;
import java.util.*;
public class Main{
	static int N;
	static int[] count,process;	//최소 연산횟수 저장 배열, 연산 이전 값 저장 배열
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //---------입력값 저장 및 배열 초기화-------
    	N = Integer.parseInt(br.readLine());
    	count = new int[N+1];
    	process = new int[N+1];
    	Arrays.fill(count, Integer.MAX_VALUE);
    	count[1] = 0;	//1은 연산횟수가 0으로 초기화
    	cal();	//count와 process 구성하는 함수 실행
    	bw.write(count[N]+ "\n");	//최소 연산 횟수 BufferedWriter 저장
    	int index = N;
        //process의 값이 1이 될 때까지의 과정 BufferedWriter 저장
    	while(index != 0) {
    		bw.write(index + " ");
    		index = process[index];
    	}
    	bw.flush();		//결과 출력
    	bw.close();
    	br.close();
    }
    //count와 process를 구성하는 함수
    static void cal() {
    	//count규칙을 적용하면서 같이 process의 값도 저장 진행
    	for(int i=2;i<=N;i++) {
    		if(i%3==0) {		//count 규칙1.
    			count[i] = count[i/3] + 1;
    			process[i] = i/3;
    		}
    		if(i%2==0) {		//count 규칙2.
    			if(count[i/2] + 1 < count[i]) {
    				count[i] = count[i/2] + 1;
    				process[i] = i/2;
    			}
    		}
            //count 규칙3.
    		if(count[i-1] + 1 < count[i]) {
    			count[i] = count[i-1] + 1;
    			process[i] = i-1;
    		} 		
    	}
    	return;
    }    	   
}