[프로그래머스] [Level 2] [다이나믹 프로그래밍] 멀리 뛰기

멀리 뛰기

코딩테스트 연습 - 멀리 뛰기

 

• 내 풀이
  • 순열을 이용해서 가능한 경우의 수 합산
    • nPr=itertools.permuatations(반복 가능한 객체(길이 n) , r)
    • nCr=itertools.combinations(n,r)
  • fail) 런타임에러

import itertools #순열조합

def solution(n):
    m=n
    k=0
    answer = 0
    arr=[1]*n
    
    while len(arr)>=n//2:
        nPr = list(set(itertools.permutations(arr, m)))
        print(nPr)
        answer+=len(nPr)
        m-=1
        
        
        if 1 not in arr:
            break
        
        arr.remove(1)
        for i in range(len(arr)):
            if arr[i]==1:
                arr[i]+=1
            if sum(arr)<n:
                continue
            else:
                break
        else:
            break
        
    return answer%1234567

 

• 내 풀이 2
  • 순열 함수 이용X → 조합의 연산방법만 이용
    • 시간 감소 , 런타임 에러는 나지 X
    • 2의 개수가 0또는 r개 이면 nCr= 1
    • 나머지는 nCr 계산방법 대로 num값 계산
  • for문에서 num을 / 대신 //로 나누었더니 통과(몫만 계산)
  • 1을 없애고 2를 하나씩 늘려가는 방식 

def solution(n):
    answer = 0
    arr=[1]*n
    num=1
    while len(arr)>=n//2:
        c=arr.count(2)
        if c==0 or c==len(arr):
            answer+=1
        else:
            for i in range(1,c+1):
                num*=len(arr)+1-i
                num//=i 

            answer+=num
            num=1
        
        if 1 not in arr:
            break
        
        arr.remove(1)
        for i in range(len(arr)):
            if arr[i]==1:
                arr[i]+=1
            if sum(arr)<n:
                continue
            elif sum(arr)==n:
                break
        else:
            break
        
    return answer%1234567

print(solution(4))
print(solution(3))
print(solution(10))
#결과
5
3
89

 

 

• 다른 사람 풀이
  • 다이나믹 프로그래밍(DP) 풀이 방법
  • 계단을 1,2칸만 올라갈 수 있으므로 3칸을 오를 때는 1,2칸을 오르는 경우의 수를 합해주면 되고,
  • 점화식으로 나타내면 f(n)=f(n-1)+f(n-2) 피보나치 수열과 같다

def solution(n):
    answer = 0
    dp = [0]*(n+1)
    dp[0], dp[1] = 1, 1

    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]

    answer = dp[n] % 1234567
    return answer