동적계획법 - 멀리 뛰기

이번문제는, 두가지로 풀 수 있는 문제입니다.(동적계획법, 기타)

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

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

조금 오래된 문제입니다.

 

해당 문제는, 주어진 거리가 있을때

 

해당 거리를 1보 또는 2보의 조합으로 갈 수 있는 모든 경우의 수를 구하는 문제입니다.

 

해당문제는 잘 동적계획법 접근과, 전역탐색 접근방법이 존재합니다.

 

1. 동적계획법

결론부터 말하면, 해당 문제는 피보나치수열과 정확이 동일합니다.

 

문제는 이게 왜 피보나치 수열과 정확히 동일할까? 입니다.

 

n = 1일때 --> (1)

n = 2일때 --> (1,1), (2)

이제, n=3일때를 생각해보면

n=1에서 2칸을 움직이는 경우 + n=2에서 1칸을 움직이는 경우

가 성립됩니다.[(1)+(2), (1,1)+(1), (2)+(1)]

 

그렇기 때문에, 해당 문제의 풀이법이 정확히 피보나치 수열 문제와 일치하는것을 알 수 있습니다 :)

 

동적계획법을 사용한 풀이 코드입니다.

def solution(n):
    answer = 0
    if n == 1:
        return 1
    elif n == 2:
        return 2
    temp1 = 1
    temp2 = 1    
    for i in range(2,n+1):
        answer = temp1%1234567 + temp2%1234567        
        temp1 = temp2
        temp2 = answer
    return answer%1234567

 

 

2. 전역탐색

전역탐색은, 주어진 N을 1과 2의 배수로 나누는 방법 입니다.

 

예를들어, 11의 경우

(1, 10), (3, 8), (5, 6), (7, 4), (9, 2), (11,0)

총 6개의 조합이 가능한 것을 알 수 있습니다.

 

이때, 위 경우의 수 마다 가능한 조합의 개수를 Factorial을 사용해서 계산해줍니다.

(6!/(1!*5!), 7!/(3!*4!), 8!/(5!*3!), 9!/(7!*2!), 10!/(9!*1!), 11!/11!)

 

이제 계산된 모든 경우의 수를 Sum 해주면, 전역탐색으로 구한 모든 경우의 수의 개수를

 

구할수가 있게됩니다 :)

 

팩토리얼을 사용한 풀이 코드

(해당 코드는 오버플로우 문제때문인지, 테스트 케이스 7번부터는 오답이 나옵니다 ㅠ)

def factorial(num):
    temp_val = 1
    for i in range(num):
        temp_val *= (i+1)
    return temp_val

#각 경우의 수에 대해서 Factorial 계산으로 경우의수를 계산
def case(temp_list):    
    temp_val = 1    
    for i in range(max(temp_list),sum(temp_list)):
        temp_val *= (i)+1    
    return temp_val/factorial(min(temp_list))
        

def solution(n):
    if n == 1:
        return 1
    elif n == 2:
        return 2
    answer = 0
    temp = []
    #1만있거나 2만있는 Case를 제외하고, Factorial 계산
    for i in range(n):
        if (n-i)%2==0 and i!=0 and (n-i)!=0:
            temp.append([i, (n-i)//2])    
    temp = [case(i) for i in temp]
    answer = sum(temp)
    #마지막에 n이 짝/홀수냐에 따라 1만있거나, 2만있는 Case를 고려해줍니다.
    if n%2 == 0:
        return (answer + 2)%1234567
    else:
        return (answer + 1)%1234567