[백준 - 1463][Python] 1로 만들기

안녕하세요 성조입니다.

이 문제는 Python 3 버전으로 풀이했습니다.

 

주어진 식이 엄청나게 어렵고, 접근하기 어려운 문제는 아니었지만 추측했던 풀이 방법이 다르다는 것을 알 수 있었던 문제였습니다. 

 

 

문제출처

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

1463번: 1로 만들기

---

문제

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.

1) X가 3으로 나누어 떨어지면, 3으로 나눈다.

2) X가 2로 나누어 떨어지면, 2로 나눈다.

3) 1을 뺀다.

정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.

 

입력

첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.

 

출력

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

 

코드

import sys

X = int( sys.stdin.readline() )
N = [0] * (X+1)

for i in range( 2, X+1 ):
    
    N[i] = N[i-1] + 1

    if i % 3 == 0:
        N[i] = min( N[i//3] + 1, N[i] )
        
    if i % 2 == 0:
        N[i] = min( N[i//2] + 1, N[i] )

print( N[X] )

 

풀이

반복문이 2부터 시작하는 이유는 i가 1인 경우 어떤 값이든 나눌 수 있기 때문에 연산이 중첩된다.

1. X가 3으로 나누어 떨어지는 경우 즉, [ i % 3 == 0 ]인 경우. 3으로 값을 나눠준다.

[ // 연산자 적용] -> [피연산자] A [연산자] // [피연산자] B

 

2. X가 2 나누어 떨어지는 경우.

[값 // 2] 연산을 한다.

 

3. 값은 1을 만들기 위한 것이므로 N[i] = N[i-1] + 1 코드를 반복문의 시작에 대입한다.

 

 

---

오타나 이해가 안 가는 부분이 있다면 언제든지 댓글로 얘기해 주시면 감사드리겠습니다.

 

다음 포스팅 때 뵙겠습니다.