[코딩테스트] 백준(BAEKJOON) - 1로 만들기(Java, 1463번)

안녕하세요~

오랜만에 다시 인사드리네요~

 

뭐 아무것도 안한건 아니구... 사실 올려야될 글이 밀려있는데

지금 하는일이 많다보니 다 딜레이 되고있네요.

 

최근글이 뜸했던 이유는 제가 요즘 출근길에는 쿼리문제가 아닌 알고리즘 관련 글을 읽기 시작했기 때문입니다.

 

특히 그중에서 DP(Dynamic Programming)문제를 다뤄보고자 합니다.

 

처음으로 백준관련 문제를 풀어보는거같은데 환경을 맞춰주는게 프로그래머스보다 어렵네요~

 

그래도 어찌저찌 성공했습니다.

그럼 문제 만나보시죠!

https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

문제의 조건은 크게 3가지 입니다.

- 주어진 수를 1로 만드는 가장 적은 숫자의 방법을 구하라

① 3으로 나누어진다면 3으로나누고

② 2로 나눠진다면 2로 나누고

③ 혹은 1을빼기

 

즉 저 3가지 방법을 이용해서 가장 작은 방법을 찾아내면 되겠습니다.

그럼 제가 작성한 코드 만나보시겠습니다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

	public static void main(String[] args) throws NumberFormatException, IOException {

		
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        int n=Integer.parseInt(br.readLine());   
        int[] array=new int[n+1];
        array[0]=0;
        array[1]=0;
        
        for(int i=2;i<=n;i++)
        {
        	        	
        	if(i==2)
        		array[2]=1;
        	else if(i==3)
        		array[3]=1;
        	else
        	{
        		array[i]=1+array[i-1];
                if(i%3==0)
                    array[i]=Math.min(array[i], 1+array[i/3]);
                if(i%2==0)
                	array[i]=Math.min(array[i],1+array[i/2]);
                
        	}
        	
        }
        
        System.out.println(array[n]);

	}

}

BufferReader는 프로그래머스에서 쓰질 않다보니 다른글을 참고해서 작성했습니다.

또한 조건문에서 살짝 헷갈렸지만 그래도 나중에 이해하고 수정했습니다.

 

각각의 조건에 맞는 방법의 수를 구한다음에 Math.min을 통해 최소숫자의 방법을 구했습니다.

DP에 대한 설명을 읽어보고 풀어보니 그래도 이해가 됩니다.

 

핵심은 각각의 방법을 구해서 최소값을 찾는다가 되겠습니다.

EX) 주어진 숫자가 9일 경우

1) -1로 하면

-1이라는 한가지 방법을 썼기에 1+

그리고 이제는 8에대해 구한 최소방법을 더하기에 array[8]

을 구하고

 

2) 3이라면

/3을하는 방법을 썼기에 1+

이제는 3을 나눈 array[3]에 저장된 최소방법

을 구하고

 

앞서 구한 1),2)를 비교해 답을 골라주면 되겠습니다.

이해가 되실까 싶어 제생각을 노트에 적어봤습니다.

 

 

오늘은 여기서 마무리하겠습니다.

 

감사합니다. :D