[DP] 백준 #1463 / 1로 만들기(+ Scanner와 BufferedReader의 차이)

뭐... 문제는 요약할게 없으니 패스! DP 문제 중에서도 중~하위 문제라고 하는데 정답률이 ㄷㄷ...

맨 처음에는 역시나! 백트래킹 기법으로 풀어봤지만, 역시나 DP문제를 백트래킹으로 푸는건 위험한듯 하다... (Memoization 기법을 사용하지 않는다면..)

그래서 그냥 DP로 풀었다.

import java.util.Scanner;
 
public class boj_1463 {
    public static void main(String args[]) {
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();
        int dp[] = new int[N+1];
        dp[1] = 0;
        
        for(int i=2;i<=N;i++) {
            dp[i] = dp[i-1]+1;
            if(i%2==0) dp[i] = dp[i/2]+1 > dp[i] ? dp[i] : dp[i/2]+1;
            if(i%3==0) dp[i] = dp[i/3]+1 > dp[i] ? dp[i] : dp[i/3]+1;
        }
        System.out.println(dp[N]);
    }
}
 

dp[i]가 의미하는 바는, 'i를 1로 만들기 위해 필요한 연산 횟수'이다.

(dp문제를 풀 때는 dp가 의미하는 바를 저렇게 정확하게 정의한 뒤에 문제를 풀어야 쉽게 풀리는 것 같다)

그러므로 dp[1]은 자연스럽게 '1을 1로 만들기 위한 연산 횟수' 이므로 0이 된다.

그 다음, 반복문이 의미하는 바는, 위에서 처음에 언급한 대로, i를 1로 만들기 위해 필요한 연산 횟수인데

처음에 문제 조건을 보면, 현재의 수에서 -1을 하거나, 3으로 나누거나, 2로 나누거나 세 가지중 하나인데

이 중에서 아무런 제한 없이 무조건 실행 가능한 케이스는 '현재 수에서 -1'을 하는것 밖에는 없었다.

즉 -1은 무조건 실행되는 케이스 이므로 조건문 보다 위에 있어야 함을 의미한다.

그 다음, 조건에 충족 되었을 때, -1 연산을 한 것과 횟수를 비교하여 더 작은 횟수를 dp에 축적시켜서

마지막에 N번째 값을 출력하면 된다는 의미가 된다.

웬만해서는 DP는 반복문으로 풀려고한다. (재귀보다는 반복문이 실행 시간을 더 줄여주기 때문)

그렇게 제출을 해봤는데 실행시간이 생각보다 길었다. 그래서 상위 랭커들의 코드를 살펴본 결과... 흥미로운 사실을 알게 되었다.

바로 바꿔서 제출해본 결과...

메모리도 줄고, 실행 시간도 28MS 씩이나 줄어든 것을 볼 수 있었다. 다음은 수정본이다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
 
public class boj_1463 {
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        int dp[] = new int[N+1];
        dp[1] = 0;
        
        for(int i=2;i<=N;i++) {
            dp[i] = dp[i-1]+1;
            if(i%2==0) dp[i] = dp[i/2]+1 > dp[i] ? dp[i] : dp[i/2]+1;
            if(i%3==0) dp[i] = dp[i/3]+1 > dp[i] ? dp[i] : dp[i/3]+1;
        }
        System.out.println(dp[N]);
    }
}
 

단순히 Scanner를 이전에 포스팅했던 BufferedReader로 바꾼게 전부인데... 그래서 구글링 발동!!

찾아본 결과, 각각은 장, 단점을 갖고 있었다.

BufferedReader는 InputStreamReader에 버퍼링 기능을 추가해서 데이터를 한 번에 읽어서 버퍼에 보관 후, 사용자가 요청할 때

버퍼에서 읽어오는 방식으로, 속도가 매우 빨라서 시간의 부하를 줄일 수 있으나 코드가 길어서 외우기 불편하다는 정도...?

Scanner는 알아서 토크나이징, 파싱을 해주기 때문에 편리하지만, 속도면에서 굉장히 느리다. 그 이유가 Regex를 많이 사용하기 때문이라고 한다.

Regex는 정규 표현식(Regular Expression)의 약자인데, 이 것을 사용하면 패턴을 통해 세밀하게 문자열을 찾아낼 수 있다고 한다.

즉, Regex를 이용함으로써 Tokenizing과 Parsing이 가능한 이유도 그 때문이라고 할 수 있다. 패턴 분석때문에 시간소모가 많다는 점으로 받아들이면 될 것 같다.

C에서의 scanf, printf 가 C++에서 cin, cout과 속도면에서 차이가 나는 것도 비슷한 이유에서가 아닐까... 생각해보지만 정확한건 아니니까 따로 공부해보는걸로 해야겠다.

아무튼! 앞으로는 Scanner보다 BufferedReader와 더 친해져야겠다.