Cos Pro 1급 - 샘플 문제 5차 1번 (계단 오르는 경우의 수-동적계획법)

문제 지문 #1

계단 n칸을 올라가는 방법의 수를 구하려고 합니다. 계단은 한 번에 1계단, 2계단, 3계단씩 오를 수 있습니다.
예를 들어, 계단 3칸을 오르는 방법은 다음과 같이 4가지가 있습니다.

1. 1계단 + 1계단 + 1계단
2. 1계단 + 2계단
3. 2계단 + 1계단
4. 3계단

계단 수 n이 매개변수로 주어질 때, 계단을 오르는 경우의 수를 return 하도록 solution 메서드를 작성하려 합니다. 빈칸을 채워 전체 코드를 완성해주세요.

---

#####매개변수 설명

계단 수 n이 solution 메소드의 매개변수로 주어집니다.

• n은 3 이상 30 이하인 정수입니다.

---

#####return 값 설명

계단을 오르는 경우의 수를 return 합니다.

---

#####입출력 예

n	return
3	4
4	7

#####입출력 예 설명
예시 #1
문제에 나온 예와 같습니다.

예시 #2
계단 4칸을 오르는 방법은 다음과 같이 7가지가 있습니다.

```

1. 1계단 + 1계단 + 1계단 + 1계단
2. 1계단 + 1계단 + 2계단
3. 1계단 + 2계단 + 1계단
4. 2계단 + 1계단 + 1계단
5. 1계단 + 3계단
6. 3계단 + 1계단
7. 2계단 + 2계단

 

728x90

 

혼자 풀이

빈 칸 채우기 문제입니다. 동적 계획법을 이용해서 푸는 문제입니다.
동적 계획법이란, 처음 주어진 문제를 더 작은 문제들로 나눈 뒤 작은 문제들의 답을 계산하고 이 계산 결과를 재활용하는 방식을 의미합니다.

- 이 문제에서 4계단을 오르는 방법은 아래와 같습니다. 

1계단 오른 뒤 3계단을 오르기	3계단을 오르는 경우의 수 4가지
2계단 오른 뒤 2계단을 오르기	2계단을 오르는 경우의 수 2가지
3계단 오른 뒤 1계단을 오르기	1계단을 오르는 경우의 수 1가지

4가지+2가지+1가지 = 총 7가지

- 이 문제에서 5계단을 오르는 방법은 아래와 같습니다.

1계단 오른 뒤 4계단을 오르기	4계단을 오르는 경우의 수 7가지
2계단 오른 뒤 3계단을 오르기	3계단을 오르는 경우의 수 4가지
3계단 오른 뒤 2계단을 오르기	2계단을 오르는 경우의 수 2가지

 7가지+4가지+2가지 = 총 13가지

즉, n계단 오르는 경우의 수는 아래와 같습니다.

n계단 오르는 경우의 수 = n-1계단 오르는 경우의 수 + n-2계단 오르는 경우의 수 + n-3계단 오르는 경우의 수

※ 4계단을 오른 뒤 1계단을 오르는 경우는 왜 없냐 할 수 있는데요.
4계단을 오르는 방법은 처음에 1,2,3계단을 오르는 방법을 포함하기 때문에 중복이되므로  제외해야 합니다.

혼자 풀이에서 답을 틀렸기 때문에 정답으로 넘어갑니다.

정답

저는 계단 오르는 경우의 수가 1  > 2 > 4 > 7 각 경우의 수의 차이가 1,2,3이기 때문에 
n계단 오르는 경우의 수 = n-1계단 오르는 경우의 수 + n-1 로 생각했습니다(주석 처리한. 이렇게 해도 main() 함수에 주어진 문제는 정답으로 나왔습니다. 하지만, n이 5 이상이 되면 틀린 답을 내기 때문에 위에 설명한 것과 같이 코드를 짜야합니다.

 

class Main {
    public int solution(int n) {
        int answer = 0;

        int[] steps = new int[n+1];
        steps[1] = 1;
        steps[2] = 2;
        steps[3] = 4;
        for(int i = 4; i <= n; i++)
            // steps[i] = @@@;            
            // steps[i] = steps[i-1]+i-1; //오답입니다.
            steps[i] = steps[i-1]+steps[i-2]+steps[i-3]; //정답입니다
        answer = steps[n];
        return answer;
    }
    
    // 아래는 테스트케이스 출력을 해보기 위한 main 메소드입니다.
    public static void main(String[] args) {
    	Main sol = new Main();
    	int n1 = 3;
    	int ret1 = sol.solution(n1);

    	// [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
    	System.out.println("solution 메소드의 반환 값은 " + ret1 + " 입니다.");

    	int n2 = 4;
    	int ret2 = sol.solution(n2);

    	// [실행] 버튼을 누르면 출력 값을 볼 수 있습니다.
    	System.out.println("solution 메소드의 반환 값은 " + ret2 + " 입니다.");
    }
}

 

실습은 아래 참고

2022.10.25 - [Programming/Cos Pro 1급] - Cos Pro 1급 공부 사이트 추천 - 구름 에듀(https://edu.goorm.io/)

Cos Pro 1급 공부 사이트 추천 - 구름에듀(https://edu.goorm.io/)