[Python 백준] 1463 | 1로 만들기
Try to solve 💭
처음엔 정수 x에 1,2에 우선순위를 두어 나누어 떨어지지 않으면 3을 연산하는 방식을 생각했지만, 정수 '10'에서 최솟값이 나오지 않는 예외가 생긴다.
-> 연산순위가 중요한 것이 아니라 연산 결과의 최솟값이 중요한 것이다.
그렇다면 주어진 정수 값에 대해, 3가지 연산을 모두 수행하여 그 중 최솟값을 구하면 될까?
-> 3 or 2로 나누어 떨어지지 않는 수들도 고려하여 조건문을 생성
정수 값이 커질수록 연산량이 상당할 것이다!
-> 결과값을 저장하는 리스트를 생성, 이전 값들의 최소 결과값들을 저장하여 연산량을 줄임
Solution 💡
점화식 이용
- 입력 받은 값의 크기만큼 리스트 생성
- 0부터 n까지 조건식을 수행하는 for문 생성
- 3 or 2로 나누어 떨어지는 값이나 1을 뺀 값 중 최솟값을 리스트에 저장
-> 처음엔 다음과 같이 수행하였다.
..
if i % 3 == 0:
list[i] = list[i//3] + 1
if i % 2 == 0:
list[i] = list[i//2] + 1
list[i] = list[i-1] + 1
..
하지만 최솟값을 고려해야 하기 때문에, 아래 코드와 같이 1을 뺀 값을 저장한 리스트 값과 크기를 비교하는 조건을 추가하여 list에 최종 값을 저장하게 하였다.
( 2,4,5 : 1을 추가하는 이유는 각 연산을 하면 연산 수가 1씩 증가하기 때문! )
Code Review 🔎
n = int(input())
list = [0] * (n+1)
for i in range(0, n+1):
if i == 0 or i == 1:
list[i] = 0
continue
list[i] = list[i-1] + 1
if i % 3 == 0 and list[i//3] + 1 < list[i]:
list[i] = list[i//3] + 1
if i % 2 == 0 and list[i//2] + 1 < list[i]:
list[i] = list[i//2] + 1
print(list[n])
Author And Source
이 문제에 관하여([Python 백준] 1463 | 1로 만들기), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@da__hey/Python-백준-1463-1로-만들기저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)