[JAVA] 1463번 - 1로 만들기

문제 탐색하기

- 문제에서 구해야 하는 최종 정답은 무엇인지 탐색한 과정
- 그 정답을 구하기 위해 어떻게 코드를 구현해야 할지 고민한 과정
- 문제에 들어오는 범위를 파악하여 어떤 알고리즘을 쓸 수 있을지 고민해 가는 과정

 

이 문제는 DP문제 인데 왜 DP문제로 풀어야하는지 생각했다.

DP적으로 접근(?)을 하려고 노력했다

DP문제가 되려면 큰 문제를 작은 문제로 쪼개서 답을 저장해서 재활용해야한다.

 

두가지 방법으로 풀어봤다.

 

1. top-down방식

할 수 있는 연산은 세가지이다.

1) 3으로 나누기

2) 2로 나누기

3) 1빼기 

n에서 가능한 모든 연산 과정을 수행하고, 이 중에서 최소 연산 횟수를 출력해야한다

 

3과 2로 나누어 떨어지는 경우(=6으로 나누어 떨어지는 경우)

- 3으로 나누는 경우

- 2로 나누는 경우

- 1을 빼는 경우

3으로만 나누어 떨어지는 경우

- 3으로 나누는 경우

- 1을 빼는 경우

2로만 나누어 떨어지는 경우

- 2로 나누는 경우

- 1을 빼는 경우

3, 2 둘다 나누어 떨어지지 않는 경우 

- 1을 빼는 경우

-> 각 경우의 수 중에서 최소값을 구해야한다.

그리고 1을 더해주면되는데

연산 횟수에 1을 더하는 이유는 현재 수행한 연산을 고려하기 위해서입니다. 각 단계에서 최소값을 구하는 것은 그 이전 상태에서의 최소 연산 횟수를 의미하며, 현재 단계에서 추가로 수행된 연산을 포함하기 위해 1을 더해주는 것

 

 

2.Bottom-up방식

이 방식은 아무리 생각해도 모르겠다... 아직도 이해못함 완벽히...

https://bada744.tistory.com/61

[BOJ] 백준 1463번 - 1로 만들기 (Java)

멘토님의 해설도 봤다.. 근데 이걸 봐도 잘모르겟어서 이분 블로그도 참고했다 ㅎ 

(며칠 있다가 다시 봐야겠음)

 

 

시간복잡도

N의 최대 크기는 10^6이니까 1,000,000이다.

O(N) = O(1,000,000)이다. 

 

 

 

코드 설계하기

위의 문제 탐색하기에서 고민한 과정을 토대로 문제 풀이에 대한 실마리를 잡았다면, 문제 풀이를 본격적으로 하기전, 문제를 풀이 위한 로드맵을 그려본다
어떤 순서로 코드를 작성해야 할지, 어떤 함수들을 작성해야 할지 등을 작성

1. dp배열을 만든다.

2. dp연산을 수행한다

3. 출력하낟.

 

시도 회차 수정 사항

- 무분별하게 "맞았습니다" 가 나올때까지 수정하는 형태의 문제 풀이를 반복하면, 내가 어떤 실수를 해서 해당 문제를 틀렸는지 모르게 된다
- 틀렸습니다를 받았다면 왜 틀렸는지 고민핸보고, 어떻게 수정할 수 있는지 고민하는 과정을 작성
- 위에 내가 세울 설계에서 어떤 부분이 틀렸는지도 함께 점검

 

Top-down

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Comparator;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {
	static Integer dp[];
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));	
             
        int n = Integer.parseInt(br.readLine());
        
        dp= new Integer[n+1];
        
        dp[0] = dp[1] = 0;
        
        System.out.println(recur(n));
        
    }

	static int recur(int n) {
		
		if(dp[n] == null) {
			if(n%6==0) {
				dp[n] = Math.min(recur(n - 1), Math.min(recur(n / 3), recur(n / 2))) + 1;
			}
			
			else if(n%3==0) {
				dp[n] = Math.min(recur(n / 3), recur(n - 1)) + 1;
			}
			else if(n%2==0) {
				dp[n] = Math.min(recur(n / 2), recur(n - 1)) + 1;
			}
			else {
				dp[n] = recur(n - 1) + 1;
			}
		}
		return dp[n];
	}

}