[python]백준 1463번 : 1로 만들기

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

나의 답

연산의 우선순위를 매겼음

1빼기 < 2나누기 < 1빼고 3나누기 < 3나누기

여기서 3나누기 > 1빼고 2나누기 이러한 가정을 예제 계산만으로 확정한대서 문제가 있었지 않나 싶다.

연산에 우선순위를 두는 것은 의미가 없음

 

다른 답

(2020-04-19 수정)

동적 계획법(Dynamic programming)을 이용하는 방법

동적 계획법은 어떤 문제의 답을 메모리에 저장해두었다가 다시 값을 구해야할 때 중복계산이 필요없게 가져다 쓰는 기법이다.

x = int(input())
count = 0
minimum = [x]

def cal(x): # 주어진 행렬의 모든 수 각각에 대해서 -1, 3으로 나누기, 2로 나누기의 3가지 연산을 모두 진행
    list = []
    for i in x:
        list.append(i-1) # 1은 모든 상황에서 뺄 수 있음
        if i%3 ==0: # 3으로 나눠지는 상황
            list.append(i/3)
        if i%2 ==0: # 2로 나눠지는 상황
            list.append(i/2)
    return list

while True:
    if x == 1: # 처음 입력받은 수가 1이면
        print(count)
        break
    temp = minimum[:] # minimum 행렬의 수들을 옮겨받음
    minimum = []
    minimum = cal(temp) # 다음 행렬을 받음
    count +=1
    if min(minimum) == 1:
        print(count)
        break

풀었을 땐 맞다고 생각했는데, 시간이 지나고 현재 이 코드를 보니 메모이제이션이 안되어있다. 그러면 3^(10^6)번의 연산이 최대 발생할 수 있는데 어떻게 시간초과가 안 나왔을까? (의문..) 또한 메모이제이션은 커녕 한번의 cal 함수 상에서 동일한 수가 결과로 나오면 지우도록 set으로 구현도 안해두었다.

 

고친 코드

<함수 내의 set만 구현한 코드>

x = int(input())
count = 0
minimum = [x]

def cal(x): # 주어진 행렬의 모든 수 각각에 대해서 -1, 3으로 나누기, 2로 나누기의 3가지 연산을 모두 진행
    a = set()
    for i in x:
        a.add(i-1) # 1은 모든 상황에서 뺄 수 있음
        if i%3 ==0: # 3으로 나눠지는 상황
            a.add(int(i/3))
        if i%2 ==0: # 2로 나눠지는 상황
            a.add(int(i/2))
    return list(a)

while True:
    if x == 1: # 처음 입력받은 수가 1이면
        print(count)
        break
    temp = minimum[:] # minimum 행렬의 수들을 옮겨받음
    minimum = []
    minimum = cal(temp) # 다음 행렬을 받음
    print(minimum)
    count +=1
    if min(minimum) == 1:
        print(count)
        break

 

 해당 코드는 함수 내에서 list를 쓰던 코드를 set을 쓰도록 바꿔서 동일한 수가 나올 경우 없애게 하였다.

그랬더니 원래는 위와 같이 중복된 수가 계속 나오던 list가 아래와 같이 중복된 수가 나오지 않게 구성되었다. 물론 set의 특성상 정렬되긴 하지만 어차피 모든 수에 대해서 구해야하기 때문에 상관없다.

 

 

 메모이제이션도 시도해보려고 했으나, python set 자료구조의 특성상 add 연산시에도 현재 set 내부에 해당 요소가 있는데 덮어씌우는 건지 확인할 수 없고 find 연산 처럼 내부에 해당 요소가 있는지 찾는 연산은 set 자료구조 특성상 당연히 없기 때문에 구현하려면 모든 요소를 for문으로 돌리면서 비교해봐야한다.

그래서 그냥 안했다. (머쓱)

https://doorbw.tistory.com/57 참고