백준 (1463번) : 1로 만들기

우선 해당 문제를 1시간 이내 풀지 못했다 :(

그래서 해당 문제에 대한 풀이를 구글링해서 찾아보았다.

 

코드들을 처음 보았을 때 바로 이해하지 못하여서 내가 이해한 대로 코드를 더 풀어보았다.

동적 계획방법에서 이전에 수행했던 계산 값을 배열에 저장하는데, 이러한 방법 중 대표적인 방법이

Top-down과 Bottom-up 이라고한다. 

 

우선 Bottom-up 방식에 대해서 해당 문제를 풀어보도록 하자

1. DP : Bottom-up 방식 

x=int(input()) # 수 입력받기

d=[0]*(x+1) 
for i in range(2,x+1): 
    # 1을 빼준 연산 ( 연산 후 카운트 + 1 해줌)
    d[i]=d[i-1]+1
    if i%2==0: 
        # print('i가 2로 나눠질 때')
        print(f"d[{i}] = min( d[{i}] : {d[i]} , d[{i//2}] : {d[i//2]} + 1)")
        d[i]=min(d[i],d[i//2]+1)
        print(f"d[{i}] : {d[i]}")
        print()
    if i%3==0:
        # print('i가 3으로 나눠질 때')
        print(f"d[{i}] = min( d[{i}] : {d[i]} , d[{i//3}] : {d[i//3]} + 1)")
        d[i]=min(d[i],d[i//3]+1)
        print(f"d[{i}] : {d[i]}")
        print()
    if (i%2!=0) and (i%3!=0):
        # print('i가 2와 3으로 나눠지지 않을 때')
        print(f"d[{i}] = d[{i-1}] : {d[i-1]} + 1")
        print()

x 에 10을 넣어주면 더보기와 같은 출력물을 보여준다.

해당 방법이 Bottom up인 이유는 x라는 수를 1부터 시작해서 x까지의 연산을 다 하기 때문이다. 

그래서 다소 연산속도가 느리다.

d[2] = min( d[2] : 1 , d[1] : 0 + 1)

d[2] : 1

 

d[3] = min( d[3] : 2 , d[1] : 0 + 1)

d[3] : 1

 

d[4] = min( d[4] : 2 , d[2] : 1 + 1)

d[4] : 2

 

d[5] = d[4] : 2 + 1

 

d[6] = min( d[6] : 4 , d[3] : 1 + 1)

d[6] : 2

 

d[6] = min( d[6] : 2 , d[2] : 1 + 1)

d[6] : 2

 

d[7] = d[6] : 2 + 1

 

d[8] = min( d[8] : 4 , d[4] : 2 + 1)

d[8] : 3

 

d[9] = min( d[9] : 4 , d[3] : 1 + 1)

d[9] : 2

 

d[10] = min( d[10] : 3 , d[5] : 3 + 1)

d[10] : 3

 

2. DP : Top-Down 방식 

x=int(input())
dp={1:0}
def rec(n):
	
    # 딕셔너리에 key값이 있을 경우 반환
    if n in dp.keys():
        return dp[n]
    
    # 2의 배수 이면서 3의 배수인 경우 최소값 구하기
    if (n%3==0) and (n%2==0):
        print(f"dp[{n}] = min( rec({n//3})+1, rec({n//2})+1 )")
        dp[n]=min(rec(n//3)+1, rec(n//2)+1)
    
    # x가 3의 배수인 경우
    elif n%3==0:
        print(f"dp[{n}] = min( rec({n//3})+1, rec({n-1})+1 )")
        dp[n]=min(rec(n//3)+1, rec(n-1)+1)
    
    # x가 2의 배수인 경우
    elif n%2==0:
        print(f"dp[{n}] = min( rec({n//2})+1, rec({n-1})+1 )")
        dp[n]=min(rec(n//2)+1, rec(n-1)+1)
    
    # 위 조건이 모두 아닌경우 즉, 1을 빼는 경우
    else:
        print(f"dp[{n}] =  rec({n-1}) + 1")
        dp[n]=rec(n-1)+1

    return dp[n]
print(rec(x))

x 에 10을 넣어주면 더보기와 같은 출력물을 보여준다.

해당 방법이 Top Down인 이유는 x라는 수를 x부터 시작해서 1까지의 연산을 다 하기 때문이다. 

그리고 x가 2의 배수, 3의 배수, 1을 뺀 경우를 dict에 넣어두어 dict안에 n이 있을 경우 최소 값이 저장되어 있어 해당 값을 return 한다.

 

dp[10] = min( rec(5)+1, rec(9)+1 )

dp[5] = rec(4) + 1

dp[4] = min( rec(2)+1, rec(3)+1 )

dp[2] = min( rec(1)+1, rec(1)+1 )

dp[3] = min( rec(1)+1, rec(2)+1 )

dp[9] = min( rec(3)+1, rec(8)+1 )

dp[8] = min( rec(4)+1, rec(7)+1 )

dp[7] = rec(6) + 1

dp[6] = min( rec(2)+1, rec(3)+1 ) 3

3

 

해당 문제를 Dynamic Programming 방법으로 접근하여 푸는 방법을 알아보았다.

코드를 이해하는 것은 해냈지만, 어떻게 저렇게 생각을 할 수 있을까 ?  는 아직 멀은 것 같다.

동적 프로그래밍 방법 안에서도 정보를 저장하는 방법 (메모제이션)이 다양하고, 어떻게 접근하는지 살짝 알게 된 문제였다..

 

---

백준 링크: https://www.acmicpc.net/problem/1463

1463번: 1로 만들기