Programmers / 3 x n 타일링 / Python 파이썬

2022. 8. 4. 12:38·coding test - python/Programmers
728x90
반응형

 

*문제 출처는 프로그래머스에 있습니다.

문제 제목: 3 x n 타일링 (2단계) -  DP

문제 사이트: https://school.programmers.co.kr/learn/courses/30/lessons/12902

 

프로그래머스

코드 중심의 개발자 채용. 스택 기반의 포지션 매칭. 프로그래머스의 개발자 맞춤형 프로필을 등록하고, 나와 기술 궁합이 잘 맞는 기업들을 매칭 받으세요.

programmers.co.kr

문제 설명

가로 길이가 2이고 세로의 길이가 1인 직사각형 모양의 타일이 있습니다. 이 직사각형 타일을 이용하여 세로의 길이가 3이고 가로의 길이가 n인 바닥을 가득 채우려고 합니다. 타일을 채울 때는 다음과 같이 2가지 방법이 있습니다

  • 타일을 가로로 배치 하는 경우
  • 타일을 세로로 배치 하는 경우

예를들어서 n이 8인 직사각형은 다음과 같이 채울 수 있습니다.

직사각형의 가로의 길이 n이 매개변수로 주어질 때, 이 직사각형을 채우는 방법의 수를 return 하는 solution 함수를 완성해주세요.

제한사항
  • 가로의 길이 n은 5,000이하의 자연수 입니다.
  • 경우의 수가 많아 질 수 있으므로, 경우의 수를 1,000,000,007으로 나눈 나머지를 return해주세요.
입출력 예
n result
4 11
입출력 예 설명

입출력 예 #1
다음과 같이 11가지 방법이 있다.

 

 

 

 

 

 

 

 

 

 


나의 풀이

 

n은 짝수만 와야 타일링을 할 수 있다.

n이 커질 수록 각각 기존의 타일을 이어서 만들 수도 있고, 새로운 타일을 만들 수 있다.

 

새로운 타일의 모양을 한번 보자.

각각 새로운 타일 2개씩 (위아래 반전으로) 이 만들어 질 수 있다.

 

그리고 기존의 타일과 새로운 타일을 붙여서도 타일을 만들 수 있다.

f(2) = 3

 

f(n) = f(n-2)*3 + f(n-4)*2 + ... + f(2)*2 + 2

라는 점화식을 얻을 수 있다.

여기서 x = n의 짝수 라고하자,

f(n) = f(n-1)*3 + f(n-2)*2 + ... + f(2)*2 + 2

점화식을 조금 더 보기 편하게 만들 수 있다.

 

첫번째 풀이(테스트 통과, 채점 오답)

def solution(n):
    answer = 0
    x = n // 2
    d = [0] * (x+1)
    if n % 2 == 1:
        return 0 # 홀수인 경우는 타일을 만들 수 없다.
    
    if x == 1:
        return 3
    if x == 2:
        return 11
    if x == 3:
        return 41
    
    for i in range(3,x+1):
        d[i] = (d[i-1] * 3 + sum(d[1:i-1]) * 2 + 2) % 1000000007
        
    return d[x]

 

두번째 풀이 (런타임 에러)

def solution(n):
    answer = 0
    d = [0] * (n+1)
    if n % 2 == 1:
        return 0 # 홀수인 경우는 타일을 만들 수 없다.
    if n == 0:
        return 0
    if n == 2:
        return 3
    if n == 4:
        return 11
    
    
    for i in range(6,n+1,2):
        d[i] = (d[i-2] * 3 + sum(d[0:i-2:2]) * 2 + 2) % 1000000007
        
    return d[x]

 

모범 답안

메모리를 고려해서 처음부터 메모리를 확장 시킨게 아니라 그냥 추가하는 형식으로 계산해준다.

 

def solution(n):
    d = [0,3,11]
    x = int(n/2)
    if n % 2 != 0: return 0
    if x < 3: return d[x]

    for i in range(3, x+1):
    	# d[i:j] -> d에서 d가 i인 원소부터 j-1인 원소까지의 sub-array
        d.append((3*d[i-1]+sum(d[1:i-1])*2+2)%1000000007)

    return d[x]

 


※ 알아야 할 것

- https://s2choco.tistory.com/24 블로그에서 보다 더 자세한 설명을 하고있다. 풀이 참조하시길...

- dp문제는 생각보다 메모리를 고려하면서 풀어야하는 경우가 많다..

728x90
반응형

'coding test - python > Programmers' 카테고리의 다른 글

Programmers / 스킬트리 / Python 파이썬  (0) 2022.08.11
Programmers / 이진 변환 반복하기 / Python 파이썬  (0) 2022.08.09
Programmers / 땅따먹기 / Python 파이썬  (0) 2022.08.04
Programmers / 2 x n 타일링 / Python 파이썬  (0) 2022.08.04
Programmers / 타겟 넘버 (DFS) / Python 파이썬  (0) 2022.08.03
'coding test - python/Programmers' 카테고리의 다른 글
  • Programmers / 스킬트리 / Python 파이썬
  • Programmers / 이진 변환 반복하기 / Python 파이썬
  • Programmers / 땅따먹기 / Python 파이썬
  • Programmers / 2 x n 타일링 / Python 파이썬
sillon
sillon
꾸준해지려고 합니다..
    반응형
  • sillon
    sillon coding
    sillon
  • 전체
    오늘
    어제
    • menu (614)
      • notice (2)
      • python (68)
        • 자료구조 & 알고리즘 (23)
        • 라이브러리 (19)
        • 기초 (8)
        • 자동화 (14)
        • 보안 (1)
      • coding test - python (301)
        • Programmers (166)
        • 백준 (76)
        • Code Tree (22)
        • 기본기 문제 (37)
      • coding test - C++ (5)
        • Programmers (4)
        • 백준 (1)
        • 기본기문제 (0)
      • 공부정리 (5)
        • 신호처리 시스템 (0)
        • Deep learnig & Machine lear.. (41)
        • Data Science (18)
        • Computer Vision (17)
        • NLP (40)
        • Dacon (2)
        • 모두를 위한 딥러닝 (강의 정리) (4)
        • 모두의 딥러닝 (교재 정리) (9)
        • 통계 (2)
      • HCI (23)
        • Haptics (7)
        • Graphics (11)
        • Arduino (4)
      • Project (21)
        • Web Project (1)
        • App Project (1)
        • Paper Project (1)
        • 캡스톤디자인2 (17)
        • etc (1)
      • OS (10)
        • Ubuntu (9)
        • Rasberry pi (1)
      • App & Web (9)
        • Android (7)
        • javascript (2)
      • C++ (5)
        • 기초 (5)
      • Cloud & SERVER (8)
        • Git (2)
        • Docker (1)
        • DB (4)
      • Paper (7)
        • NLP Paper review (6)
      • 데이터 분석 (0)
        • GIS (0)
      • daily (2)
        • 대학원 준비 (0)
      • 영어공부 (6)
        • job interview (2)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    백준
    Python
    소수
    programmers
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.3
sillon
Programmers / 3 x n 타일링 / Python 파이썬
상단으로

티스토리툴바