[SWEA][D2] 파이썬 SW문제해결 기본 - Stack1-종이붙이기 D2

문제 출처 HOME > Learn Course > Programming Intermediate > 파이썬 SW문제해결 기본 - Stack1 https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDN86AAXw5UW6&subjectId=AWOVHzyqqe8DFAWg

학습목표

1. 스택 자료구조의 개념과 기본 연산을 설명할 수 있다.
2. 스택을 응용한 괄호 검사 알고리즘과 함수 호출과 재귀 호출에 대하여 설명할 수 있다.
3. 재귀 호출의 중복을 보완하는 메모이제이션에 대하여 설명할 수 있다.
4. 동적 계획법 알고리즘의 개념에 대하여 설명할 수 있다.
5. 스택을 이용한 깊이 우선 탐색 알고리즘에 대하여 설명할 수 있다.

 

 

---

4869. [파이썬 S/W 문제해결 기본] 4일차 - 종이붙이기 D2

4869. [파이썬 S/W 문제해결 기본] 4일차 - 종이붙이기
 
def paper(n):
    if n==1:
        return 1
    elif n==2:
        return 3
    return paper(n-1) + (2*paper(n-2))
 
T= int(input())
for t in range(1,T+1):
    n= int(input())
    cnt = paper(n//10)
    print("#{} {}".format(t,cnt))
 

 N이 주어졌을 때, 종이를 붙이는 모든 경우를 찾기는

( 테이프로 만든 표시한 영역을 몇 개나 만들어야 되는지) 

종이붙이기의 점화식(규칙성)을 알아야 풀 수 있는 문제...

입력 값 n은 10배로 나오는데 편의를 위해 n//10 으로 해서 풀었습니다. (10 => 1 20 =>2)

결론 paper(n) = paper(n-1) + 2*paper(n-2)

 

paper(n) = 1*paper(n-1) + 2*paper(n-2)

 

paper(n) 은 = paper(n-1) 케이스와  paper(n-2) 케이스에서 발전된 종이가 추가된 다음 단계인데, 

n-1 였던 것에서 1번 네모를 추가하는데 이 디자인은 1개 뿐이여서, 1*paper(n-1)

paper(n-1)의 갯수에서 그냥 크기만 한칸 커진거지 갯수는 paper(n-1)의 갯수(경우의 수) 와 똑같다. 

n-2 였던 것에서 1번네모 세운디자인1개, 1번네모 누운디자인1개, 2번네모 한번쓴 디자인 1개

이때, 3*paper(n-2) 이 아니라 2* paper(n-2)이다. 세운 디자인은 이미 1*paper(n-1) 랑 같아서

2가지 경우만 고려하기 떄문이ㅏㄷ...아오, ..

 

 

참고) 점화식이란...

 

 

점화식은 패턴 규칙성을 찾아 그걸 식으로 표현한 것이라고 본다.

 

관련영상을 좀 봤었는데 다시 찾아보는 중...