취준생의 코딩테스트 연습기

[백준] 1463번 1로 만들기 / 파이썬(python) 본문

코딩테스트/백준

[백준] 1463번 1로 만들기 / 파이썬(python)

Jiwon_C 2021. 5. 23. 21:38

# 문제 링크

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

 

1463번: 1로 만들기

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

www.acmicpc.net

# Soultion

1
2
3
4
5
6
7
8
9
10
11
12
13
14
n = int(input())
 
count = [n+1]*(n+1)
count[1]=0
 
for i in range(2,n+1):
    tmp = [count[i-1]]
    if i%2==0:
        tmp.append(count[i//2])
    if i%3==0:
        tmp.append(count[i//3])
    count[i] = min(tmp)+1
    
print(count[n])
 cs
 

3. 최소계산수를 저장하기 위해 n+1개의 배열을 선언

4. 숫자1은 자기자신이므로 0으로 초기화해준다.

7. 1을 뺀 경우

8. 2로 나눈 경우

10. 3으로 나눈 경우

12. 위의 세가지경우에서 최소값을 구해 1을 더해준다.

'코딩테스트 > 백준' 카테고리의 다른 글

[백준] 1654번 랜선 자르기 / 파이썬(python)  (0) 2021.05.25
[백준] 11053번 가장 긴 증가하는 부분 수열 / 파이썬(python)  (0) 2021.05.23
[백준] 1149번 RGB거리 / 파이썬(python)  (0) 2021.05.23
[백준] 10816번 숫자 카드 2 / 파이썬(python)  (0) 2021.05.21
[백준] 1920번 수 찾기 / 파이썬(python)  (0) 2021.05.21
'코딩테스트/백준' Related Articles more
Comments