[프로그래머스] 멀리 뛰기

https://programmers.co.kr/learn/courses/30/lessons/12914

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

 

조합, 파스칼의 삼각형을 이용하여 풀었다. 4를 예로 들면, 2칸을 기준으로

 

2칸을 뛴 적이 0번일 때 : 4C0

1번일 때 : 3C1

2번일 때 : 2C2

answer = 4C0(1) + 3C1(3) + 2C2(1) = 5 이다.

 

파스칼의 삼각형의 원리를 이용하여 2차원 배열에 각 조합 값을 담아(dp[i][j] = iCj) 필요한 값을 꺼내어 answer 을 반환하였다.

 

def solution(n):
    answer = 0
    dp = [[1, 1]]
    
    for i in range(1, n):
        dp.append([1])
        
        for j in range(i):
            dp[i].append((dp[i-1][j] + dp[i-1][j+1]) % 1234567)
        
        dp[i].append(1)
    
    for i in range(n // 2 + 1):
        answer += dp[n-i-1][i]
        answer %= 1234567

    return answer
    
    print(solution(4)) # 5