[백준_1463]1로 만들기 with Python, Java

백준(BOJ) DP 문제집: 1로 만들기(실버 3)

문제 출처: https://www.acmicpc.net/problem/1463

1463번: 1로 만들기

 

1. 알고리즘

DP 알고리즘 사용하면 쉽게 풀린다. 배낭 문제처럼...? 1부터 N까지 이전 숫자+1로 숫자를 만들어 횟수를 카운팅해주면 됨.

예전에 Python으로 풀었을 땐 한 번에 잘했던데 이번에 Java로 풀 때 중간에 로직을 바꾸면서 else if를 사용하는 바람에 한 번 틀림.

else if를 사용하면, 2나 3으로 동시에 나눠지는 숫자들에 대해 3으로만 처리한다. >> 틀린다는 뜻.

아 그리고 Java로 풀면서 성능이 궁금해져서 이것저것 해봤다. 나중에 재귀로 풀어서도 비교해봐야지

 

• N 입력받음
• N+1의 배열 생성
• 2부터 N까지 반복하며 숫자를 만드는 횟수 카운팅
  • 각 경우를 저장할 List 생성
  • 이전 숫자에 3을 곱해서 n 을 만드는 경우, 2를 곱해서 n을 만드는 경우, 1을 더해서 n을 만드는 경우 횟수를 카운팅
    • 만들 수 있으면 List에 넣음
    • 만들 수 없으면 pass
    • List의 최소값을 배열 n번 인덱스에 삽입
• 배열의 N 인덱스 숫자 출력

 

2. 유의 사항

 

 

3. 어려웠던 점, 해결 방법

• 3 또는 2로 나뉘는 지 여부를 확인할 때, else-if문을 사용하면 한 가지 경우에 대해서만 확인함.
  
  • if문으로 수정

 

 

4. 소스코드

자세한 설명은 주석 참고

4-1. Python

import sys
 
 
if __name__=="__main__":
    N = int(*map(int, sys.stdin.readline().split()))
    cal = [0]*(N+1)
 
    for n in range(1, N+1):
        if n == 1:
            continue
        count = []
        #3으로 나누어 떨어지면
        if n % 3 == 0:
            count.append(cal[n//3]+1)
        #2로 나누어 떨어지면
        if n % 2 == 0:
            count.append(cal[n//2]+1)
        #1을 뺀다
        count.append(cal[n-1]+1)
 
        #가장 적은 연산 횟수로 갱신
        cal[n] = min(count)
 
    print(cal[N])

 

 

4-2. Java: ArrayList 사용

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
 
public class Main {
 
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        
        int[] values = new int[N+1];    //카운팅 담을 배열
        for(int i=2; i<=N; i++) {
            ArrayList<Integer> temp = new ArrayList<>();
            if(i%3 == 0)    temp.add(values[i/3]+1);    //3으로 나눌 수 있을 때
            if(i%2 == 0)    temp.add(values[i/2]+1);    //2로 나눌 수 있을 때
            temp.add(values[i-1]+1);                    //1 더할 때
            
            values[i] = Collections.min(temp);            //경우의 수 중 가장 작은 
        }
        
        System.out.println(values[N]);
    }
}

 

 

4-3. Java: int 배열 사용

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
 
public class Main {
 
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int N = Integer.parseInt(br.readLine());
        
        int[] values = new int[N+1];
        for(int i=2; i<=N; i++) {
            int[] temp = new int[3];
            Arrays.fill(temp, Integer.MAX_VALUE);    //최소값 카운팅을 위해 최대값으로 채움
            
            if(i%3 == 0)    temp[0] = values[i/3]+1;    //3으로 나뉠 때
            if(i%2 == 0)    temp[1] = values[i/2]+1;    //2로 나뉠 때
            temp[2] = values[i-1]+1;                    //1 더할 때
            
            values[i] = Arrays.stream(temp).min().getAsInt();    //배열의 최소값으로 
        }
        System.out.println(values[N]);
    }
}

 

5. 생각

• 4. 소스코드 결과를 보면 ArrayList로 min값 가져오는 게, int배열 min값 가져오는 것보다 훨씬 빠름
• Arrays.fill 추가 연산이 들어가서 인가? 아니면 Arrays.stream 함수도 더 느려서 복합적인 결과인가?
• 다른 풀이로도 효율 어떻게 나올지 궁금하다