[백준] 1463번 : 1로 만들기 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

1463번: 1로 만들기

 

1. 문제 설명

2. 풀이과정

이 문제는 이전의 결과가 다음의 결과에 영향을 주는 문제이다.

이전의 결과를 다음의 결과에 반영하여 다음 결과를 도출하는 방식으로 구현해야 한다.

저는 입력받은 숫자까지 각 자연수의 값과 연산의 최소 횟수를 딕셔너리에 저장하고 마지막에 딕셔너리에서 입력받은 숫자의 값을 출력하도록 구현하였다.

 

1. sys.stdin.readline() 함수를 사용하므로 sys 모듈을 불러온다. import sys
2. 정수를 하나 입력받는다. N = int(sys.stdin.readline())
3. 딕셔너리를 하나 생성하고 1, 2, 3까지는 각각 값을 대입해 주어 초기화한다. d = {1:0, 2:1, 3:0}
4. 2부터 입력받은 정수까지 모든 정수의 연산 횟수를 딕셔너리에 저장한다. for i in range(2, N + 1)
5. 해당 정수를 key로 하는 value은 우선 모든 경우에서 실행될 경우가 있는 연산인 1을 뺀다의 연산 결과를 비교 대상으로 만들어준다. d[i] = d[i - 1] + 1
6. 다음으로 3보다 2로 나누어 떨어지는 수가 더 많으므로 2로 나누었을 때 나누어 떨어지면 처음의 비교 대상과 2로 나누는 연산의 결과의 값을 비교하여 더 작은 값을 저장해 준다. if (i % 2 == 0): d[i] = min(d[i], d[i // 2] + 1)
7. 마지막으로 3으로 나누었을 때 나누어 떨어지면 3으로 나누는 연산의 결과의 값을 이전 결과와 비교하여 더 작은 값을 저장해 준다. if (i % 3 == 0): d[i] = min(d[i], d[i // 3] + 1)
8. 입력받은 정수까지 연산한 결과를 저장하였으면 딕셔너리에서 입력값이 key인 value를 출력해 준다. print(d[N])

반응형

3. 소스코드

import sys

N = int(sys.stdin.readline())

d = {1:0, 2:1, 3:1}
for i in range(2, N + 1):
    d[i] = d[i - 1] + 1

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

print(d[N])