[백준 12852번 1로 만들기 2]

728x90

오늘의 문제는 " 1로 만들기 2 "이다.

 

 

#고민의 흐름

처음엔 무조건 완전탐색!

 

이번 문제는 DP문제임을 알고 풀이를 시작했다.

그래서 어떤 방식으로 문제풀이를 할지 고민했었다.

그 결과 DP배열을 만들어주고 1부터 최선(최소)의 값을 채워나가면 되겠다고 생각하였다.

dp [1] = 1; 을 기본으로 설정해 주고, 2부터 N까지 조건에 맞게 이전 값을 참고하고

가장 최소인 값 + 1을 해당 dp[i]에 대입하였다.

 

 

코드는 다음과 같다.

( 코드가 너무 커보인다면 "Ctrl + 스크롤 내리기" 하면 잘 보여요! )

( 초기화는 "Ctrl + 0" / 다시 확대는 "Ctrl + 스크롤 올리기" )

 

import java.util.*;
import java.io.*;

public class Main {
    static Integer[] dp; // dp배열 ~
    static int cnt; // 출력에 필요한 cnt
    static StringBuilder sb = new StringBuilder(); // 출력양식을 맞추기위한 sb
    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 [1000010]; 
        // 문제에서 주어진 10^6에 맞게,
        //하지만 자잘한오류를 피하기 위해 10 더 크게 선언하였다.
        dp[0] = 1000; // 배제하기위해 큰값으로 세팅
        dp[1] = 1; // 1은 1
        cnt = 0; // 0으로 시작.
        for(int i = 2; i<N+1; i++){ // 2부터 주어진 N까지
            if(i % 3 == 0 && i % 2 == 0){ // 3, 2 모두 나눠진다면
            // 두가지 모두 확인하고 1작을 때까지 확인하여 이번 배열칸을 채워준다.
                dp[i] = Math.min(dp[i/3], dp[i/2]);
                dp[i] = Math.min(dp[i], dp[i-1]) + 1;
            }else if(i % 3 == 0){ // 3으로만 나눠진다면,
                dp[i] = Math.min(dp[i/3], dp[i-1]) + 1;
            }else if(i % 2 == 0){ // 2로만 나눠진다면,
                dp[i] = Math.min(dp[i/2], dp[i-1]) + 1;
            }else{ // 3과 2 모두 나눠지지 않을 때.
                dp[i] = dp[i-1] + 1;
            }
        }
        sb.append(N).append(" "); // 맨처음 시작하는 수를 sb에 넣어주고 ,
        trace(N);


        System.out.println(cnt);
        System.out.print(sb);
    }

    static void trace(int cur){ // 출력에 필요한 1까지의 과거를 추적하는 함수이다.
        if(cur == 0 || cur == 1) return; // 0이나 1이면 return;
        cnt += 1; // 0과 1이 아니면 매번 cnt를 더해준다.
        int min = dp[cur]; // 무조건 이전이 현재보단 작을테니 현재 수로 min설정
        int min_idx = 0; // 다음으로 추적할 idx를 저장할 변수
        if(cur % 3 == 0 && cur % 2 == 0){ // main함수에서의 내용과 같다.
            if(min > dp[cur/3]){
                min_idx = cur/3;
            }

            if(min > dp[cur/2]){
                min_idx = cur/2;
            }

            if(min > dp[cur-1]){
                min_idx = cur - 1;
            }
        }else if(cur % 3 == 0){
            if(min > dp[cur/3]){
                min_idx = cur/3;
            }

            if(min > dp[cur-1]){
                min_idx = cur - 1;
            }
        }else if(cur % 2 == 0){
            if(min > dp[cur/2]){
                min_idx = cur/2;
            }

            if(min > dp[cur-1]){
                min_idx = cur - 1;
            }
        }else{
            if(min > dp[cur-1]){
                min_idx = cur - 1;
            }
        }
        if(min_idx == 0){
            sb.append(1).append(" ");
            return;
        }
        sb.append(min_idx).append(" "); // sb에 넣어주고 
        trace(min_idx); // 함수실행 !
    }
}

 

 

최근 문제를 풀다가 멘탈이 나갔었다.

기복이 크다고 느꼈기 때문이다.

뭔가 풀어지는 문제는 잘 풀어내고 못 푸는 문제들은 한참을 걸려도 잘 풀리지 않았다.

그중 하나가 DP문제였다.

그래서 DP문제집을 검색해 문제를 풀이해 보았다.

앞으로도 파이팅 ,,

궁금한 점이 있거나 보충할 점이 있다면 언제든 댓글 부탁드립니다 ~

 

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