[BOJ 12852] 1로 만들기 2

문지영·2023년 4월 11일
0

CODINGTEST

목록 보기
21/21

문제 12852

풀이

정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
1. X가 3으로 나누어 떨어지면, 3으로 나눈다.
2. X가 2로 나누어 떨어지면, 2로 나눈다.
3. 1을 뺀다.

1로 만들기 문제에 N을 1로 만드는 방법에 포함되는 수를 출력해야 함.

  • dp[i]: i가 1이 되는 방법의 최솟값
  • pre[i]: i에서 1로 가기 위한 최소 경로
  • pre[now]은 N에서 1이 될때까지 출력

정답

N = int(input())
dp = [0]*(N+1) # 횟수의 최솟값
pre = [0]*(N+1) # 최소 경로
for i in range(2,N+1):
    dp[i] = dp[i-1] + 1 # 1 빼기
    pre[i] = i-1
    if i%2==0 and dp[i]>dp[i//2]+1: # 2로 나누기
        dp[i] = dp[i//2]+1
        pre[i] = i//2
    if i%3==0 and dp[i]>dp[i//3]+1: # 3로 나누기
        dp[i] = dp[i//3]+1
        pre[i] = i//3
print(dp[N])

now = N
while True:
    print(now, end=' ')
    if now==1: break
    now = pre[now]

제출

profile
BeHappy

0개의 댓글