프로그래머스 알고리즘 문제 - 2 x n 타일링(python)

🔍문제보러가기

코딩테스트 연습 - 2 x n 타일링

풀이방법

1. 수학 문제 풀이의 3원칙은 '무시,  변화, 관계'를 찾는 것.

(천재들의 생각법이자 수학으로 생각하는 방법은 '무시, 변화, 관계'라고 알려주는 깨봉수학 창업자님의 유튜브 보기) 

2. 먼저 곁가지를 다 쳐내는 '무시'를 해보면, 높이는 2로 고정되어 있으니 중요하지 않고 가로의 길이만 주목하면 됨을 알 수 있다.

3. 그 다음으로 '관계'에 주목해보자. 직사각형을 왼쪽부터 오른쪽으로 채워가면, 마지막의 길이 2는 2가지 방식으로 채울 수 있으니, 길이가 n일때 경우의 수와 길이가 n-2일때 경우의 수의 관계를 생각해볼 수 있다.

4. 그래서 cases[n]을 가로 길이가 n일때 직사각형을 채우는 경우의 수라고 하면 cases[n] = 2 x cases[n-2] 일 것 같다. 하지만 아니다.

5. 왜냐면 다음 그림처럼 되기 때문이다.

6. 마지막 길이가 1만 남았을 때가 위 그림의 오른쪽 부분이다. 왼쪽의 아래 그림은 길이가 2남았을때  직사각형이 세로가 더 길게 세워서 채우는 경우인데, 이는 길이가 1만큼 남았을 때에도 있을 수 있는 경우다. 위 그림에서 같다고 표시한 부분은 중복되는 부분이다.

7. 그러므로 다음과 같은 관계식이 성립한다.

cases[n] = cases[n-2] + cases[n-1]

8. 이건 점화식이므로 재귀나 동적프로그래밍으로 푼다. 문제의 조건에서 n은 60,000까지 허용된다. n이 커질수록 재귀로는 계산량이 감당을 못하므로, 동적프로그래밍을 이용해서 풀어야 한다.

9. 동적프로그래밍은 메모이제이션을 하며 풀었던 값들을 기억해놓고 참조해가며 푸는 방식이므로, '기억하며 풀기'이라는 말이 더 풀이법의 개념을 잘 담은 말이다.

10. 이 방식은 '기억'을 해가면서 풀기 때문에 메모리를 소모해서 공간복잡도가 올라간다는 단점이 있지만,  시간복잡도는 재귀에 비해 획기적으로 작아지는 (= Big-O가 작아진다) 장점이 있다. 

풀이코드

tip! 문제에서 설명한대로 경우의 수가 많아질 수 있으니 1,000,000,007로 나눠준 값을 결과값으로 해줘야 테스트를 통과한다. 이 풀이의 경우는 for문 안의 added가 memoization용으로 쓰는 리스트안에 누적되어 가는 결과값이니 for문을 도는 중에는 added를 계속 1,000,000,007로 나눠줘야 한다.

# dynamic programming(동적프로그래밍 사용)
# 동적프로그래밍보다 '기억하며 풀기'라는 말이 이 풀이법의 개념을 더 잘 설명하는 단어.
# 동적프로그래밍이란 말은 이 단어의 창시자가 펀딩을 받기 위해서
# 자기 딴에는 '있어 보이는것 같아서' 지은 이름이라고 합니다.
# 이렇게 개념과 이름을 동떨어지게 짓다니 이건 학습자들을 농락하는 작명입니다.

# '기억하며 풀기'라는 말은 저장해가면서(memoization), 그 값들을 참고해가면서 푼다는 뜻.
# 재귀에는 이 저장하면서 참고하는 과정이 없이 매번 다시 푼 값을 사용하는데,
# 매번 계산 다시 하니까 계산량이 많아진다 = 예전에 했던 계산도 다시 한다
# = 계산시간이 늘어난다 = Big-O 가 커진다.
# '기억하며 풀기'에는 매번 새로 계산할 필요없이 참고만 하면 되므로 계산량이 줄어듬. 
# 단지 문제는 기억을 하다보니 메모리를 쓴다는 것 = 공간복잡도가 올라간다.

def solution(n):
	tilecases = [0, 1, 2]  # memoization
	condition = 1000000007
	for i in range(2, n):
		# added = 2 x tilecases[i-1] 인것 같지만 아니다
		# added = tilecases[i-1] + tilecases[i]인 이유는 
		# 아래 그림을 보고 생각해보면 알아차릴 수 있다.
		added = tilecases[i-1] + tilecases[i]
		tilecases.append(added % condition)
	print(tilecases)
	return tilecases[-1]

print(solution(20))