백준 #17202 핸드폰 번호 궁합

 

17202번: 핸드폰 번호 궁합 (acmicpc.net)

17202번: 핸드폰 번호 궁합

 

<내 풀이>

arr=[]

for i in range(15):

    arr.append([])

   

arr_1=list(map(int,input()))

arr_2=list(map(int,input()))

for i in range(8):

    arr[0].append(arr_1[i])

    arr[0].append(arr_2[i])

for i in range(1,15):

    for j in range(len(arr[i-1])-1):

        arr[i].append((arr[i-1][j]+arr[i-1][j+1])%10)

print(*arr[14], sep='')

#

 

arr이라는 리스트 안에 [](빈 리스트) 15개 추가하기

 

arr_1이라는 리스트에 첫번째 전화번호 여덟자리 입력

arr_2라는 리스트에 두번째 전화번호 여덟자리 입력 (정수형으로)

 

arr[0]에다가 arr-1[0] arr_2[0] arr_1[1] arr_2[1] arr_1[3] arr_2[3].... 순으로 넣기 (총 16자리)

 

이제 arr[1]부터 arr[14]까지 리스트에다가 숫자를 넣을 건데, arr[1]이 첫번째 계산한 수로 15자리, 

arr[2]가 두번째 계산한 수로 14자리... 이런 식으로 해서 arr[14]는 두 개의 원소를 가진 리스트로 만들어진다. 

 

넣는 수를 계산하는 방법은 이렇다. 

넣는 리스트의  (바로 앞 리스트에 있는 j번째 원소+ 바로 앞 리스트 에 있는 j+1번째 원소)를 10으로 나눈 것의 나머지

(= 일의자리 수만 입력하고 만약 10, 20 등이면 0으로 입력된다.)

j는 0부터 1씩 늘어나는 수이고, 바로 앞의 원소의 개수보다 2 적은 수까지 출력하는데 마지막 수를 대입하면 마지막+1도 대입돼서 같이 계산되기 때문이다. 

 

그다음에 arr[14]에서 숫자만 추출해서 공백없이 출력한다.

 

 

#

이게 왜 다이나믹 프로그래밍이냐.

한 번 append한 숫자들은 그 다음줄을 계산하는 데 쓰이지만, 다음다음 줄을 계산하는 데는 반영되지 않는다. 

즉 새로운 i로 넘어갈 때마다 그 이전 (i-1번째)리스트만을 참조하면 되도록 값을 차곡차곡 쌓아서,

중복 연산이 없게 만드는 것이다.

 

 

<풀이 후>

 

다른 사람의 풀이를 보고 배운 것

 

1. extend와 append의 차이

 

extend는 리스트를 삽입할 때 리스트 전체를 하나의 원소로 보는 것이 아니라,

리스트를 '확장'하여 리스트 안의 원소들을 각각의 원소로 풀어서 삽입한다. 

 

arr_1=list(map(int,input()))

arr_2=list(map(int,input()))

for i in range(8):

    arr[0].append(arr_1[i])

    arr[0].append(arr_2[i])

이건 append

 

arr_1=list(input())

arr_2=list(input())

for i in range(8):

arr.extend((int(arr_1[i]),int(arr_2[i])))

 

이건 extend

뭐가 다른 거지?

 

 

 

 

 

2. 문제 푸는 방법

 

내 풀이에서는 이차원 리스트를 만들어서 한 줄을 더할 때마다 새로운 리스트에 값을 추가했다. 

그런데 일차원 리스트에서 이전 값을 계산에 이용한 다음, 다음 값으로 덮어씌우는 방법도 있다. 

 

 

그.. 이전 문제들에서 일차원 피보나치 수열에서 배열에다가 새 값을 append하는 게 아니라,

a랑 b라는 변수를 최신값으로 재정의 하면서 계산에 계속 이용하는 것과 같은 원리이다.