2. codeup 2834 : [상태 정의를 통한 탐색] 계단 오르기 3-1 & 2836 : [상태 정의를 통한 탐색] 계단 오르기 6-1 문제 해결

코드업 2834번을 해결해 봅시다!

출처<코드업 사이트>

 

문제는 위와 같은데요. 

코딩을 하기에 앞서 먼저 어떤식으로 알고리즘을 설계해야할지에 대해 생각해 보겠습니다.

이 문제에서 문제를 해결할때 생각해야할 두개의 데이터는 몇번째 계단을 밟았는지와 몇번째로 밟은 계단인지 입니다.

n번째 계단을 밟기 위해서는 n-1번째 계단에서 올라오거나 n-2번째 계단에서 올라오는 방법이 있는데 그 둘은 동시에 일어나는 사건이 아니기 때문에 경우의 수를 더해주어야 합니다. 

저는 이 두 데이터를 하나의 배열로 묶어서 경우의 수를 계산하기로 하였습니다. 우선 출발하는 경우의 수는 당연히 1개 겠지요. 그리고 첫번째 칸에 올라가는 경우의 수는 출발칸에서 가는 경우의 수밖에 없습니다. 그래서 이 두가지 경우는 예외로 처리하고 나머지 계단에서는 위의 알고리즘처럼 1계단 전과 2계단전의 경우의 수를 더해줍니다. 물론 계단을 오른 횟수는 하나 적은 경우의 경우의 수를 더해주어야 겠죠. 

#include<stdio.h>

int a[50][50];      //데이터를 저장하는 배열 선언

//경우의 수를 더하는 함수
int stair(int i,int j){  
    if(i==1) a[i][j]+=a[0][j-1];  //첫번째 계단 예외 처리
    else a[i][j]=a[i-1][j-1]+a[i-2][j-1]; //경우의 수 덧셈
    
    if(j<=i) return stair(i,j+1); //이동하는 횟수를 1씩 증가시킴(계단의 번호보다 작을때까지만)
}
int main(){
    int n, k;    //변수 선언
    scanf("%d %d",&n,&k); //변수 입력
    a[0][1]=1;  //출발칸의 경우의 수
    for(int i=1;i<=n;i++){    //계단 n개
    	stair(i,1);    
	}
	int ans=0; //두 사람의 총 경우의 수를 저장하는 변수
	
	for(int i=0;i<=k;i++)ans+=a[n][i]*a[n][i]; //두 사람이므로 경우의 수의 제곱

    printf("%d",ans); //정답 출력
}

위의 알고리즘을 따라 C코드로 구현해 보았습니다. 함수를 사용하는 편이 코드를 보고 해석하는데에 편리할 것 같아 주요 행동인 경우의 수를 더하는 부분을 함수로 표현하였습니다. 또 위에서 언급하지 않은 내용이 있는데 이 문제는 두 명이 계단을 오르는 문제이기 때문에 한명의 경우의 수에 제곱을 해주어야 합니다. 한 명이 a개의 행동을 했다고 가정할때 나머지 한명은 행동 1개마다 각각 a개의 행동을 하는 경우의 수가 생기기 때문입니다. 

 

 

여기서 끝난 줄 알았지만 한 문제만 더 해결해 봅시다!!

출처<코드업 사이트>

사실 전 문제와 별 다를게 없는것처럼 느껴집니다. 위의 문제에서 사람만 한명이 되고 계단이 3칸 전부터 올 수 있고 한칸이 금지되는 조건이 추가가 되었네요. 

 

사람이 한명이 된 부분은 기존에 결과값을 제곱했던 코드를 제곱만 풀어주면 될것 같네요. 

3칸씩 올라올 수 있어진 부분은 점화식을 약간 수정해주면 될것 같고요.

그런데 한칸이 금지된 부분은 어떻게 구현해야 할까요??

 

아주 간단합니다!

 

함수에 금지된 칸에 해당하는 인자를 추가로 전달해주고 그 계단을 밟는 경우는 경우의 수 계산에서 배제 해주면 됩니다!

#include<stdio.h>

int a[50][50];     //데이터를 저장하는 배열 선언

//경우의 수를 더하는 함수
int stair(int i,int j,int m){  
	if(i!=m){   //m번째 계단 배제
	
    if(i==1) a[i][j]+=a[0][j-1]; //첫번째 계단 예외 처리
	else if(i==2) a[i][j]+=a[1][j-1]+a[0][j-1]; //두번째 계단 예외 처리
	else a[i][j]=a[i-1][j-1]+a[i-2][j-1]+a[i-3][j-1]; //경우의 수 덧셈

    if(j<=i) return stair(i,j+1,m);  //이동하는 횟수를 1씩 증가시킴(계단의 번호보다 작을때까지만)

}
}
int main(){
    int n, k, m; //변수 선언
    scanf("%d %d %d",&n,&m,&k); //변수 입력
    a[0][1]=1; //출발칸의 경우의 수
    for(int i=1;i<=n;i++){  //계단 n개
    	stair(i,1,m);
	}
	int ans=0; //두 사람의 총 경우의 수를 저장하는 변수
	
	for(int i=0;i<=k;i++) ans+=a[n][i]; //경우의 수 더하기

    printf("%d",ans); //정답 출력
}

코드로 구현하면 이렇게 됩니다. 위 문제의 코드와 별로 달라진 점이 없죠. 금지된 계단을 m이라는 변수에 입력받고 함수에 m번째 계단일때는 경우의 수 계산이 이루어지지 않도록 조건문을 씌워줍니다. 또한 앞 문제와 다르게 3칸씩도 오를 수 있으니 그 부분을 점화식에 추가해 주고 마지막 결과값 부분을 제곱을 풀어줌으로써 사람을 한명으로 바꿔주었습니다.

 

 

이런 코드를 물론 한번에 쓸 수 있지는 않았죠. 여러 오류와 맞닥드렸지만 제일 시간을 오래 쓴것 같은 오류를 말하고 싶네요.

 

 if(j<=i) return stair(i,j+1);

함수의 이 부분에서 처음에는 조건문을 넣지 않고 컴파일 하였더니 컴파일이 오래걸리고 나서 아무값도 나오지 않는 현상이 발생하더라고요. 어디서 오류가 발생했을까를 살피며 다른곳을 헤집다가 컴파일이 오래걸리는것은 너무 많은 연산이 수행되고 있어서가 아닐까?라는 생각을 하게 됩니다. 그래서 범위에 제한을 두어야겠다! 하고 이 줄에 범위의 제한을 주니 해결이 되더라고요. 매우 뿌듯했습니다!

 

 

 

지금까지 부족한 제 첫 코딩 게시물을 읽어주셔서 감사합니다! 이런걸 해본적이 없어서 말이 자연스럽지 못하지만 앞으로 게시글을 쓰면서 점점 성장해 나가겠습니다. 감사합니다! 궁금하신점이 있다면 댓글로~!