Programmers] 멀리 뛰기

📌 파이썬 으로 풀이

 

📌 문제 링크 :

프로그래머스

 

📌 문제 설명 :

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 1칸, 또는 2칸을 뛸 수 있습니다.

칸이 총 4개 있을 때, 효진이는
(1칸, 1칸, 1칸, 1칸)
(1칸, 2칸, 1칸)
(1칸, 1칸, 2칸)
(2칸, 1칸, 1칸)
(2칸, 2칸)
의 5가지 방법으로 맨 끝 칸에 도달할 수 있습니다. 멀리뛰기에 사용될 칸의 수 n이 주어질 때, 효진이가 끝에 도달하는 방법이 몇 가지인지 알아내, 여기에 1234567를 나눈 나머지를 리턴하는 함수, solution을 완성하세요. 예를 들어 4가 입력된다면, 5를 return하면 됩니다.

 

📌 제한 사항

• n은 1 이상, 2000 이하인 정수입니다.

 

📌 입출력 예

---

추측) 

n의 개수를 일단 2로 나눈 몫을 구한다 .

몫이 0이면 n는 1밖에 없으므로 cnt에 1을 넣어 반환

몫이 0이 아니면 몫의 길이 만큼 for문을 돌린다. 

for문의 i를 2칸의 개수로 보고 n에서 2*i를 뺀걸 1칸의 개수로 본다.

그리고 그 턴에서의 2칸의 개수와 1칸의 개수로 중복있는 순열의 경우 수를 구해 최종 값에 +대입한다. 

모든 for문을 돌면서 경우의 수를 누적하고 마지막으로 리턴한다. 

 

소스코드) 

* 1차) 실패 : 정확도 37.5점

def solution(n):
    answer = 0
    num = int(n/2)

    if num == 0 :
        return 1

    for i in range(0, num + 1):
        two_num = i
        one_num = n-(2*i)

        if two_num == 0 or one_num == 0 :
            answer += 1
            continue

        top_num = factorial(two_num+one_num, 1)
        b_case = factorial(two_num, 1)
        c_case = factorial(one_num, 1)

        case_num = int(top_num / (b_case * c_case))
        answer += case_num

    return answer % 1234567

def factorial(num, result):
    if num == 0 :
        return result

    result *= num
    num -= 1
    return factorial(num, result)

* 2차) 성공 : 다른 사람들이 DP방식 적용했다는 거 알고 공부 후 적용

def solution(n):
    n_list = [0] * n

    for i in range(n):
        if i == 0 :
            n_list[i] = 1
        elif i == 1 :
            n_list[i] = 2
        else:
            n_list[i] = n_list[i-1] + n_list[i-2]

    return n_list[n-1] % 1234567

 

 

리뷰) 

 

1차)

찾아도 어려운 길로 찾아가고 있었구나 싶다 나도 참.. 순열로 풀라고 했는데

나름 회심의 재귀함수로 팩토리얼 구현까지 했는데 🤣

 

더이상 해결이 안되서 질문하기 글들을 봤다

그 중 똑같이 순열로 풀어본 사람이 테스트 예시로 2000을 넣어보라는 글이 있었다.

아... 이런 ㅋㅋㅋ오버플로우!

이런 오류가 날 수 있는 상황도 생각했어야지!  

 

그럼 다른 사람들은 이 문제를 어떻게 접근했을 까하고 보니 DP로 푸는 걸 보게 됬다.

일단 왜 이게 DP일까? 싶어서 경우의 수를 차례차례 따져봤다. 

n	경우의  수
1	(1칸)	1
2	(1칸,1칸), (2칸)	2
3	(1칸,1칸,1칸), (2칸, 1칸), (1칸, 2칸)	3	1+2
4	(1칸,1칸,1칸,1칸),(2칸,1칸,1칸), (1칸, 2칸, 1칸), (2칸,1칸,1칸), (2칸, 2칸)	5	2+3
5	(1칸,1칸,1칸,1칸,1칸),(2칸,1칸,1칸,1칸), (1칸,2칸,1칸,1칸),(1칸,1칸,2칸,1칸),(1칸,1칸,1칸,2칸), (2칸, 2칸,1칸),(2칸,1칸,2칸), (1칸,2칸,2칸)	8	3+5
			피보나치 수열 형태로 나온다

아, 피보나치! 

 

그래서 바로 적용!

일단 앞의 수들을 다 미리 저장해 두려면 n개 만큼 0이 든 배열을 만든다.

n_list = [0] * n

n 만큼 for문을 돌릴건데 n이 1과 2일 때는 앞에 2개의 수가 없으므로 그냥 각각 1과 2을 인덱스에 대입한다. 

3 이상 부터는 그 인덱스의 전 값과 바로 전전 값을 더해 대입한다. 

n 만큼 for문을 돌아 배열을 완성하면 n-1의 인덱스 값을 가져와 리턴한다. 

 

그러면 최종적으로 경우의 수를 구하게 된다! 

 

휴 아직도 경험치가 많이 부족하다. 문제 파악을 빠르고 정확하게 할 수 있도록 많이 풀어보자.