BAEKJOON 2579
문제
정수 X에 사용할 수 있는 연산은 다음과 같이 세 가지 이다.
첫 번째, X가 3으로 나누어 떨어지면, 3으로 나눈다.
두 번째, X가 2로 나누어 떨어지면, 2로 나눈다.
세 번째, 1을 뺀다.
정수 N이 주어졌을 때, 위와 같은 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값을 출력하시오.
입력
첫째 줄에 1보다 크거나 같고, 106보다 작거나 같은 정수 N이 주어진다.
나의 처음 코드
제일 처음에 생각했을 때는, 특정한 규칙이 숨어있을 것 같았다. 예를들어, 3과2의 배수일 때는 3을 먼저 나눈다던지, 2의 배수인데 2로 나눴을 때도 2의 배수이면 -1을 하지말고 2로 나눠준다던지. 하지만 반례를 보고 바보같은 짓을 했다는 걸 느꼈다. 그런데 문제를 자세히 보다보면, 첫번 째 수로 시작해서 조건에 맞게 연산을 해주면 n번째 연산을 했을 때 다른 문제처럼 2의 n승 만큼 연산을 안해도 된다는 것이다. 자세히 보면 2는 2로 나눠떨어질 때만 나눌 수 있고, 3도 3으로 나눠떨어질 때만 나눌 수 있다는 것이다. 자 그러면, 이것을 Memorizing과 bfs를 통해서 문제를 풀면된다는 것을 직감적으로 알 수 있을 것이다. (사실 직감보다는 개고생 하면 알 수 있다.) 그에 관한 코드는 아래와 같다.
N = int(input())
before_list = [N]
after_list = []
check_list = [True] * 1000001 #memorizing 리스트
num_count = 0
flag = 0
while True:
for i in before_list:
if 1 in before_list:
flag = 1
break
#그 전에 한번도 안나온 값이면 실행한다
if check_list[i] != False:
if i % 2 == 0:
after_list.append(i//2)
check_list[i] = False
if i % 3 == 0:
after_list.append(i//3)
check_list[i] = False
if i % 2 != 0 or i % 3 != 0:
after_list.append(i-1)
check_list[i] = False
#flag가 1이라는 것은, 1이 befor_list에 포함되어 있을 때
#즉, 1이 나왔기 때문에 이제 연산을 그만해도 된다는 뜻
if flag == 1:
break
num_count += 1
before_list.clear()
before_list = after_list.copy()
after_list.clear()
print(num_count)
결과는 맞았습니다. 다른 사람들의 코드에 비해 실행속도가 나름 빠른 편이다. 이유는 잘 모르겠지만 그냥 그런가부다,,, 하고 넘어간다. 단, 이번에 확실히 안 내용은 아래에 적어놓겠다. 리스트 때문에 고생을 조금 했어서,,,
다들 알지 모를지 모르겠지만, C나 C++ 에서는 = 연산자를 쓰면 Shallow copy가 되는 것을 알 수 있다.
int arr1 = [1, 2, 3, 4]; int arr2; arr2 = arr1위와 같이 했을 경우에 arr2에 무슨 짓을 해도 arr1에는 영향이 안 간다는 것이다. 그러나 파이썬 이 자식은 조금 다르다. 저렇게 = 연산자로 리스트를 넣어줬을 경우에는 Deep copy가 된다. 따라서 Shallow copy를 하기 위해서는 다음과 같이 해야한다.
list1 = [1,2,3,4]
list2 = list()
list2 = list1.copy()