[백준 BOJ] 2775번 부녀회장이 될테야 (C언어)

문제 설명

https://www.acmicpc.net/problem/2775

2775번: 부녀회장이 될테야

 

접근 방법 - 수학적 사고력을 필요로 하는 문제

백준의 2775번 문제는 수학적 사고력을 이용해서 해결해야 하는 문제이다.

해당 문제는 손으로 직접 값을 구하다 보면 특정 규칙을 찾을 수 있다.

필자는 아래의 규칙을 찾았으며 이를 활용하여 문제를 해결하였다.

 

필자가 찾아낸 규칙

- 해당 문제의 설명에 따르면, 0층의 n호는 n명이 거주하며, m층의 1호는 1명이 거주한다.

- 그리고 1층 2호부터 거주자 수를 계산해보면 이러한 규칙이 있다.

home[i][j] = home[i-1][j] + home[i][j-1]
=> 특정 위치에 있어서, 바로 아래층 집의 거주자와 바로 왼쪽 집의 거주자를 합한 값이 이 위치의 거주자 값이다.

필자는 이 규칙을 이용해 배열을 먼저 전체적으로 초기화한 뒤, 입력값을 순차적으로 받아 바로 출력하는 방식으로 문제를 해결하였다.

 

코드의 실행 순서

1) 문제에서 제시된 최대 범위의 층수 및 호수대로 배열을 선언한다.

 

2) 배열을 모두 초기화한다.

- 0층 a호인 경우, a 값으로 초기화한다.

- b층 1호인 경우, 1로 초기화한다.

- 이 외의 경우, 즉 c층 d호인 경우, [c-1][d]의 거주자와 [c][d-1]의 거주자를 합하여 값을 초기화한다.

 

3) 테스트 케이스, 각 층수와 호수를 입력받는다.

 

4) 각 층수와 호수에 따른 배열값을 바로 출력한다.

 

5) 모든 테스트 케이스가 종료되면, 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <stdio.h>

//백준 2775번 코드
int arr[14][15];
int main() {
	for (int i = 0; i <= 14; i++) {
		for (int j = 1; j <= 14; j++) {
			if (i == 0 || j == 1) { arr[i][j] = j; }
			else {
				arr[i][j] = arr[i - 1][j] + arr[i][j - 1];
			}
		}
	}

	int t;	int k, n;
	scanf("%d", &t);
	for (int m = 0; m < t; m++) {
		scanf("%d %d", &k, &n);
		printf("%d\n", arr[k][n]);
	}
}

 

제출 결과

(2021.12.20 백준 2775번 문제 제출 결과)