[백준/python][dp] 백준 13703번 - 물벼룩의 생존확률

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

13703번: 물벼룩의 생존확률

문제

수면에서 k 센티미터 아래에 있는 물벼룩은 1초마다 각각 1/2의 확률로 위 또는 아래로 1 센티미터 이동한다.  물벼룩은 수면에 닿자마자 기다리고 있던 물매암이들에 의해 먹혀 없어진다.  예를 들어, 수면아래 2 센티미터에 있던 물벼룩은 3초 동안 "위위위, 위위아래, 위아래위, ..., 아래아래아래"의 8가지 방법으로 움직일 수 있고, 이 방법들의 확률은 모두 1/8로 같다.  이 중, "위위위, 위위아래"의 경우 2초만에 수면에 닿자마자 먹혀 없어진다.  그리고 나머지 6가지 경우에는 수면아래에 살아있게 되어, 3초후 생존확률은 6/8이다.  수면아래 k 센티미터에 있는 물벼룩이 n초후 생존할 확률이 S/2^n일때 S를 계산하시오.

---

입력

첫째 줄에 k와 n이 주어진다. (0 ≤ k ≤ n ≤ 63)

---

출력

첫째 줄에 S를 출력한다.

---

예제 입력1

2 3

예제 출력1

6

 

예제 입력2

3 10

예제 출력2

672

 

---

코드

from sys import stdin 
r_line = stdin.readline

k, n = map(int, r_line().split())
arr      = [0 for _ in range(k+n+1)]
temp_arr = [0 for _ in range(k+n+1)]

# 초기화
arr[k] = temp_arr[k] = 1
a_len = k+n+1

for i in range(n): # n초만큼 반복 0,1,2
    for j in range(1, a_len):
        if arr[j]: # 값이 있다면
            temp_arr[j-1] += temp_arr[j] 
            temp_arr[j+1] += temp_arr[j]
            temp_arr[j] = 0
    
    # arr = temp_arr ==> 1.잘못된 풀이입니다. 
    # for i in range(a_len): ==> 2.파이썬을 잘 이용하지 못한 풀이입니다.
    #     arr[i] = temp_arr[i]
   arr = temp_arr[:] #==> 3. BEST ANSWER 입니다.
   
print(sum(arr)-arr[0])

풀이

수면이 k센티미터인데, 0센티미터로 가면 물벼룩은 바로 죽게 된다.

최상의 경우로, 물벼룩이 수면아래로만 계속 갈경우, Kcm에서 n초동안 들어가는거기 때문에

마지막 n초에 한 번 더 분기하는 경우까지 생각해서

arr      = [0 for _ in range(k+n+1)]
temp_arr = [0 for _ in range(k+n+1)]

만큼의 배열과, pre(이전) 배열을 저장할 똑같은 크기의 배열을 선언한다.

 

예제입력 1의 예시를 대입하면

이런 점화식을 세워볼 수 있다.

arr[j]에 값이 있다면 양옆으로 똑같은 값을 분배하고, 자신은 0이 된다.

위아래로 전부 분기할 수 있고, 다음초에 가만히 있을 수 없기 때문이다.

따라서 반복문은 항상 1부터 실행한다. 0은 이미 물벼룩은 이미 죽은거기 때문이다.

 

여기서 파이썬문법을 생각해 볼 필요가 있다.

필자는 문법을 잘 못 이해해서 1시간 이상에 시간을 소요하였다.

 

    1.잘못된 풀이입니다.
    arr = temp_arr 
    
    2.파이썬을 잘 이용하지 못한 풀이입니다.
    for i in range(a_len): 
        arr[i] = temp_arr[i]
        
   3. BEST ANSWER 입니다.
   arr = temp_arr[:]

필자가 하고 싶었던 해결방법은 배열 A에서 배열 B(값)만을 복사하고 싶었다.

파이썬에서는 주소의 개념을 사용하지 않는지 알고 

1번으로 arr = temp_arr 되는지 알았는데, 다른 의미가 존재했다.

이때, 단순히 값에 대해서는 문제가 없게 된다.

하지만 c언어에서 포인터를 지정한 것과 비슷한 경우가 된다.

 

예를 들면,

list_A = ["ABC", "DEF"]
list_B = list_A

이런 경우라면, 이처럼 값만 복사하는 게 아니라, A배열이 B배열의 주소값을 가리키게 된다.

따라서 값만 복사하려면 다른 방법을 사용해야 한다.

 

2번의 경우인

    2.파이썬을 잘 이용하지 못한 풀이입니다.
    for i in range(a_len): 
        arr[i] = temp_arr[i]

는 인덱스당 값을 할당하는 다른 저급언어에서 사용되는 방법이다.

이는 파이썬문법을 잘 활용하지 못한 예이다.

 

best 정답인 3번은

   3. BEST ANSWER 입니다.
   arr = temp_arr[:]

는 값을 복사하되 인덱스처음부터 끝까지라는 뜻의 [:] 슬라이싱 기호를 사용함으로써

파이썬 문법을 잘 활용해서 list를 복사한 예이다.

 

따라서 값을 복사하여 나온 최종 배열에서

0번(=죽은 물벼룩)을 제외하고 나머지 sum을 구하면 정답을 구할 수 있다.