[C++] 멀리 뛰기

 

 

멀리 뛰기

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

 

 

 

 

입출력 예

4	5
3	3

 

 

 

1칸 또는 2칸을 갈 수 있기 때문에 도착점에 도착하는 경우가 두가지가 있을 수 있습니다.

 

예를들어 6번째 칸에 도착하기 위해서는 첫번째 5번칸에서 1칸이동하는경우, 두번째 4번칸에서 2칸이동하는경우 이렇게 두가지입니다.

 

다시 5번째 칸에 도착하는 경우와 4번째 칸에 도착하는경우 ...  이렇게 1칸 2칸까지 줄이다보면 피보나치 수열을 생각할 수 있습니다.

 

 

 

 

 

 

배열에 피보나치 수열 결과를 저장하는 방법으로 풀이하였습니다.

 

#include <string>
#include <vector>

using namespace std;

long long a[2001] = {0, 1, 2, };


long long solution(int n) {
    long long answer = 0;
    for(int i = 1; i < n + 1; i++){
        if(i>2) a[i] = (a[i-1]+ a[i-2]) % 1234567;
    }
    return a[n];
}

 

 

 

 

 

+

 

2022년 알고리즘 해석 및 설계  과제2번

 

 

프로그래밍 과제 2

N단의 계단이 있고, 한번에 계단을 한 단 또는 두 단을 올라갈 수 있다고 하자. 

최대 두 군데의 계단에는 장애물이 있어서 올라갈 수 없다. 

이 때 N단까지 올라가는 서로 다른 방법의 수를 구하는 프로그램을 작성하시오. 

 

입력 

표준입력으로 세 정수 N A B가 주어진다. N은 계단의 단수로, 1 이상 30 이하이다. 

A와 B는 장애물이 있는 계단의 위치이다. A와 B는 0 이상 N 이하인 수이며, A와 B가 같을 수 있다. 

A, B 값이 0이라면, 이는 장애물이 없다는 뜻이다. 예를 들어 N, A, B가 3, 0, 1이라고 주어지면 

총 3단의 계단이 있고, 장애물은 1단에만 있다. 조금 더 생각해보면 N, A, B가 3, 1, 0으로 주어져도

같다는 것을 알 수 있다. 

 

출력

표준출력으로 하나의 정수를 출력한다. N단까지 오는 서로 다른 방법의 수이다. 

 

힌트 

만약 1단, 2단을 올라갈 수 있다면, 1단에 올라가는 방법은 한 가지, 2단에 올라가는 방법은 두 가지이다. 

 

예제 입력 1

3 0 1

예제 출력 1

1

 

예제 입력 2

7 2 4

예제 출력 2

2

 

 

 

 

'멀리 뛰기' 프로그래머스 문제풀이 원리를 장애물이 있는 계단 전까지로 적용

 

#include <iostream>

using namespace std;

int stair(int num){

	if (num == 1) return 1;
	else if (num == 2) return 2;
	else if (num == 0) return 1;
	else if (num == -1) return 1;

	return stair(num - 2) + stair(num - 1);
}

int main(){

	int N, A, B;

	cin >> N >> A >> B;

	if (N >= 1 && N <= 30) { 
		if (A == 0 && B == 0)
			cout << stair(N) << endl;

		else if (A == 0 && B != 0) {
			if (N == B)
				cout << "장애물은 마지막 계단에 올 수 없습니다." << endl;

			else if (B * 2 == N)
				cout << stair(N - B - 1) * stair(N - B - 1) << endl;
			else
				cout << stair(B - 1) * stair(N - B - 1) << endl;
		}
				

		else if (A != 0 && B == 0) {
			if (N == A)
				cout << "장애물은 마지막 계단에 올 수 없습니다." << endl;

			else if (A * 2 == N)
				cout << stair(N - A - 1) * stair(N - A - 1) << endl;
			else
				cout << stair(A - 1) * stair(N - A - 1) << endl;
		}

				
		else {
			if (N == A || N == B)
				cout << "장애물은 마지막 계단에 올 수 없습니다." << endl;
			else if(B - A == 1)
				cout << "장애물은 2칸 연속 올 수 없습니다." << endl;

			else {
				if (A > B) {
					int tmp;
					tmp = A;
					A = B;
					B = tmp;
				}

				if (B - A == 2)
					cout << stair(A - 1) * stair(N - B - 1) << endl;
				else if (B - A == 3)
					cout << stair(A - 2) * stair(N - B - 1) << endl;

				else {
					if (A == 2 || A == 1)
						cout << stair(B - A - 2) * stair(N - B - 1) << endl;
					else
						cout << stair(A - 1) * stair(B - A - 2) * stair(N - B - 1) << endl;
				}	
			}
		}		
	}
	else {
		cout << "1이상 30 이하의 N을 입력하시오." << endl;
	}

	return 0;
}