[백준] 1로 2만들기 2 / DP python 실1

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

 

처음에 접근하려고 한 방법

 

일단 1,2,3인경우에는 답이 간단하게 나오니까

각 경우는 직접 출력하고,

그 이상의 값은 dp를 이용하도록 하려고 했다

 

for문으로 4부터 n+1까지 순회하면서

현재 값이 2로 나누어 떨어지면 dp[i//2]를 temp 배열에 넣고

현재 값이 3으로 나누어 떨어지면 dp[i//3]을 temp 배열에 넣고

dp[i-1]값을 temp배열에 넣고

 

이 temp 배열에서 min값을 구해서 dp[i]에 min값+1을 넣었다

 

이와 같은 점화식을 세우게 된 이유는

직접 그려봤을 때

min 길이를 구하는 방법이 방금 설명한 방법과 같았기 때문

 

우선 이렇게 해서 1로 도달하는 최소 길이 구하는 것까지는 괜찮았는데,

그 후 n에서 1로 도달하는 경로의 숫자를 출력하는 부분ㄴ이 issue였다

 

dp 배열에서 역순으로 추적하며, i의 length가 이전에 이미 탐색한 숫자보다 작으면

해당 i를 업데이트 하는 방식으로 추적했는데,

정답이 아닌 것 같았다

<틀린 풀이(접은글)>

n = int(input())
if n==1:
    print(0)
    print(1)
elif n==2:
    print(1)
    print(f'{2} {1}')
elif n==3:
    print(1)
    print(f'{3} {1}')
else:
    ans=[n]
    dp = [0]*(n+1)
    dp[1]=1
    dp[2]=1
    dp[3]=1
    for i in range(4,n+1):
        temp=[]
        if i%2==0:
            temp.append(dp[i//2])
        if i%3==0:
            temp.append(dp[i//3])
        temp.append(dp[i-1])
        dp[i]=min(temp)+1
    flag=dp[n]
    for i in range(n):

        if flag!=dp[n-i] and dp[n-i]<flag:
            ans.append(n-i)
            flag=dp[n-i]
    ans.append(1)
    print(*ans)
    print(dp[n])

 

그래서 다시 풀어보았다

전체적인 접근은 맞았는데

경로를 출력하기 위해 dp를 설계하면서 path 배열도 같이 만들어줘야 하는 걸 알았다

 

dp를 빌드

1. dp[i]=dp[i-1]+1

이전 원소에서 높이가 1 증가한 값을 일단 대입

2. 만약 현재 숫자가 2로 나누어 떨어지면서, 방금 1번에서 대입한 값보다 dp[i//2]+1 값이 작은 경우

현재 숫자에서 1를 더해서 다음 숫자로 접근하는 tree의 높이보다

i//2번째 숫자에서 2를 곱하고 1을 더해서 다음 숫자로 접근하는 tree의 높이가 작은 경우

그 값으로 dp[i]를 업데이트한다

 

경로 배열에 현재 순번에 i//2 값을 추가한다

 

3. 만약 현재 숫자가 3으로 나누어 떨어지면, 1번에서 대입한 값보다 dp[i//3]+1값이 작은 경우

2번과 같은 논리로 dp[i//3]+1값으로 업데이트하고

경로 배열의 현재 순번에 i//3 값을 추가한다

 

이렇게 하면 dp 배열을 구할 수 있고, dp[n]을 출력하면 n에서 1로 가기 위한 최소 횟수를 알 수 있다

 

그다음 path 배열을 사용해서 그 경로를 구한다

 

result 배열을 두고, 현재 숫자를 n으로 둔다

 

while문이 current가 -1이 될때까지 돌린다

- result에 current값을 삽입한다

- current값을 path[current번째]로 업데이트한다

 

path = [-1, -1, 1, 1, 3, 4, 3, 6, 4, 3, 9]
dp = [0, 0, 1, 1, 2, 3, 2, 3, 3, 2, 3]

 

이게 이해가 잘 안돼서... 배열로 직접 해봐야겠다

 

1. current=10으로 시작

2. 10 삽입 path[10] = 9로 current 업데이트

3. 9 삽입, path[9] = 3

4. 3 삽입, path[3] = 1

5. 1 삽입, path[1] = -1, 종료

 

10 9 3 1

 

이게 가능한 이유는 아까 for문 돌 때 dp[i]값 업데이트 하면서

dp[i]의 최소 값을 업데이트 할 때

path[i]에 i에서 최소 경로로 이동하기 위해 필요한 다음 값을 path에 집어넣기 떄문이다

 

그래서 path 배열의 current 번째를 탐색하면, 현재 숫자에서 최소경로로 가기 위한 다음 숫자를 알 수 있는 것이다

 

그래서 전문 코드는 아래와 같다

 

n = int(input())

dp = [0]*(n+1)
path = [-1]*(n+1)

for i in range(2,n+1):
    dp[i] = dp[i-1]+1
    path[i] = i-1

    if i%2==0 and dp[i]>dp[i//2]+1:
        dp[i] = dp[i//2]+1
        path[i] = i//2
    if i%3==0 and dp[i]>dp[i//3]+1:
        dp[i] = dp[i//3]+1
        path[i]=i//3
print(dp[n])
result=[]
current=n
while current!=-1:
    result.append(current)
    current = path[current]

print(*result)