Algorithm

[백준] 16953 A to B Python, 깊은 복사

YunSeong 2021. 8. 2. 21:30
728x90
반응형

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

 

16953번: A → B

첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.

www.acmicpc.net

 

1. 문제 

이 문제는 A, B를 입력 받아서 

A == B가 true가 되게하기 위해서 

A = A * 2

A = A * 10 + 1

위 두 식을 최소한으로 몇 번 사용해야하는 지 구하는 문제이다.  

 

구체적인 문제는 위 링크에 있다. 

 

 

2. 풀이

이 문제를 보고 제일 먼저 어떻게 계산 횟수를 줄여서 효율적으로 풀어야할 지 고민을 했지만

고민의 결과가 안 나와서 그냥 다 계산해보기로 했다.

 

 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
list = []
 
A, B = input().split(" ")
A, B = int(A), int(B)
list.append(A)
count = 1
while(1) :
    count += 1
    list2 = list[:]
    list = []
    for a in list2 :
        if a * 10 + 1 < B :
            list.append(a*10 + 1)
        if a * 2 < B :
            list.append(a*2)
        if (a*2==or a*10+1==B) :
            print(count)
            exit()
    if list2 == [] :
        print(-1)
        exit()
cs

 

3~4에서 A, B를 입력 받아서 정수 형태로 저장했다.

 

9에서 list2에 list를 깊은 복사를 했다.

10에서 list를 초기화했다. 

 

11~18 list2에 들어있는 모든 원소들을 검사하고 계산했다.

    12~13 a * 10 + 1을 했을 때 B보다 작다면 초기화한 list에 저장했다. 

    14~16 a * 2을 했을 때 B보다 작다면 초기화한 list에 저장했다.

    16~18 만약 식에 넣었을 때 B와 같아진다면 count를 출력한다. 

19~21 만약 위 코드들에서 if문을 통과하지 못해서 list2에 아무 원소도 남지 않는다면 A로 B를 만들 수 없다는 뜻이기에 -1을 출력한다. 

 

 

* 깊은 복사 

list 같이 한 객체의 데이터가 큰 것은 보통 모두 복사하는 것이 아닌 주소만 복사하는 얕은 복사라는 것을 한다. 

만약 list2 = list와 같이 list2에 list를 대입해주고 

list2[1] = 1 이런식으로 list2의 원소를 건드린다면 

list[1]또한 1이 되는 식이다. 

 

얕은 복사가 더 효율적이긴 하겠지만 깊은 복사가 필요한 경우가 있다. 

 

그래서 그때는 list2 = list[:] 이런식으로 [:]를 뒤에 붙인다면 깊은 복사를 할 수 있다. 

 

 

 

728x90
반응형

'Algorithm' 카테고리의 다른 글

[백준] 1309 동물원 Python  (0) 2021.08.08
[백준] 10164 격자상의 경로 Python  (0) 2021.08.02