[Programmers Lv 3/C++] 멀리 뛰기

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

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

 

문제 설명

효진이는 멀리 뛰기를 연습하고 있습니다. 효진이는 한번에 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	result
4	5
3	3

입출력 예 설명

입출력 예 #1
위에서 설명한 내용과 같습니다.

입출력 예 #2
(2칸, 1칸)
(1칸, 2칸)
(1칸, 1칸, 1칸)
총 3가지 방법으로 멀리 뛸 수 있습니다.

 

풀이 방법

다이나믹 프로그래밍이 딱 떠오르는 문제이다.

예를 들어

- 1로 가는 방법은 1가지이다. (1)

- 2로 가는 방법은 2가지이다. (1,1 / 2)

- 3으로 가는 방법은 3가지이다. (1,1,1 / 2,1 / 1,2)

 

여기서만 봐도 규칙을 알 수 있는데 3으로 가는 방법은 1로 가는 방법 + 2칸 이동, 2로 가는방법 + 1칸 이동과 같다.

즉 여기서 점화식을 만들면

dp[n] = dp[n - 1] + dp[n - 2]가 되는 것이다.

 

 

 

 

소스 코드는 다음과 같다.

// Programmers Level 3. 멀리 뛰기
// https://programmers.co.kr/learn/courses/30/lessons/12914
// Written By Rylah
// Written Date : 2022.03.01
 
#include <bits/stdc++.h>
using namespace std;
 
long long dp[2005];
long long solution(int n) {
    dp[1] = 1;
    dp[2] = 2;
    for (int i = 3; i <= n; i++)
    {
        dp[i] = (dp[i - 1] + dp[i - 2]) % 1234567;
    }
 
    return dp[n];
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    long long n;
    n = 4;
    cout << solution(n) << "\n";
    n = 3;
    cout << solution(n) << "\n";
 
    return 0;
}

입력 범위가 2000까지이므로 넉넉하게 2005까지 주고 해결 할 수도 있다.

하지만 우리는 피보나치 수열을 해봤듯이 메모리를 줄일 수 있을 것이다.

 

메모리를 줄여보자

// Programmers Level 3. 멀리 뛰기
// https://programmers.co.kr/learn/courses/30/lessons/12914
// Written By Rylah
// Written Date : 2022.03.01
 
#include <bits/stdc++.h>
using namespace std;
 
long long dp[4];
long long solution(int n) {
    dp[1] = 1;
    dp[2] = 2;
    
    if (n <= 2)
        return dp[n];
 
    for (int i = 3; i <= n; i++)
    {
        dp[3] = (dp[1] + dp[2]) % 1234567;
        dp[1] = dp[2];
        dp[2] = dp[3];
    }
 
    return dp[3];
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    long long n;
    n = 4;
    cout << solution(n) << "\n";
    n = 3;
    cout << solution(n) << "\n";
 
    return 0;
}

 

처음 결과

정확성 테스트

테스트 1 〉	통과 (0.01ms, 4.1MB)
테스트 2 〉	통과 (0.01ms, 4.17MB)
테스트 3 〉	통과 (0.01ms, 4.09MB)
테스트 4 〉	통과 (0.01ms, 4.16MB)
테스트 5 〉	통과 (0.01ms, 3.65MB)
테스트 6 〉	통과 (0.01ms, 3.71MB)
테스트 7 〉	통과 (0.01ms, 3.57MB)
테스트 8 〉	통과 (0.01ms, 4.16MB)
테스트 9 〉	통과 (0.01ms, 4.15MB)
테스트 10 〉	통과 (0.01ms, 4.1MB)
테스트 11 〉	통과 (0.02ms, 4.18MB)
테스트 12 〉	통과 (0.02ms, 4.1MB)
테스트 13 〉	통과 (0.02ms, 4.18MB)
테스트 14 〉	통과 (0.02ms, 4.17MB)
테스트 15 〉	통과 (0.02ms, 4.1MB)
테스트 16 〉	통과 (0.02ms, 3.69MB)

채점 결과

정확성: 100.0

합계: 100.0 / 100.0

 

메모리 줄인 결과

채점을 시작합니다.

정확성 테스트

테스트 1 〉	통과 (0.01ms, 4.14MB)
테스트 2 〉	통과 (0.01ms, 4.16MB)
테스트 3 〉	통과 (0.01ms, 4.15MB)
테스트 4 〉	통과 (0.01ms, 4.16MB)
테스트 5 〉	통과 (0.01ms, 4.17MB)
테스트 6 〉	통과 (0.01ms, 4.14MB)
테스트 7 〉	통과 (0.01ms, 4.14MB)
테스트 8 〉	통과 (0.01ms, 3.58MB)
테스트 9 〉	통과 (0.01ms, 4.11MB)
테스트 10 〉	통과 (0.01ms, 4.14MB)
테스트 11 〉	통과 (0.01ms, 4.14MB)
테스트 12 〉	통과 (0.01ms, 4.08MB)
테스트 13 〉	통과 (0.01ms, 3.73MB)
테스트 14 〉	통과 (0.01ms, 4.17MB)
테스트 15 〉	통과 (0.01ms, 4.15MB)
테스트 16 〉	통과 (0.01ms, 4.15MB)

채점 결과

정확성: 100.0

합계: 100.0 / 100.0