백준 1003번 문제 (다이나믹 프로그래밍) python 이중 배열

요즘 다이나믹 프로그래밍 완벽 숙지를 위해 매일 하나씩 풀고 있습니다.

 

백준 1003번 문제는 이중 배열을 이용하여 풀었는데요.

 

이중 배열을 대입 연산자를 이용하여 변경할 때 꼭 알아야 하는 내용이 있어 같이 들고 왔습니다.

 

---

문제 1003번

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

1003번: 피보나치 함수

 

 

 

피보나치수열의 응용문제인데 당연히 다이나믹 프로그래밍으로 해결이 가능하다.

 

문제를 보면 fibonacci(1), fibonacci(0) 일 때 각각 1과 0을 리턴한다.

 

그렇다면 fibonacci(2) 일 때는 fibonacci(1) + fibonacci(0) 이니깐 

 

0과 1의 개수가 각각 1개, 1개이다.

 

즉 1 1이 출력되게 된다.

 

 

 

풀이는 작은 수부터 0과 1의 개수를 이중배열을 이용하여 저장시켜주면 된다.

fibonacci(n) = fibonacci(n - 1) + fibonacci(n - 2) 

 

---

이중 배열 정의시 주의할 점

# 반복문을 사용
d = [[0 for col in range(2)] for row in range(41)]

# 반복문 사용 x
d = [[0] * 2] * 41

반복문을 사용하지 않고 이중 배열을 정의해주게 되면

 

d[1][1] = 1

같이 이중배열에 대입 연산자를 사용하면 모든 배열의 2번째 자리에 1이 들어가 있는 것을 볼 수 있습니다.

arr = [[0] * cols] * rows 로 이중 배열을 만들었을 때 생기는 문제가

1. 하나의 정수 개체만 생성됩니다. 
2. 단일 1d 목록이 생성되고 모든 인덱스가 포인트 1의 동일한 int 개체를 가리킵니다. 
3. 이제 arr[0], arr[1], arr[2] … arr[n-1] 모두 위의 2번 지점에서 동일한 목록 객체를 가리킵니다.

한마디로 모든 배열이 같은 객체를 가리키게 된다.

 

이걸 얕은 복사라고 하는데

 

해결 방법은 반복문을 사용하여 이중 배열을 만들면 된다.

---

1. 배열 0과 1에 값을 넣어둔다.

d[0][0] = 1

d[1][1] = 1

 

2. 2부터 40까지 반복문을 이용하여 0과 1 개수를 더하여 저장한다.

for j in range(2, 41):

  d[j][0] = d[j - 1][0] + d[j - 2][0]

  d[j][1] = d[j - 1][1] + d[j - 2][1]

 

완성본

#테스트 케이스의 개수
T = int(input())

#케이스 n은 0<=n<=40
narray = [] * T
for i in range(T):
  n = int(input())
  narray.append(n)
# 대입연산자 이용시 반복문으로 사용하는 것을 권장
d = [[0 for col in range(2)] for row in range(41)]

d[0][0] = 1
d[1][1] = 1

for j in range(2, 41):
  d[j][0] = d[j - 1][0] + d[j - 2][0]
  d[j][1] = d[j - 1][1] + d[j - 2][1]

for k in range(T):
  print(d[narray[k]][0], d[narray[k]][1])