CodeUp[Q_2029] : 숫자 끼워 넣기

1. 문제

https://codeup.kr/problem.php?id=2029

숫자 끼워 넣기

[출처 : 코드업(https://codeup.kr/)]

이번 문제는 주어진 조건에 맞는 수열의 m번째 줄의 n번째 항을 구하는 문제입니다.

수열의 규칙은 다음과 같습니다.

1행 : 1  1

2행 : 1  2(1+1)  1

3행 : 1  3(1+2)  2  3(2+1)  1

4행 : 1  4(1+3)  3  5(3+2)  2  5(2+3)  3  4(3+1)  1

이처럼 이전 행을 그대로 가져오되 두 숫자사이에 양쪽 숫자의 합을 넣어주면 됩니다.

 

 

2. 풀이 방법

STEP 1.  m+1번째 행에 m번째 행의 값을 가져오되 각 숫자사이에 공백을 넣어 준다.

STEP 2. 공백에 양쪽 숫자의 합을 넣어준다. 

 

 

3. 해답

#include <stdio.h>

int arr[19][999999] = { 0, };

int main() {
	int m, n;

	scanf("%d %d", &m, &n);

	arr[0][0] = arr[0][1] = 1;

	for (int i = 1; i < m; i++) {
		// 숫자와 숫자 사이에 공백 만들기
		for (int j = 499999; j >= 0; j--) {
			if (arr[i - 1][j] == 0) continue;

			arr[i][j * 2] = arr[i - 1][j];
		}
		// 공백에 양쪽 숫자의 합 입력
		for (int j = 1; j < 999999; j += 2) {
			if (arr[i][j + 1] == 0) break;

			arr[i][j] = arr[i][j - 1] + arr[i][j + 1];
		}
	}

	printf("%d", arr[m - 1][n - 1]);


	return 0;
}