[백준] 1453 1로 만들기

백준 1453번 1로 만들기

DP

 

---

 

[문제]

 

기본적인 DP(동적계획법) 문제

오랜만에 풀게되서 dp를 생각하지 못했고 dp개념을 다시 공부한 후 풀었다.

 

핵심은 1,2,3번으로 나온 연산의 최소횟수를 구하는 것

 

---

[과정]

dp - BottomUp 풀이 / for문 사용

다른 하나는 재귀를 사용하는 TopDown 풀이가 있는데 이 문제에서는 BottomUp풀이를 사용했다.

 

• n에 변수 입력받기
• dp배열을 0이 (x+1)개 있는 리스트로 초기화
  • dp[1]은 0이고 1이 1로 되는데 필요한 연산은 0회라는 뜻
  • 즉, 이후에 dp[2]는 2가 1이 되는데 필요한 최소 연산 횟수인 1이 될 것
• 2부터 n+1까지 반복
  • dp[i]=dp[i-1]+1 : d[i]는 숫자 i가 1이 되는데 걸리는 최소한의 연산 횟수를 저장
  • i에서 1을 빼면 i-1이 되므로, dp[i-1]+1을 함으로써, dp[i-1] (i-1이 1이 되는데 필요한 최소한의 연산) + 1 (i에서 1을 빼서 i-1이 되는데 필요한 연산 횟수 1회)로 초기화
• if i%2==0:    dp[i]=min(dp[i],dp[i//2]+1) : i가 2로 나누어 떨어질 때, dp[i]와 dp[i//2]+1중 최솟값을 dp[i]에 저장
  • dp[i//2]+1 : i를 2로 나눈 값이 1이 되는데 걸리는 최소 연산 횟수+i를 2로나누는 연산횟수 1회
• if i%3==0:    dp[i]=min(dp[i],dp[i//3]+1) : i가 3으로 나누어 떨어질 때, dp[i]와 dp[i//3]+1 중 최솟값을 dp[i]에 저장

 

---

[소스코드]

 

# 백준 1453 1로만들기

n = int(input())
dp = [0]*(n+1)


for i in range(2, n+1):
    dp[i] = dp[i-1]+1
    if i % 2 == 0:
        dp[i] = min(dp[i], dp[i//2]+1)
    if i % 3 == 0:
        dp[i] = min(dp[i], dp[i//3]+1)
    
print(dp[n])

 

직관적으로 dp배열의 변화를 보고싶어서 출력문을 찍어본 형태는 다음과 같다.

 

---

[통과]

 

 

---

 

// 스터디에서 dp문제가 나와 dp개념을 다시 잡기위해서 dp기본문제를 풀어봤다.