[프로그래머스] Level 2_멀리뛰기(연습문제)

📌문제 유형

연습문제

 

📌문제

프로그래머스

 

📌나의 문제풀이

1차 시도(93.7, 1개 런타임 에러)

from  collections import deque

def factorial(num):
    if num == 0:
        return 1
    a = 1
    for i in range(1,num+1):
        a *= i
    return a

def solution(n):
    answer = 1
    list_ = [1 for i in range(n)]
    list_ = deque(list_)
    stop = (len(list_)//2) + (len(list_)%2)
    
    while True:
        list_.popleft()
        list_.popleft()
        list_.append(2)
        
        count_2 = list_.count(2)
        count_1 = list_.count(1)
        answer += (factorial(len(list_)) // (factorial(count_2) * factorial(count_1)))
        
        if len(list_) == stop:
            break
                   
    return answer % 1234567

2차 시도(통과)

 - factorial(num) : 팩토리얼 구현

 - list_의 초기값으로 다 1 넣어주기

• deque로 변경

 - stop : while문 멈출 조건, list_가 구성할 수 있는 최소의 개수

 - 1차 시도는 while True, 2차 시도는 조건문

• while 조건을 먼저 명시해야 런타임 에러에 안 걸림
• popleft 이용하여 1을 2번 빼주기 -> append로 2 넣기
• list_의 1의 개수, 2의 개수 세기 -> factorial로 answer 계산

from  collections import deque

# 팩토리얼 구현
def factorial(num):
    if num == 0:
        return 1
    a = 1
    for i in range(1,num+1):
        a *= i
    return a

def solution(n):
    answer = 1
    list_ = [1 for i in range(n)]
    list_ = deque(list_)
    stop = (len(list_)//2) + (len(list_)%2)
    
    while len(list_) > stop:
        list_.popleft()
        list_.popleft()
        list_.append(2)
        
        count_2 = list_.count(2)
        count_1 = list_.count(1)
        answer += (factorial(len(list_)) // (factorial(count_2) * factorial(count_1)))
     
    return answer % 1234567

 

📌다른 사람들의 풀이

1) DP 이용

n이 1일 때부터 5일 때까지 나올 수 있는 경우의 수를 차분히 count 해보면 피보나치의 수열 규칙이다.

출처 : https://m.blog.naver.com/chanmuzi/222843477118

멀리 뛰기 [Level 2](Python)

def solution(n):
    # n=1 일 때 1 반환
    if n == 1: return 1
    else: 
        # DP 테이블 초기화
        dp = [0] * (n+1)
        dp[1] = 1
        dp[2] = 2

        # 점화식 적용, 숫자가 커지는 것을 방지하기 위해
        # 계속해서 나머지 연산자 활용하기
        for i in range(3,n+1):
            dp[i] = (dp[i-2] + dp[i-1]) % 1234567

        # DP 테이블 마지막 값 반환
        return dp[-1]

 

📌리뷰

 - while에 조건 걸어서 런타임 줄이기

 - deque 앞에서 꺼내는건 popleft 사용(pop은 뒤에서 꺼내는 것)

 - 개수 규칙으로 DP 사용 가능